解題區/解題區 - UVa

UVa 12017 - Imitation

Problem

遞移性 a->b, b->c 則 a->c。

給定一張圖的遞移，求不改變任兩個點的遞移關係，最多可以有多少邊、最少需要多少條邊。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
3
3 3
1 2
2 3
1 3
3 3
1 2
2 3
3 1
9 9
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7

Sample Output

1
2
3
Case #1: 2 3
Case #2: 3 6
Case #3: 9 18

Solution

從最多條邊來說，最簡單使用 floyd 內閉包的算法 O(n^3)。

1
2
3
4
for k in n
    for i in n
        for j in n
            f[i, j] |= f[i][k] & f[k][j]

最後計算 1(true) 的個數即可，但是這一題 n 最大為 1000，必須從 O(n^3) -> O(n^2)，取而代之，採用 dfs 的方式，把每一個點 s 當作起點，則可以搜索到的點 t，都存有遞移關係 s->t。

而在處理最少條邊，採用強連通元件 (SCC)，先將數個點縮成一個元件，則一個強連通元件內的個數只需要使用一個環即可代替原先的遞移關係。縮圖完之後，會產生 DAG 圖，DAG 圖上仍然會有多餘的遞移關係，從 a->b, b->c, a->c 中，可以發現 a->c 可以不存在。

最後，採用 bfs 的方式，對於每個點 s 當作起點找到最長路徑，假使 t 距離 s 大於 1，且存在 s->t，則可以再少一條邊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> g[1005], dag[1005];
int vfind[1005], findIdx;
int stk[1005], stkIdx;
int in_stk[1005], visited[1005];
int contract[1005], contract_cnt[1005];
int scc(int nd) {
    in_stk[nd] = visited[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(int i = 0; i < g[nd].size(); i++) {
        if(!visited[g[nd][i]])
            mn = min(mn, scc(g[nd][i]));
        if(in_stk[g[nd][i]])
            mn = min(mn, vfind[g[nd][i]]);
    }
    if(mn == vfind[nd]) {
        contract_cnt[nd] = 0;
        do {
            in_stk[stk[stkIdx]] = 0;
            contract[stk[stkIdx]] = nd;
            contract_cnt[nd]++;
        } while(stk[stkIdx--] != nd);
    }
    return mn;
}
int min_edge, max_edge, mg[1024][1024];
void dfs(int u, int start) {
    mg[start][u] = 1, max_edge++;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!mg[start][v]) {
            dfs(v, start);
        }
    }
}
void bfs(int st, int n) {
    queue<int> Q;
    int dist[1024] = {}, u, v;
    Q.push(st);
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        for (int i = 0; i < dag[u].size(); i++) {
            v = dag[u][i];
            if (dist[v] < min(dist[u] + 1, 2)) {
                dist[v] = min(dist[u] + 1, 2);
                Q.push(v);
            }
        }
    }
    for (int i = 0; i < dag[st].size(); i++) {
        int v = dag[st][i];
//        printf("%d %d %d\n", st, v, dist[v]);
        if (dist[v] != 1) {
            if (mg[st][v]) {
                mg[st][v] = 0, min_edge--;
            }
        }
    }
}
int main() {
    int testcase, cases = 0, n, m;
    int u, v;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i <= n; i++)
            g[i].clear(), dag[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
        }
        min_edge = max_edge = 0;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                mg[i][j] = 0;
        
        for (int i = 1; i <= n; i++)
            dfs(i, i);
        
        // SCC
        memset(visited, 0, sizeof(visited));
        memset(in_stk, 0, sizeof(in_stk));
        for(int i = 1; i <= n; i++) {
            if(!visited[i]) {
                findIdx = stkIdx = 0;
                scc(i);
            }
        }
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                mg[i][j] = 0;
        
        for(int i = 1; i <= n; i++) {
            int x = contract[i], y;
            for(vector<int>::iterator it = g[i].begin();
                it != g[i].end(); it++) {
                y = contract[*it];
                if(x != y) {
                    if (!mg[x][y]) {
                        mg[x][y] = 1, dag[x].push_back(y);
                        min_edge++;
                    }
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            if (contract[i] == i) {
                if (contract_cnt[i] > 1)
                    min_edge += contract_cnt[i];
                bfs(i, n);
            }
        }
        printf("Case #%d: %d %d\n", ++cases, min_edge, max_edge - n);
    }
    return 0;
}
/*
 3
 3 3
 1 2
 2 3
 1 3
 3 3
 1 2
 2 3
 3 1
 9 9
 1 2
 2 3
 3 1
 4 5
 5 6
 6 4
 7 8
 8 9
 9 7
 */
Read More +
解題區/解題區 - UVa

UVa 12011 - Complete the Set

Problem

找到一個完備集合，其任兩個數字做 AND 和 OR 運算都在集合中。

給定部分集合，請問至少還需要幾個元素使得其變成完備集合。

Sample Input

1
2
3
4
5
6
7
8
9
4
5
0 1 3 5 7
2
2 4
3
3 7 11
3
1 2 4

Sample Output

1
2
3
4
Case #1: 0
Case #2: 2
Case #3: 1
Case #4: 5

Solution

這一題從傳錯題目開始已經放著很久，當時怎麼樣都沒有想法，直接著手 O(n * 2^20) 最慘運行方式，其實這種複雜度與通過的複雜度就差那麼一點的 n。 // 肯定是死在 n。

其實可以發現到，假使挑選 i-th bit 很有可能會連帶其他的 bit 一同帶上，因此對於 i-th bit 最小化攜帶的 bit (做 AND 最小化)。

最後窮舉攜帶 i-th bit 是否要挑 (OR 所有攜帶的 bit)，複雜度降至 O(2^20)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    int n, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        set<int> S;
        int A[32] = {}, all = (1<<18) - 1; // used i-th bits minimum attachment.
        memset(A, -1, sizeof(A));
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            S.insert(x);
            all &= x; // used mask = 0
            for (int j = 0; j < 18; j++) {
                if ((x>>j)&1) {
                    if (A[j] == -1)
                        A[j] = x;
                    else
                        A[j] = A[j] & x;
                }
            }
        }
        S.insert(all);
        int m = 0;
        for (int i = 0; i < 18; i++) {
            if (A[i] != -1)
                A[m++] = A[i];
        }
        for (int i = 1; i < (1<<m); i++) { // used mask
            int num = 0;
            for (int j = 0; j < m; j++) {
                if ((i>>j)&1) {
                    num |= A[j];
                }
            }
            S.insert(num);
        }
        printf("Case #%d: %d\n", ++cases, (int)S.size() - n);
    }
    return 0;
}
/*
 4
 5
 0 1 3 5 7
 2
 2 4
 3
 3 7 11
 3
 1 2 4
 */
Read More +
解題區/解題區 - UVa

UVa 11587 - Brick Game

Problem

現在有 N 個積木，兩個人輪流拿 X 個積木 (X in Set, X <= 20)，直到最後一個人拿走最後一塊積木獲勝，如果無法拿取則對方獲勝。

給定一個勝負的前 M 個積木的博弈結果，求 |Set| 最小為何，相同時則輸出字典順序最小的。

Sample Input

1
2
3
4
3
WWLWWL
WWWW
WLW

Sample Output

1
2
3
Case 1: 1 2
Case 2: 1 2 3 4
Case 3: 1

Solution

這一題很賊的地方在於 X <= 20，那麼已經可以發現可以窮舉集合情況，從最小的的集合順序開始窮舉。

窮舉的方式採用 stl 中的 next_permutation。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
    int testcase, cases = 0;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s + 1);
        printf("Case %d:", ++cases);
        s[0] = 'L';
        int A[20], slen = (int)strlen(s);
        for (int m = 1, n = 20; m <= 20; m++) { // C(n, m)
            int v[20] = {}; // generating combination
            for (int i = 0; i < n - m; i++)
                v[i] = 1;
            sort(v, v+n);
            do {
                int cn = 0;
                for (int i = 0; i < 20; i++) {
                    if (!v[i])
                        A[cn++] = i + 1;
                }
                // dp
                int ok = 1;
                for (int i = 1; i < slen; i++) {
                    int d = 'L';
                    for (int j = 0; j < cn && i - A[j] >= 0; j++) {
                        if (s[i - A[j]] == 'L') {
                            d = 'W';
                            break;
                        }
                    }
                    if (d != s[i]) {
                        ok = 0;
                        break;
                    }
                }
                if (ok) {
                    for (int i = 0; i < cn; i++)
                        printf(" %d", A[i]);
                    puts("");
                    m = 100; // break outer loop
                    break;
                }
            } while (next_permutation(v, v + n));
        }
    }
    return 0;
}
/*
 3
 WWLWWL
 WWWW
 WLW
 
 Case 1: 1 2
 Case 2: 1 2 3 4
 Case 3: 1
 */
Read More +
解題區/解題區 - UVa

UVa 11071 - Permutation Representation

Problem

給定一個置換群，要我們表示成以下特定的形式，1 ≤ n ≤ 200000。

由右至左看，第一次為了填5必須移動2位，第二次移動填4也是移動2位
3 2 5 1 4 -> 1 4 3 2 5 移動 2
1 4 3 2 5 -> 3 2 1 4 5 移動 2
3 2 1 4 5 -> 2 1 3 4 5 移動 2
2 1 3 4 5 -> 1 2 3 4 5移動 1

解題者：李育賢
解題日期：2008 年 3 月 21 日

Sample Input

1
2
3
4
5
6
5
1 2 3 4 5
3 2 5 1 4
4
1 2 3 4
3 4 1 2

Sample Output

1
2
0 1 2 2 2
0 0 0 2

Solution

李育賢他的解法使用線段樹，靜態操作 shift rotate 和 remove 的問題，仔細想想似乎也不難，但是沒想到我用了模擬的塊狀鏈表解決這一道題目。

為了解決 shift，還必須增加數字的映射，否則沒辦法再 O(sqrt(n)) 時間內完成操作。

塊狀鏈表相當暴力模擬，最簡單地盡可能讓塊差不多是 sqrt(n) 個元素，這樣再 shift 的時候，可以將 head 指標移動次數卡在 sqrt(n) 將給一個操作都限制在 O(sqrt(n))。

塊狀鏈表看看就好，還是回去寫線段樹吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
// 11071 - Permutation Representation
#define MAXN 262144
int A[MAXN], B[MAXN], C[MAXN];
struct PILE {
    int v[512], size;
    PILE *next;
    int label;
    static int MAXSIZE, BUFSIZE;
    static PILE *head;
    PILE() {
        size = label = 0;
        next = NULL;
    }
};
int PILE::MAXSIZE = 512, PILE::BUFSIZE = 0;
PILE* PILE::head = NULL;
int mp[MAXN]; // map
PILE* removePileElement(PILE *where, int pos) {
    if (pos == where->size - 1) {
        where->size--;
        return where->next;
    }
    assert(pos < where->size);
    PILE::BUFSIZE++;
    PILE *m = new PILE();
    m->label = PILE::BUFSIZE;
    assert(m->size == 0);
    for (int i = pos + 1; i < where->size; i++) {
        m->v[m->size++] = where->v[i];
        assert(where->v[i] < MAXN);
        mp[where->v[i]] = m->label;
    }
    where->size = pos;
    m->next = where->next;
    where->next = m;
    return m;
}
int shrinkList() {
    for (PILE *i = PILE::head; i->next != PILE::head; ) {
        PILE *next = i->next;
        int prevsize = i->size;
        int nextsize = next->size;
        if (prevsize + nextsize <= PILE::MAXSIZE) {
            for (int j = 0; j < next->size; j++) {
                i->v[i->size++] = next->v[j];
                mp[next->v[j]] = i->label;
            }
            i->next = next->next;
            delete next;
        } else
            i = i->next;
    }
    return 0;
}
void printPile() {
    PILE *i = PILE::head;
    do {
        for (int j = 0; j < i->size; j++) {
            printf("%d -> ", i->v[j] + 1);
        }
        printf(" | ");
        i = i->next;
    } while (i != PILE::head);
    puts("\n====");
}
void solve(int n) {
//    printPile();
    for (int i = n - 1; i >= 0; i--) {
        PILE *where = NULL;
        int pos = -1;
//        printf("%d\n", i);
        for (PILE *j = PILE::head; ; j = j->next) {
            if (j->label == mp[i]) {
                where = j;
                break;
            }
        }
        assert(where != NULL);
        for (int j = 0; j < where->size; j++) {
            if (where->v[j] == i) {
                pos = j;
                break;
            }
        }
        assert(pos >= 0  && pos < where->size);
        int shift = where->size - pos - 1;
//        printf("%d %d %d\n", node[where].size, pos, shift);
        for (PILE *j = where->next; j != PILE::head; j = j->next) {
            shift += j->size;
        }
//        printf("shift %d\n", shift);
        C[i] = shift;
        PILE::head = removePileElement(where, pos);
        shrinkList();
//        printPile();
    }
    for (PILE *i = PILE::head, *j = i->next; j != PILE::head; j = i->next) {
        delete i;
        i = j;
    }
}
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &B[i]);
        }
//        for (int i = 0; i < n; i++) {
//            A[i] = i + 1;
//            B[i] = A[i];
//        }
//        for (int i = 0; i < n; i++) {
//            int x = rand()%n;
//            int y = rand()%n;
//            swap(B[x], B[y]);
//        }
        for (int i = 0; i < n; i++) {
            C[A[i] - 1] = B[i] - 1;
        }
        
        PILE *node = new PILE();
        PILE::MAXSIZE = (int)sqrt(n) + 1;
        PILE::head = node;
        PILE::BUFSIZE = 0;
        PILE::BUFSIZE++;
        node->label = PILE::BUFSIZE, node->next = node;
        for (int i = 0; i < n; i++) {
            node->v[node->size++] = C[i];
            mp[C[i]] = node->label;
            if (node->size == PILE::MAXSIZE) {
                PILE *tmp = new PILE();
                PILE::BUFSIZE++;
                tmp->label = PILE::BUFSIZE;
                tmp->next = node->next;
                node->next = tmp;
                node = node->next;
            }
        }
        
        solve(n);
        
        for (int i = 0; i < n; i++) {
            printf("%d%c", C[i], i == n - 1 ? '\n' : ' ');
        }
    }
    return 0;
}
/*
 5
 1 2 3 4 5
 3 2 5 1 4
 4
 1 2 3 4
 3 4 1 2
*/
Read More +
解題區/解題區 - UVa

UVa 10694 - Combinatorial Summation

Problem

對於組合公式，輸出其結果。

Sample Input

1
2
3
2
3
4

Sample Output

1
2
7
14

Solution

暴力法將前幾項找出來，發現其相鄰兩項之差恰好有規律。

1
2
0 1 3 7 14 26 46 79 133 
  0 2 4 7 12 20 33 54

其規律是前兩項總和再加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        BigInteger[] f1 = new BigInteger[1024];
        BigInteger[] f2 = new BigInteger[1024];
        f1[1] = BigInteger.valueOf(2);
        f1[2] = BigInteger.valueOf(4);
        f2[0] = BigInteger.valueOf(0);
        f2[1] = BigInteger.valueOf(1);
        for (int i = 3; i < f1.length; i++)
            f1[i] = f1[i - 2].add(f1[i - 1]).add(BigInteger.ONE);
        for (int i = 2; i < f2.length; i++)
            f2[i] = f2[i - 1].add(f1[i - 1]);
        Scanner cin = new Scanner(System.in);
        int testcase = cin.nextInt();
        while (testcase-- != 0) {
            int n = cin.nextInt();
            if (n < 0)
                n = 0;
            System.out.println(f2[n]);
        }
    }
}
/*
 * 0 1 3 7 14 26 46 79 133 
 	 0 2 4 7 12 20 33 54
 */
Read More +
解題區/解題區 - UVa

UVa 1635 - Irrelevant Elements

Problem

題目給定一種亂數產生方式，一開始先給定 n 個數字序列 ai (1 <= i <= n)，之後相鄰兩兩相加得到 n - 1 個數字的序列，最後這一個數字 mod m = ? 來決定最後要輸出的亂數。

請問最後產生出來的數字 無關序列的第幾項。

Sample Input

1
3 2

Sample Output

1
2
1
2

Solution

其實可以見到的，第 i 個數字會在最後使用 C(n-1, i) 次，無關的意思，也就是說恰好 C(n-1, i) == 0 mod m，不管 ai 為何皆不影響最後產生出來的數字。

為了加速運算，我們必須先質因數分解 m 的結果。

對於 C(a, b) = a! / (b!(b-a)!) 是否整除 m，查閱 m 的所有質因數 p 的個數是否符合需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
#define maxL (50000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k, l;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(j = i + i; j <= n; j += i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int isPrime(int n) {
    for(int i = 0; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            return 0;
        }
    }
    return 1;
}
vector< pair<int, int> > factor(int n) {
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
int g(int n, int p) {
    int ret = 0;
    long long pp = p;
    while (n >= pp) {
        ret += n / pp;
        pp *= p;
    }
    return ret;
}
int main() {
    sieve();
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        vector< pair<int, int> > f = factor(m);
        vector<int> solution;
        n--;
        for (int i = 0; i <= n; i++) {
            int ok = 1;
            for (int j = 0; j < f.size() && ok; j++) {
                int p = f[j].first;
                int cnt = g(n, p) - g(i, p) - g(n - i, p); // C(n, i) has p^cnt.
                if (cnt < f[j].second) {
                    ok = 0;
                }
            }
            if (ok) {
                solution.push_back(i + 1);
            }
        }
        printf("%d\n", (int)solution.size());
        for (int i = 0; i < solution.size(); i++) {
            printf("%d%s", solution[i], i == solution.size() - 1 ? "" : " ");
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1594 - Ducci Sequence

Problem

將序列根據步驟轉換，是否會產生迴圈或者是回歸到 0。

Sample Input

1
2
3
4
5
6
7
8
9
4 
4 
8 11 2 7 
5 
4 2 0 2 0 
7 
0 0 0 0 0 0 0 
6 
1 2 3 1 2 3

Sample Output

1
2
3
4
ZERO 
LOOP 
ZERO 
LOOP

Solution

用 hash (RS hashing) 來壓縮一下儲存的方式，碰撞的機率應該是挺低的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <map>
#include <algorithm>
using namespace std;
int nextSeq(int A[], int n) {
    int B[32];
    A[n] = A[0];
    for (int i = 0; i < n; i++)
        B[i] = abs(A[i] - A[i+1]);
    for (int i = 0; i < n; i++)
        A[i] = B[i];
    return 1;
}
int main() {
    int testcase, n, A[32];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        map<int, int> R;
        do {
            int ok = 1, hash = 0;
            int a = 63689, b = 378551;
            for (int i = 0; i < n; i++) {
                hash = hash * a + A[i], a = a * b;
                ok &= A[i] == 0;
            }
            if (ok) {
                puts("ZERO");
                break;
            }
            int &f = R[hash];
            if (f) {
                puts("LOOP");
                break;
            }
            f = 1;
        } while (nextSeq(A, n));
    }
    return 0;
}
/*
 4
 4
 8 11 2 7
 5
 4 2 0 2 0
 7
 0 0 0 0 0 0 0
 6
 1 2 3 1 2 3
 */
Read More +
解題區/解題區 - UVa

UVa 1590 - IP Networks

Problem

找在同一個區域的 IP 中的 IP 遮罩。

Sample Input

1
2
3
4
3 
194.85.160.177 
194.85.160.183 
194.85.160.178

Sample Output

1
2
194.85.160.176 
255.255.255.248

Solution

也就是說我們必須找到其最長共同前綴，知道共同前綴的長度直接輸出 1111111…111000。

用 trie 對於這一道題目，只會用到 0/1 兩種字符，也可以直接暴力掃描，用 trie 沒有甚麼特別快的好處。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Trie {
    int n, label, dist;
    int link[2];
} Node[1048576];
int TrieSize;
int insertTrie(const char* str) {
    static int i, idx;
    for(i = idx = 0; str[i]; i++) {
        if(Node[idx].link[str[i]-'0'] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[TrieSize].label = TrieSize;
            Node[TrieSize].dist = i + 1;
            Node[idx].link[str[i]-'0'] = TrieSize;
        }
        idx = Node[idx].link[str[i]-'0'];
    }
    Node[idx].n ++;
    return Node[idx].label;
}
void binaryIP(const int ip[], char buf[]) {
    int idx = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 8 - 1; j >= 0; j--) {
            buf[idx++] = '0' + ((ip[i]>>j)&1);
        }
    }
    buf[idx] = '\0';
}
void getAllLCP(char buf[]) {
    int idx = 0, bidx = 0;
    do {
        int branch = 0, next = 0, c = 0;
        for (int i = 0; i < 2; i++) {
            if (Node[idx].link[i]) {
                branch++, next = Node[idx].link[i], c = i;
            }
        }
        if (branch != 1)
            break;
        buf[bidx++] = c + '0', idx = next;
    } while (true);
    buf[bidx] = '\0';
}
int main() {
    int n, ip[4];
    char bip[128];
    while (scanf("%d", &n) == 1) {
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        for (int i = 0; i < n; i++) {
            scanf("%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]);
            binaryIP(ip, bip);
            insertTrie(bip);
        }
        getAllLCP(bip);
        int m = (int)strlen(bip);
        for (int i = 0; i < 4; i++) {
            int bb = 0;
            for (int j = 8 - 1; j >= 0; j--) {
                if (i * 8 + 7 - j < m) {
                    if (bip[i * 8 + 7 - j] == '1') {
                        bb |= 1<<j;
                    }
                }
            }
            printf("%d%c", bb, i == 3 ? '\n' : '.');
        }
        for (int i = 0; i < 4; i++) {
            int bb = 0;
            for (int j = 8 - 1; j >= 0; j--) {
                if (i * 8 + 7 - j < m) {
                    bb |= 1<<j;
                }
            }
            printf("%d%c", bb, i == 3 ? '\n' : '.');
        }
    }
    return 0;
}
/*
 3
 194.85.160.177
 194.85.160.183
 194.85.160.178
*/
Read More +
解題區/解題區 - UVa

UVa 816 - Abbott's Revenge

Problem

給每一個路口的可行進方向，請問從起點到終點的最短路徑為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END

Sample Output

1
2
3
4
5
SAMPLE
  (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1)
  (2,2) (1,2) (1,3) (2,3) (3,3)
NOSOLUTION
  No Solution Possible

Solution

忘記有可能起點和終點一樣，所以刷了不少 WA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>
using namespace std;
int g[32][32][4];
char dirName[1024] = "NESW";
const int dx[] = {-1, 0, 1, 0}; // N, E, S, W
const int dy[] = {0, 1, 0, -1};
void bfs(int sx, int sy, int sdir, int ex, int ey) {
    int visited[32][32][4] = {};
    int fdir[] = {-1, 1, 0}, tx, ty;
    queue<int> X, Y, D;
    pair<int, pair<int, int> > from[32][32][4];
    int ox = sx, oy = sy;
    sx += dx[sdir], sy += dy[sdir];
    X.push(sx), Y.push(sy), D.push(sdir);
    visited[sx][sy][sdir] = 1;
    from[sx][sy][sdir] = make_pair(-1, make_pair(-1, -1));
    while (!X.empty()) {
        sx = X.front(), X.pop();
        sy = Y.front(), Y.pop();
        sdir = D.front(), D.pop();
        if (sx == ex && sy == ey) {
            int tx, ty, dir;
            stack< pair<int, int> > stk;
            tx = sx, ty = sy, dir = sdir;
            while (tx >= 0) {
                stk.push(make_pair(tx, ty));
                int ttx = from[tx][ty][dir].second.first;
                int tty = from[tx][ty][dir].second.second;
                int tdd = from[tx][ty][dir].first;
                tx = ttx, ty = tty, dir = tdd;
            }
            stk.push(make_pair(ox, oy));
            int output = 0;
            while (!stk.empty()) {
                if (output%10 == 0) {
                    printf("\n ");
                }
                pair<int, int> pt = stk.top();
                stk.pop();
                printf(" (%d,%d)", pt.first, pt.second);
                output++;
            }
            puts("");
            return ;
        }
        for (int i = 0; i < 3; i++) {
            if (g[sx][sy][sdir]&(1<<i)) {
                int dir = (sdir + fdir[i] + 4)%4;
                tx = sx + dx[dir], ty = sy + dy[dir];
                if (visited[tx][ty][dir] == 0) {
                    visited[tx][ty][dir] = 1;
                    X.push(tx), Y.push(ty), D.push(dir);
                    from[tx][ty][dir] = make_pair(sdir, make_pair(sx, sy));
                }
            }
        }
    }
    printf("\n  No Solution Possible\n");
}
int main() {
    char testcase[1024], sdir[1024];
    int x, y, sx, sy, ex, ey;
    while (gets(testcase) && strcmp("END", testcase)) {
        memset(g, 0, sizeof(g));
        scanf("%d %d %s %d %d", &sx, &sy, sdir, &ex, &ey);
        while (scanf("%d", &x) == 1 && x) {
            scanf("%d", &y);
            char token[10];
            while (scanf("%s", token) == 1 && token[0] != '*') {
                int dir = find(dirName, dirName+4, token[0]) - dirName;
                int follow = 0;
                for (int i = 1; token[i]; i++) {
                    switch (token[i]) {
                        case 'L': follow |= 1; break;
                        case 'R': follow |= 2; break;
                        case 'F': follow |= 4; break;
                    }
                }
                g[x][y][dir] = follow;
            }
        }
        int dir = find(dirName, dirName+4, sdir[0]) - dirName;
        printf("%s", testcase);
        bfs(sx, sy, dir, ex, ey);
        while (getchar() != '\n');
    }
    return 0;
}
/*
SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END
 
 
 SAMPLE
 3 1 N 3 3
 1 1 WL NR *
 1 2 WLF NR ER *
 1 3 NL ER *
 2 1 SL WR NF *
 2 2 SL WF ELF *
 2 3 SFR EL *
 0
 NOSOLUTION
 3 1 N 3 2
 1 1 WL NR *
 1 2 NL ER *
 2 1 SL WR NFR *
 2 2 SR EL *
 0
 MyMaze 1
 3 1 N 1 1
 0
 MyMaze 2
 3 1 N 3 1
 0
 MyMaze 3
 3 1 N 2 1
 0
 MyMaze 4
 2 2 W 3 2
 1 1 NR *
 1 2 ER *
 2 1 WR *
 2 2 SF *
 0
 MyMaze 5
 2 2 N 2 3
 1 1 WL *
 1 2 NL *
 2 1 SF *
 2 2 NR *
 3 1 SL *
 3 2 EL *
 0
 Circle
 2 1 N 2 1
 1 1 NR *
 1 2 ER *
 2 2 SF *
 3 1 WR *
 3 2 SR *
 0
 Robert Abbott's Atlanta Maze
 4 2 N 4 3
 1 1 NR WL *
 1 2 NLR WF EFR *
 1 3 EFR WFR NL *
 1 4 ER NL *
 2 1 SFL WL NFR *
 2 2 EL SFLR WFRL NFL *
 2 3 EFLR SF NF WFRL *
 2 4 SR ELR NF *
 3 1 WR SL *
 3 2 EFL SLR WR NF *
 3 3 EFL SLR WL *
 3 4 EL SR *
 0
 END
 */
Read More +
解題區/解題區 - UVa

UVa 721 - Invitation Cards

Problem

ACM 參賽選手要到比賽會場，公車都是單向運行，求選手們來回的最少花費。

給一個有向圖，求從編號 1 到所有點的最短路徑總和，以及所有點到編號 1 的最短路徑總和。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample Output

1
2
46
210

Solution

對一開始給定的圖，從編號 1 做一次 SSSP (單源最短路徑)，隨後再對題目給的反向圖做一次 SSSP 即可以得到所有點到編號 1 的最短路徑。

這一題很類似於 zerojudge 的地道問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 1048576
vector< pair<int, long long> > g[MAXN], invg[MAXN];
long long dist[MAXN];
int inq[MAXN];
long long spfa(int source, int n, vector< pair<int, long long> > g[]) {
    for (int i = 0; i < n; i++) {
        dist[i] = 1LL<<60, inq[i] = 0;
    }
    queue<int> Q;
    int u, v;
    long long w;
    Q.push(source), dist[source] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].first, w = g[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    Q.push(v), inq[v] = 1;
                }
            }
        }
    }
    long long ret = 0;
    for (int i = 0; i < n; i++) {
        ret += dist[i];
    }
    return ret;
}
int main() {
    int testcase, N, M;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        for (int i = 0; i < N; i++) {
            g[i].clear(), invg[i].clear();
        }
        for (int i = 0; i < M; i++) {
            int x, y, c;
            scanf("%d %d %d", &x, &y, &c);
            x--, y--;
            g[x].push_back(make_pair(y, c));
            invg[y].push_back(make_pair(x, c));
        }
        long long ret = 0;
        ret += spfa(0, N, g);
        ret += spfa(0, N, invg);
        printf("%lld\n", ret);
    }
    return 0;
}
/*
 2
 2 2
 1 2 13
 2 1 33
 4 6
 1 2 10
 2 1 60
 1 3 20
 3 4 10
 2 4 5
 4 1 50
*/
Read More +