解題區/解題區 - UVa

UVa 12462 - Rectangle

Problem

在長條圖中，每一條有其的數值和顏色屬性，找到一個最大的面積，使得每一個顏色都出現過。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
6 3
2 3 1 7 3 5
2 0 1 0 1 2
3 1
2 2 2
0 0 0
5 2
3 2 1 2 3
1 0 1 0 1
6 4
1 2 3 4 5 6
0 1 2 3 1 0
7 2
1 2 3 4 3 2 1
0 1 0 1 0 1 0
10 2
2 1 2 1 1 2 1 2 2 1
1 0 0 0 1 0 0 1 1 0
3 2
1000000000 999999997 999999999
0 1 1
0 0

Sample Output

1
2
3
4
5
6
7
9
6
5
12
10
10
2999999991

Solution

對於每一個長條 h[i]，勢必將往左往右延伸到第一個數值比較低的，因此會得到一個區間 [l, r]，如果 [l, r] 之間不具有所有顏色，則忽略之。反之紀錄 h[i] * (r - l + 1) 是否為最大值。這樣的貪心方式，盡可能會具有最多的顏色，同時考慮到所有最大面積會卡住的地方。

但是窮舉找到每一個 [l, r] 相當費時，這裡運用單調堆的思路，分別從左、從右側往反方向掃描，掃描時維護堆裡面元素呈現遞減情況，分別找到左右端點後，檢查是否區間內有相符的顏色個數。

找所有左右端點只需要 O(n) 時間，但是檢查區間內的顏色個數是否符合則必須 O(nm)。

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
#include <stdio.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
#define MAXN 131072
#define MAXC 32
int h[MAXN], c[MAXN], sumc[MAXN][MAXC];
int L[MAXN], R[MAXN]; 
int main() {
    int N, C;
    while (scanf("%d %d", &N, &C) == 2 && N) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &h[i]);
        for (int i = 1; i <= N; i++)
            scanf("%d", &c[i]);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < C; j++)
                sumc[i][j] = sumc[i-1][j];
            sumc[i][c[i]]++;
        }
        for (int i = 0; i < C; i++)
            sumc[N+1][i] = sumc[N][i]; 
            
        h[0] = h[N+1] = 0;
        stack<int> stk;
        stk.push(0);
        for (int i = 1; i <= N; i++) {
            while (h[i] <= h[stk.top()])
                stk.pop();
            L[i] = stk.top() + 1, stk.push(i);
        }
        
        while (!stk.empty())	stk.pop();
        
        stk.push(N + 1);
        for (int i = N; i >= 1; i--) {
            while (h[i] <= h[stk.top()])
                stk.pop();
            R[i] = stk.top() - 1, stk.push(i);
        }
        
        long long ret = 0;
        for (int i = 1; i <= N; i++) {
            int ok = 1;
            for (int j = 0; j < C; j++)
                ok &= sumc[R[i]][j] - sumc[L[i] - 1][j] > 0;
            if (ok)
                ret = max(ret, (long long) h[i] * (R[i] - L[i] + 1));
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
6 3
2 3 1 7 3 5
2 0 1 0 1 2
3 1
2 2 2
0 0 0
5 2
3 2 1 2 3
1 0 1 0 1
6 4
1 2 3 4 5 6
0 1 2 3 1 0
7 2
1 2 3 4 3 2 1
0 1 0 1 0 1 0
10 2
2 1 2 1 1 2 1 2 2 1
1 0 0 0 1 0 0 1 1 0
3 2
1000000000 999999997 999999999
0 1 1
*/
Read More +
解題區/解題區 - UVa

UVa 12618 - I Puzzle You

Problem

給一個 n = 3 魔術方塊的盤面，找最少操作次數使其每一面顏色都相同。

每一次操作限定旋轉 90 度。如果需要的步數大於 7 步，直接輸出 Impossible。

Sample Input

1
2
3
4
5
4
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY
WWWWWWRRRRRYBBBWOOGGGRRYBBBWOOGGGRRYBBBWOOGGGOOOYYYYYY
WWBWWBWWBRRRBBYOOOWGGBBYOOOWGGRRRRRRBBYOOOWGGYYGYYGYYG
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYGGGYYYYYY

Sample Output

1
2
3
4
Case 1: 0
Case 2: 1
Case 3: 2
Case 4: Impossible

Solution

首先，關於旋轉操作只能手動打表，總共會有 9 種旋轉序列 (窮舉時操作成順、逆兩種)，其中的 6 種序列會使得相鄰的面旋轉 90 度 (必須特別考慮這邊緣的旋轉)。

關於啟發式：六個面中，其中一個面具有最多的顏色，將會是預估的最少移動操作。

這一個啟發式相當重要，也非常難想，參考 http://blog.csdn.net/qq564690377/article/details/16867503

一開始使用 IDA* 的效果似乎不很好，於是換了雙向 BFS (doubling BFS)，由於步數限定 7 步內，從目標狀態建表 4 步內的結果。接著對於每一組詢問，搜索 3 步內的操作，查看是否會相遇。

狀態壓縮可以採用重新命名，也就是最小化表示法，不管顏色，只考慮同構。

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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
#include <stdio.h> 
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int rotateInfo[9][12] = {
    {1, 4, 7, 13, 25, 37, 46, 49, 52, 45, 33, 21}, // margin rotate begin
    {3, 6, 9, 15, 27, 39, 48, 51, 54, 43, 31, 19},
    {10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21},
    {34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45},
    {1, 2, 3, 18, 30, 42, 54, 53, 52, 34, 22, 10},
    {7, 8, 9, 16, 28, 40, 48, 47, 46, 36, 24, 12},
    {2, 5, 8, 14, 26, 38, 47, 50, 53, 44, 32, 20}, // center rotate begin
    {4, 5, 6, 17, 29, 41, 51, 50, 49, 35, 23, 11},
    {22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33}
};
int rotateFace[6][9] = { // not center rotate
    {10, 11, 12, 22, 23, 24, 34, 35, 36},
    {18, 17, 16, 30, 29, 28, 42, 41, 40},
    {1, 4, 7, 2, 5, 8, 3, 6, 9},
    {52, 49, 46, 53, 50, 47, 54, 51, 48},
    {21, 20, 19, 33, 32, 31, 45, 44, 43},
    {13, 14, 15, 25, 26, 27, 37, 38, 39}
};
int rotateOrder1[9] = {2, 5, 8, 1, 4, 7, 0, 3, 6};
int rotateOrder2[9] = {6, 3, 0, 7, 4, 1, 8, 5, 2};
int face[6][9] = {
    {1, 2, 3, 4, 5, 6, 7, 8, 9},
    {10, 11, 12, 22, 23, 24, 34, 35, 36},
    {13, 14, 15, 25, 26, 27, 37, 38, 39},
    {16, 17, 18, 28, 29, 30, 40, 41, 42},
    {19, 20, 21, 31, 32, 33, 43, 44, 45},
    {46, 47, 48, 49, 50, 51, 52, 53, 54}
};
map<string, int> Rstep, Bstep;
void adjustInfo() {
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 12; j++)
            rotateInfo[i][j]--;
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 9; j++)
            face[i][j]--;
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 9; j++)
            rotateFace[i][j]--;
}
int isCompleted(const char A[]) {
    for (int i = 0; i < 6; i++) {
        int ok = 1;
        for (int j = 0; j < 9; j++)
            ok &= A[face[i][j]] == A[face[i][0]];
        if (!ok)	return ok;
    }
    return 1;
}
string reduceCube(string u) {
    static int used[128] = {}, R[128], testcase = 0;
    char idx = 'A';
    testcase++;
    for (int i = 0; i < u.length(); i++) {
        if (used[u[i]] != testcase) {
            R[u[i]] = idx++, used[u[i]] = testcase;
        }
        u[i] = R[u[i]];
    }
    return u;
}
string rotateCube(string u, int kind, int dir) {
    static int a, b, c;
    static char tmp[9];
    if (dir == 0) {
        char v[3] = {u[rotateInfo[kind][0]], u[rotateInfo[kind][1]], u[rotateInfo[kind][2]]};
        for (int i = 0; i < 3; i++) {
            a = i * 3, b = i * 3 + 1, c = i * 3 + 2;
            u[rotateInfo[kind][a]] = u[rotateInfo[kind][a + 3]];
            u[rotateInfo[kind][b]] = u[rotateInfo[kind][b + 3]];
            u[rotateInfo[kind][c]] = u[rotateInfo[kind][c + 3]];
        }
        a = 3 * 3, b = 3 * 3 + 1, c = 3 * 3 + 2;
        u[rotateInfo[kind][a]] = v[0];
        u[rotateInfo[kind][b]] = v[1];
        u[rotateInfo[kind][c]] = v[2];
        if (kind < 6) {
            for (int i = 0; i < 9; i++)
                tmp[i] = u[rotateFace[kind][i]];
            for (int i = 0; i < 9; i++)
                u[rotateFace[kind][i]] = tmp[rotateOrder1[i]];
        }
    } else {
        char v[3] = {u[rotateInfo[kind][9]], u[rotateInfo[kind][10]], u[rotateInfo[kind][11]]};
        for (int i = 3; i > 0; i--) {
            a = i * 3, b = i * 3 + 1, c = i * 3 + 2;
            u[rotateInfo[kind][a]] = u[rotateInfo[kind][a - 3]];
            u[rotateInfo[kind][b]] = u[rotateInfo[kind][b - 3]];
            u[rotateInfo[kind][c]] = u[rotateInfo[kind][c - 3]];
        }
        a = 0, b = 1, c = 2;
        u[rotateInfo[kind][a]] = v[0];
        u[rotateInfo[kind][b]] = v[1];
        u[rotateInfo[kind][c]] = v[2];		
        if (kind < 6) {
            for (int i = 0; i < 9; i++)
                tmp[i] = u[rotateFace[kind][i]];
            for (int i = 0; i < 9; i++)
                u[rotateFace[kind][i]] = tmp[rotateOrder2[i]];
        }
    }
    return u;
}
int hfunction(string u) {
    static int used[128] = {}, testcase = 0, cnt = 0;
    int ret = 0;
    for (int i = 0; i < 6; i++) {
        testcase++, cnt = 0;
        for (int j = 0; j < 9; j++) {
            if (used[u[face[i][j]]] != testcase) {
                used[u[face[i][j]]] = testcase;
                cnt++;
            }
        }
        ret = max(ret, cnt - 1);
    }
    return ret;
}
void bfs(string A) {
    queue<string> Q;
    string u, v;
    Rstep.clear();
    A = reduceCube(A); 
    Q.push(A), Rstep[A] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = Rstep[u];
        if (step >= 4)	continue;
        for (int i = 0; i < 9; i++) {
            v = reduceCube(rotateCube(u, i, 0));
            if (Rstep.find(v) == Rstep.end()) {
                Rstep[v] = step + 1;
                Q.push(v);
            }
            v = reduceCube(rotateCube(u, i, 1));
            if (Rstep.find(v) == Rstep.end()) {
                Rstep[v] = step + 1;
                Q.push(v);
            }
        }
    }
//	printf("4 steps state %d\n", Rstep.size());
}
int bfs2(string A) {
    if (isCompleted(A.c_str()))
        return 0;
    queue<string> Q;
    string u, v;
    Bstep.clear();
    A = reduceCube(A); 
    Q.push(A), Bstep[A] = 0;
    int ret = 0x3f3f3f3f;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = Bstep[u];
        if (Rstep.find(u) != Rstep.end())
            ret = min(ret, step + Rstep[u]);
        if (step >= 3 || step + hfunction(u) >= min(7, ret))
            continue;
        for (int i = 0; i < 9; i++) {
            v = reduceCube(rotateCube(u, i, 0));
            if (Bstep.find(v) == Bstep.end()) {
                Bstep[v] = step + 1;
                Q.push(v);
            }
            v = reduceCube(rotateCube(u, i, 1));
            if (Bstep.find(v) == Bstep.end()) {
                Bstep[v] = step + 1;
                Q.push(v);
            }
        }
    }
    return ret <= 7 ? ret : -1;
}
int main() {
    adjustInfo();
    bfs("WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY");
    int testcase, cases = 0;
    char A[64];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", A);
        int ret = bfs2(A);
        
        printf("Case %d: ", ++cases);
        if (ret == -1)
            puts("Impossible");
        else
            printf("%d\n", ret);
    }
    return 0;
}
/*
      W W W                               1  2  3
      W W W                               4  5  6
      W W W                               7  8  9
R R R B B B O O O G G G         10 11 12 13 14 15 16 17 18 19 20 21
R R R B B B O O O G G G         22 23 24 25 26 27 28 29 30 31 32 33
R R R B B B O O O G G G         34 35 36 37 38 39 40 41 42 43 44 45
      Y Y Y                              46 47 48
      Y Y Y                              49 50 51
      Y Y Y                              52 53 54
4
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOGGGYYYYYYYYY
WWWWWWRRRRRYBBBWOOGGGRRYBBBWOOGGGRRYBBBWOOGGGOOOYYYYYY
WWBWWBWWBRRRBBYOOOWGGBBYOOOWGGRRRRRRBBYOOOWGGYYGYYGYYG
WWWWWWWWWRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYGGGYYYYYY
*/
Read More +
解題區/解題區 - UVa

UVa 12886 - The Big Painting

Problem

兩個 2D 模式找出現的次數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4 4 10 10
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo

Sample Output

1
4

Solution

做法來源：http://www.csie.ntnu.edu.tw/~u91029/StringMatching.html#5

演算法筆記－2D String Matching: Baker-Bird Algorithm

步驟 1.
把 T 橫切成一條一條，
把 P 橫切成一條一條，
然後每一條 T 都執行 Multi-Pattern String Matching，例如Aho-Corasick Algorithm。
如果第 a 條 P ，從 T[i,j] 開始出現，那麼就進行紀錄：M[i,j] = a。
M 是一個跟 T 一樣大的陣列。

步驟 2.
把M直切成一條一條，
每一條M都執行String Matching，例如Morris-Pratt Algorithm。
看看是否出現1234567…n這個字串（剛剛P共有n條）。

要點
當 P 有某兩條相同時，則要小心處理，把這兩條的編號設為相同。
AC 自動機不用跑匹配的後綴，因為必然是沒有的，所以在這裡的 AC 自動機寫法比較特別。

速度看起來挺慢的，也許 hash 或者是 FFT 某方面對於這種會稍微快一點？

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
// similar 11019 - Matrix Matcher 
#define MAXN 2048
char T[MAXN][MAXN], P[MAXN][MAXN];
int M[MAXN][MAXN];
//<AC automation>
struct Node {
    Node *next[26], *fail;
    int matched, label;
    Node() {
        fail = NULL;
        matched = -1;
        label = -1;
        memset(next, 0, sizeof(next));
    }
};
int insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx;
    p = root;
    for(i = 0; str[i]; i++) {
        idx = str[i]-'a';
        if(p->next[idx] == NULL)
            p->next[idx] = new Node();
        p = p->next[idx];
    }
    if(p->label == -1)
        p->label = label;
    return p->label;
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 26; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else
                nd->next[i]->fail = p->next[i];
        }
    }
}
void quertACautomaiton(const char* str, Node *root, int row) {
    static Node *p, *q;
    static int i, idx;
    p = root;
    for(i = 0; str[i]; i++) {
        idx = str[i]-'a';
        while(p != root && p->next[idx] == NULL)
            p = p->fail;
        p = p->next[idx];
        p = (p == NULL) ? root : p;
        q = p;
        M[row][i] = -1;
        if(q != root && q->label >= 0)
            M[row][i] = q->label;
    }
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 26; i++)
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        delete nd;
    }
}
//</AC automation>
int kmpTable[MAXN];
void KMPtable(int P[], int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPMatching(int T[], int P[], int tlen, int plen) {
    int i, j;
    int matchCnt = 0;
    for(i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1) {
            matchCnt++;
            j = kmpTable[j];
        }
    }
    return matchCnt;
}
int main() {
    int testcase;
    int n, m, x, y;
    int i, j, k;
    int pattern[MAXN], str[MAXN];
    while(scanf("%d %d", &x, &y) == 2) {
        scanf("%d %d", &n, &m);
    	Node *root = new Node();
        for(i = 0; i < x; i++) {
            scanf("%s", P[i]);
            pattern[i] = insertTrie(P[i], root, i);
        }
        for(i = 0; i < n; i++)
            scanf("%s", T[i]);
            
        buildACautomation(root);
        for(i = 0; i < n; i++)
            quertACautomaiton(T[i], root, i);
            
        /*for(i = 0; i < x; i++)
            printf("%d xx\n", pattern[i]);
        for(i = 0; i < n; i++, puts(""))
            for(j = 0; j < m; j++)
                printf("%3d ", M[i][j]);*/
        KMPtable(pattern, x);
        int ret = 0;
        for(i = 0; i < m; i++) {
            for(j = 0; j < n; j++)
                str[j] = M[j][i];
            ret += KMPMatching(str, pattern, n, x);
        }
        printf("%d\n", ret);
        freeTrie(root);
    }
    return 0;
}
/*
4 4 10 10
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo
*/
Read More +
解題區/解題區 - UVa

UVa 12881 - Ricochet Robots

Problem

一款神秘的團隊遊戲，機器人需要彼此合作，使得 1 號機器人恰好停留在 X 上面。盤面最多給定 4 個機器人。

每一個時刻，最多有一個機器人進行移動，此時會將其他機器人視為障礙物，每次選擇其中一個方向，並且要移動到碰到障礙物為止。

在有限步數內找到一個最小步數，如果找不到輸出無解。

Sample Input

1
2
3
4
5
6
7
8
9
10
2 5 4 10
.2...
...W.
WWW..
.X.1.
1 5 4 10
.....
...W.
WWW..
.X.1.

Sample Output

1
2
6
NO SOLUTION

Solution

把多個機器人的座標作為一個狀態。狀態紀錄時，除了 1 號機器人外，其他機器人的座標視為集合看待，適當地減少搜索狀態。

跟預期想的相同，全搜索不致於造成狀態總數過大。

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
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int N, W, H, L;
struct state {
    pair<int, int> xy[4];
    bool operator<(const state &a) const {
        for (int i = 0; i < N; i++)
            if (xy[i] != a.xy[i])
                return xy[i] < a.xy[i];
        return false;
    }
    void normal() {
        sort(xy + 1, xy + N);
    }
};
char g[16][16];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int isValid(int x, int y) {
    return x >= 0 && y >= 0 && x < H && y < W;
}
int bfs(state init, int L) {
    state u, v;
    queue<state> Q;
    map<state, int> R;
    int x, y, tx, ty;
    int used[11][11] = {}, testcase = 0;
    init.normal();
    Q.push(init), R[init] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        int step = R[u];
        if (g[u.xy[0].first][u.xy[0].second] == 'X')
            return step;
        if (step > L)
            continue;
        testcase++;
        for (int i = 0; i < N; i++) {
            x = u.xy[i].first, y = u.xy[i].second;
            used[x][y] = testcase;
        }
        for (int i = 0; i < N; i++) {
            x = u.xy[i].first, y = u.xy[i].second;
            for (int j = 0; j < 4; j++) {
                tx = x, ty = y;
                while (isValid(tx + dx[j], ty + dy[j])) {
                    if (g[tx + dx[j]][ty + dy[j]] == 'W')
                        break;
                    if (used[tx + dx[j]][ty + dy[j]] == testcase)
                        break;
                    tx += dx[j], ty += dy[j];					
                }
                v = u, v.xy[i] = make_pair(tx, ty);
                v.normal();
                if (R.find(v) == R.end()) {
                    R[v] = step + 1;
                    Q.push(v);
                }
            }
        }
    }
    return 0x3f3f3f3f;
}
int main() {
    while (scanf("%d %d %d %d", &N, &W, &H, &L) == 4) {
        for (int i = 0; i < H; i++)
            scanf("%s", g[i]);
        
        state init;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (g[i][j] >= '1' && g[i][j] <= '9')
                    init.xy[g[i][j] - '1'] = make_pair(i, j);
            }
        }
        
        int ret = bfs(init, L);
        if (ret > L)
            puts("NO SOLUTION");
        else
            printf("%d\n", ret);
    }
    return 0;
}
/*
2 5 4 10
.2...
...W.
WWW..
.X.1.
1 5 4 10
.....
...W.
WWW..
.X.1.
*/
Read More +
解題區/解題區 - UVa

UVa 12870 - Fishing

Problem

有 N x M 個魚池，接著要進行釣魚，為了防止生態滅絕，必須要餵兩次魚才能釣一次魚。餵魚時必須嚴格往右下角餵，釣魚也必須依序嚴格往右下角餵。很特別的是，釣魚、餵魚不影響魚池內的數量 (WTF)。餵魚成本、釣魚獲益都等於該魚池的數量，可以選擇在同一個魚池餵魚或者是釣魚。

求最大獲益為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
2
4 4
1 1 1 4
1 3 1 1
1 1 2 1
1 1 1 1
3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output

1
2
2
0

Solution

兩個路徑獨立，分開計算最大獲益路徑，直接著手 dp，找左上到右下，挑數個進行釣魚和餵魚動作。

每一個位置多紀錄已經挑了多少個魚池動作，隨後窮舉到底要怎麼組合來得到最佳獲益。

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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 128
int dp[MAXN][MAXN][MAXN];
int dp2[MAXN][MAXN][MAXN];
int main() {
    int testcase;
    int n, m, A[128][128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &A[i][j]);
        int nm = min(n, m);
        int lenMAX[128] = {}, lenMIN[128] = {};
        for (int i = 0; i <= nm; i++) {
            lenMAX[i] = 0;
            lenMIN[i] = -0x3f3f3f3f;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k <= nm; k++) {
                    dp[i][j][k] = 0, dp2[i][j][k] = -0x3f3f3f3f;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j][1] = max(dp[i][j][1], A[i][j]);
                dp2[i][j][1] = max(dp2[i][j][1], -A[i][j]);
                for (int k = 1; k <= nm; k++) {
                    if (i > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i-1][j][k]);
                    }
                    if (j > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i][j-1][k]);
                    }
                    if (i > 0 && j > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1] + A[i][j]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i-1][j-1][k-1] - A[i][j]);
                    }
//                    printf("%d %d %d %d\n", i, j, k, dp2[i][j][k]);
                }
                for (int k = 1; k <= nm; k++)
                    lenMAX[k] = max(lenMAX[k], dp[i][j][k]), lenMIN[k] = max(lenMIN[k], dp2[i][j][k]);
            }
        }
        int ret = 0;
        for (int i = 2; i <= nm; i += 2) {
            ret = max(ret, lenMAX[i/2] + lenMIN[i]);
//            printf("%d %d %d\n", i, lenMAX[i/2], lenMIN[i]);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
 9999
 4 4
 1 1 1 4
 1 3 1 1
 1 1 2 1
 1 1 1 1
 3 5
 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1
 3 4
 0 0 1 0
 0 0 2 0
 0 1 0 0
 2 2
 0 1
 2 0
 2 3
 10 20 30
 30 4 50
 3 2
 10 20
 30 30
 4 50
 */
Read More +
解題區/解題區 - UVa

UVa 12866 - Combination

Problem

Total number of odd entries in first n rows of Pascal’s triangle.

對於巴斯卡三角形找奇數的個數。

Sample Input

1
2
3
4
2 3
10 20
100 200
0 0

Sample Output

1
2
6
70

Solution

下面是巴斯卡三角形 (組合數) 前 n 行為奇數的總個數。

0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, 57, 65, 81, 83, 87, 91, 99, 103, 111, 119, 135, 139, 147, 155, 171, 179, 195, 211, 243, 245, 249, 253, 261, 265, 273, 281, 297, 301, 309, 317, 333, 341, 357, 373, 405, 409, 417, 425, 441, 449, 465, 481, 513, 521

在 A006046 可以得到遞迴公式：

  • a(0) = 0
  • a(1) = 1
  • a(2k) = 3 * a(k), a(2k+1) = 2*a(k) + a(k+1)

但是在第三項中可以發現到有可能指數增加，由於會被拆分成兩項，所以這方法不太可行。

如果打印每一行的奇數個數出來，四四分組，會發現組合是以 2 的冪次增長的組合，而組合之間恰好是兩倍的關係。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1 2 2 4  ----------- sum 9
2 4 4 8  ----------- sum 27
--
2 4 4 8 
4 8 8 16 ----------- sum 81
-- prev x 2
2 4 4 8 
4 8 8 16 
4 8 8 16 
8 16 16 32 ----------- sum 273  
-- prev x 2
2 4 4 8 
4 8 8 16 
4 8 8 16 
8 16 16 32 
4 8 8 16 
8 16 16 32
...

觀察如上所述，遞推之。

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
#include <stdio.h> 
// https://oeis.org/A006046
// a(0) = 0, a(1) = 1, a(2k) = 3*a(k), a(2k+1) = 2*a(k) + a(k+1).
long long f(long long n) {
    if (n < 2)	return n;
    if (n&1) 
        return f(n/2) * 2 + f(n/2 + 1);
    else
        return f(n/2) * 3;
}
unsigned long long dp[50] = {};
unsigned long long g(long long n) {
    if (n == 0)	return 0;
    if (n == 1)	return 1;
    if (n == 2)	return 3;
    if (n == 3)	return 5;
    if (n == 4)	return 9;
    if (n == 5)	return 11;
    if (n == 6)	return 15;
    if (n == 7)	return 19;
    long long i, j;
    for (i = 1, j = 1; 8 * i < n; i <<= 1, j++);
//	printf("%lld %lld %lld %lld\n", j, n, i, n - 4 * i);
    return dp[j] + 2 * g(n - 4 * i);
}
int main() {
    dp[1] = 9, dp[2] = 27;
    for (int i = 3; i < 50; i++)
        dp[i] = dp[i - 1] * 3;
     
//	int C[105][105] = {}, totsum = 0;
//	C[0][0] = 1;
//	for (int i = 0; i < 100; i++) {
//		C[i][0] = 1;
//		int sum = 1;
//		for (int j = 1; j <= i; j++) {
//			C[i][j] = (C[i-1][j] + C[i-1][j-1])&1;
//			sum += C[i][j];
//		}
//		totsum += sum;
//		printf("%2d: %5d %5d\n", i, sum, totsum);
//	}
//	for (int i = 0; i < 50; i++) {
//		for (int j = 0; j <= i; j++)
//			printf("%d", C[i][j]);
//		puts("");
//	}
    long long L, R;
    while (scanf("%lld %lld", &L, &R) == 2) {
        if (L == 0 && R == 0)
            break;
//		printf("%lld %lld\n", f(R + 1), g(R + 1));
//		long long ret = f(R + 1) - f(L);
//		printf("%lld\n", ret);
        unsigned long long ret2 = g(R + 1) - g(L);
        printf("%llu\n", ret2);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12795 - Ecology

Problem

給 N x N 個 grid，每一格有權重，找到一個連通子圖，其大小恰好為 M，並且具有最大權重。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 6
31 12 7 1 14
23 98 3 87 1
5 31 8 2 99
12 3 42 17 88
120 2 7 5 7
4 8
1 1 1 1
9 9 9 1
9 1 9 1
9 9 9 1

Sample Output

1
2
377
72

Solution

Number of fixed polyominoes with n cells.

Number of fixed polyominoes with n cells. (Formerly M1639 N0641)
1, 2, 6, 19, 63, 216, 760, 2725, 9910, 36446, 135268, 505861, 1903890, 7204874, 27394666, 104592937, 400795844, 1540820542, 5940738676, 22964779660, 88983512783, 345532572678, 1344372335524, 5239988770268, 20457802016011, 79992676367108, 313224032098244, 1228088671826973

連通子圖 n = 10 也不過 36446，對於所有位置嘗試擺放，也不過 O(36446 * 50 * 50)，給 60 秒還跑不出來。

關於窮舉連通圖的部分，想像成生成樹，這棵樹必然要有 M 個節點，適時要在葉節點返回，然後在其他尚未長出來的地方繼續生長。根據尤拉路徑最多走 2M 步，窮舉 2M 步進行建造。

為了加快窮舉速度，將找到的 polyominoes 依據長寬儲存，窮舉時先 greedy 估算這個矩形內部能產出最好的 polyominoes 可能是多少，如果已經低於已知解就直接放棄。

只能說測資不隨機，有極端測資，照理來講不用建表的速度應該會稍微快了些。

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
#include <stdio.h> 
#include <vector>
#include <map>
#include <algorithm>
#include <set> 
#include <string.h>
#include <assert.h>
using namespace std;
int g[64][64], n, m;
int used[64][64];
pair<int, int> path[64], pre[64][64];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct Area {
    vector<pair<int, int> > V;
    bool operator<(const Area &a) const {
        for (int i = 0; i < V.size(); i++) 
            if (V[i] != a.V[i])	return V[i] < a.V[i];
        return false;
    }
    Area() {
        V.clear();
    }
};
// Number of fixed polyominoes with n cells. https://oeis.org/A001168
set<Area> shape[16][16][16];
void storeArea(Area a) {
    sort(a.V.begin(), a.V.end());
    int x, y, mx, my;
    x = a.V[0].first, y = a.V[0].second;
    mx = x, my = y;
    for (int i = 0; i < a.V.size(); i++) {
        x = min(x, a.V[i].first), y = min(y, a.V[i].second);
        mx = max(mx, a.V[i].first), my = max(my, a.V[i].second);
    }
    for (int i = 0; i < a.V.size(); i++)
        a.V[i].first -= x, a.V[i].second -= y;
    sort(a.V.begin(), a.V.end());
    shape[a.V.size()][mx - x][my - y].insert(a);
    assert(mx - x >= 0 && mx - x < 16 && my - y >= 0 && my - y < 16);
}
void dfs(int idx, int x, int y, int pick, int m) {
    if (pick == m) {
        Area t;
        for (int i = 0; i < pick; i++)
            t.V.push_back(path[i]);
        storeArea(t);
        return ;
    }
    if (idx >= 2 * m)
        return;
    vector< pair<int,int> > test;
    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i], 
            ty = y + dy[i];
        if (used[tx][ty])
            continue;
        pre[tx][ty] = make_pair(x, y);
        path[pick] = make_pair(tx, ty);
        used[tx][ty] = 1;
        dfs(idx+1, tx, ty, pick + 1, m);
        test.push_back(make_pair(tx, ty));
    }
    if (pre[x][y].first != -1) // stop on leaf
        dfs(idx+1, pre[x][y].first, pre[x][y].second, pick, m);
    for (int i = 0; i < test.size(); i++) {
        int tx = test[i].first,
            ty = test[i].second;
        used[tx][ty] = 0;
    }
}
int place(int x, int y, int n, const Area &a) {
    int ox = x, oy = y;
    int sum = 0;
    for (int i = 0; i < a.V.size(); i++) {
        x = ox + a.V[i].first;
        y = oy + a.V[i].second;
        if (x < 0 || y < 0 || x >= n || y >= n)	return 0;
        sum += g[x][y];
    }
    return sum;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j < 32; j++)
            for (int k = 0; k < 32; k++)
                pre[j][k] = make_pair(-1, -1);
        pre[11][11] = make_pair(-1, -1);
        path[0] = make_pair(11, 11);
        used[11][11] = 1;
        dfs(1, 11, 11, 1, i);
        used[11][11] = 0;
        int sum = 0;
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < i; k++)
                sum += shape[i][j][k].size();
        } 
//		printf("complete %d %d\n", i, sum);
    }
    while (scanf("%d %d", &n, &m) == 2) {
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &g[i][j]);
            }
        }
        
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int mx[16] = {}, mxx = 0, tmp;
                for (int p = 0; p < m && i + p <= n; p++) {
                    mxx = 0;
                    for (int q = 0; q < m && j + q <= n; q++) {
                        mx[q] = max(mx[q], g[i+p][j+q]);
                        mxx = max(mxx, mx[q]);
                        if (mxx * m <= ret)	continue;
                        vector<int> D;
                        for (int a = i; a <= i+p; a++)
                            for (int b = j; b <= j+q; b++) 
                                D.push_back(g[a][b]);
                        sort(D.begin(), D.end(), greater<int>());
                        tmp = 0;
                        for (int a = 0; a < m; a++)
                            tmp += D[a];
                        if (tmp <= ret)		continue;
                        for (set<Area>::iterator it = shape[m][p][q].begin(); 
                            it != shape[m][p][q].end(); it++) {
                            ret = max(ret, place(i, j, n, *it));
                        }
                    }
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
5 6
31 12 7 1 14
23 98 3 87 1
5 31 8 2 99
12 3 42 17 88
120 2 7 5 7
4 8
1 1 1 1
9 9 9 1
9 1 9 1
9 9 9 1
3 5
0 5 0
5 5 5
0 5 0
10 5
733 950 26 696 512 570 327 531 829 600 
499 459 728 877 673 464 368 438 566 599 
512 631 242 499 919 931 688 602 490 172 
587 745 704 453 475 370 47 439 705 844 
133 449 264 732 361 612 196 635 739 853 
944 872 938 228 74 296 604 677 801 27 
763 628 650 40 558 159 7 500 405 423 
450 455 26 543 881 87 292 431 74 546 
349 115 568 589 390 40 606 802 434 479 
732 890 361 334 208 439 118 18 494 894 
*/
Read More +
解題區/解題區 - UVa

UVa 12761 - Blue Chips

Problem

N 個人圍繞一圈，每一個回合自身的分數為相鄰距離小於 D (不包含自己) 的權重總和 mod N。

請問在 K 個回合後，最大分數和擁有最大分數的人分別為何？

Sample Input

1
2
3
1
3 3 1
1 2 2

Sample Output

1
2
1
2 3

Solution

由於 K 很大，明顯地是一道矩陣 D&C。

把遞迴公式建造出來，可以在 O(N^3 log K) 時間內完成。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int mod = 10000;
struct Matrix {
    int v[64][64];
    int row, col; // row x col
    Matrix(int n, int m, int a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++) {
            for(int k = 0; k < col; k++) {
                if (v[i][k])
                    for(int j = 0; j < x.col; j++) {
                        ret.v[i][j] += v[i][k] * x.v[k][j],
                        ret.v[i][j] %= mod;
                    }
            }
        }
        return ret;
    }
    Matrix operator+(const Matrix& x) const {
        Matrix ret(row, col);
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                ret.v[i][j] = v[i][j] + x.v[i][j];
            }
        }
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
    Matrix powsum(int k) {
        if (k == 0) return Matrix(row, col, 0);
        Matrix vv = powsum(k/2);
        if (k&1) {
            return vv * (Matrix(row, col, 1) + vv) + vv;
        } else {
            return vv * (Matrix(row, col, 1) + vv);
        }
    }
};
int main() {	
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout); 
    int testcase, N, K, D;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &K, &D);
        mod = N;
        Matrix m(N, N), a(N, 1);
        for (int i = 0; i < N; i++)
            scanf("%d", &a.v[i][0]), a.v[i][0] %= N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if ((abs(i - j) <= D || N - abs(i - j) <= D) && i != j)
                    m.v[i][j] = 1;
            }
        }
        Matrix ret = (m ^ K);
        ret = ret * a;
        int mn = 0x3f3f3f3f;
        for (int i = 0; i < N; i++) {
            mn = min(mn, ret.v[i][0]);
        }
        printf("%d\n", mn);
        int f = 0;
        for (int i = 0; i < N; i++) {
            if (ret.v[i][0] == mn) {
                if (f)  putchar(' ');
                f = 1;
                printf("%d", i + 1);
            }
        }
        puts("");
    }
    return 0;
}
/*
 1
 3 3 1
 1 2 2
 */
Read More +
解題區/解題區 - UVa

UVa 12637 - 30 Minutes or Less

Problem

現在有 R 個 Pizza 店，同一個時間接收到 N 筆訂單，每一個店負責處理一筆訂單，發送的成本為店家到訂單的曼哈頓距離。

求所有訂單送達的總時間最小值為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2 2
1 5
2 1
4 2
4 3
3 2
2 1
4 3
7 4
4 5
5 -1

Sample Output

1
2
8
7

Solution

一開始以為是要求最後一個送達的時間最小化，二分下去才發現連範測都過不了。

建圖之後，用 KM 算法找最大帶權匹配 (費用最小就取負號)，用最少費用流解也是可以。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
#include <map>
#include <vector>
using namespace std;
struct KM {
    int W[105][105], N;
    int mx[105], my[105]; // match arr
    int lx[105], ly[105]; // label arr
    int x[105], y[105]; // used arr
    int hungary(int nd) {
        int i;
        x[nd] = 1;
        for(i = 0; i < N; i++) {
            if(y[i] == 0 && W[nd][i] == lx[nd]+ly[i]) {
                y[i] = 1;
                if(my[i] == -1 || hungary(my[i])) {
                    my[i] = nd;
                    return 1;
                }
            }
        }
        return 0;
    }
    int run() {
        int i, j, k, d;
        memset(mx, -1, sizeof(mx));
        memset(my, -1, sizeof(my));
        for (int i = 0; i < N; i++)
        	lx[i] = -0x3f3f3f3f, ly[i] = 0;
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                lx[i] = lx[i] > W[i][j] ? lx[i] : W[i][j];
        for(i = 0; i < N; i++) {
            while(1) {
                memset(x, 0, sizeof(x));
                memset(y, 0, sizeof(y));
                if(hungary(i))  break;
                d = 0x3f3f3f3f;
                for(j = 0; j < N; j++) {
                    if(x[j]) {
                        for(k = 0; k < N; k++)
                            if(!y[k])
                            d = d < lx[j]+ly[k]-W[j][k] ?
                                d : lx[j]+ly[k]-W[j][k];
                    }
                }
                if(d == 0x3f3f3f3f)  break;
                for(j = 0; j < N; j++) {
                    if(x[j])    lx[j] -= d;
                    if(y[j])    ly[j] += d;
                }
            }
        }
        int res = 0;
        for(i = 0; i < N; i++) {
            if(my[i] != -1)
                res += W[my[i]][i];
        }
        return res;
    }
} km;
int dist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
    int N, R;
    int x[256], y[256], cost[128][128];
    while (scanf("%d %d", &R, &N) == 2) {
        for (int i = 0; i < R; i++)
            scanf("%d %d", &x[i], &y[i]);
        for (int i = 0; i < N; i++)
            scanf("%d %d", &x[i+R], &y[i+R]);
        
        km.N = R;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < N; j++) {
                cost[i][j] = dist(x[i], y[i], x[j+R], y[j+R]);
                km.W[i][j] = -cost[i][j];
            }
            for (int j = N; j < R; j++)
                km.W[i][j] = 0;
        }
        int ret = km.run();
        printf("%d\n", -ret);
    }
    return 0;
} 
/*
2 2
1 5
2 1
4 2
4 3
3 2
2 1
4 3
7 4
4 5
5 -1
*/
Read More +
解題區/解題區 - UVa

UVa 12890 - Easy Peasy

Problem

給一串整數序列，請問有多少連續的區間，區間不包含重複的數字。

Sample Input

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

Sample Output

1
2
5
12

Solution

窮舉每一個點當作區間左端點，向左延伸的最遠的右端點必然非遞減。

掃描線計算右端點。效率 O(n log n)。

掛上輸入優化、HASH 會來得更快。

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
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int testcase, n, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        map<int, int> R;
        int low = 0;
        long long ret = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            int &y = R[x];
            if (y > low)	low = y;
            y = i;
            ret += i - low;
//			printf("[%d %d]\n", low + 1, i);
        }
        printf("%lld\n", ret);
    }
    return 0;
}
/*
9
3
1 2 1
5
1 2 3 1 2
4
1 2 2 1
*/
Read More +