解題區/解題區 - UVa

UVa 12769 - Kool Konstructions

Problem

有一長度為 n 的都市地帶，每一次將會做區段的都市更新，將建築物都增加高度 v。

操作

  • B X Y V ： 將區間 [X, Y] 都增加 V 高度
  • Q X ： 詢問當前位置 X 的建築物高度為何

(題目中的圖示貌似有錯誤)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
0

Sample Output

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

Solution

想要區間更新、單點查詢，有兩種方案 segment tree 附加懶操作、或者 binary indexed tree、最後是塊狀鏈表這幾種方式。這裡使用 binary indexed tree。雖然 binary indexed tree 原本的操作是單點修改，前綴總和查找。利用這一點完成區間修改的操作。

由於這一題還是單純的加法，那麼符合加法原則，當區間修改 B X Y V 時，相當於修改單點 Arr[X] += V，Arr[Y+1] -= V，從前綴和 SUM[1...Z] = \sum Arr[i]來看，保證只有區間 [X, Y] 的詢問增加了 V 值，其他保持不變。

單筆操作都是 O(log 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
#include <stdio.h> 
#include <string.h> 
#define MAXN 100000
int BIT[MAXN + 5];
void modify(int x, int val, int L) {
    while (x <= L) {
        BIT[x] += val;
        x += x&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int n, a, b, y;
    char cmd[8];
    while (scanf("%d", &n) == 1 && n) {
        memset(BIT, 0, sizeof(BIT));
        for (int i = 0; i < n; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'B') {
                scanf("%d %d %d", &a, &b, &y);
                modify(a, y, MAXN);
                modify(b + 1, -y, MAXN);
            } else {
                scanf("%d", &a);
                int ret = query(a);
                printf("%d\n", ret);
            }
        }
    }
    return 0;
}
/*
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
9
B 5 5 2
B 8 8 2
B 10 13 1
Q 8
B 8 13 1
Q 8
B 15 16 1
B 2 10 1
Q 8
0
*/
Read More +
解題區/解題區 - UVa

UVa 745 - Numeric Puzzles Again

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
23
24
7
6
3333
33
3333
 33
 33
7  7
7  7
7777
88888
 6
666
 66
  22
222
  2
  5
 55
 55
555
5 5
#
0

Sample Output

1
2
3
4
5
6
7
8777333
8733333
8733323
8777323
8655222
6665552
6655555

Solution

轉換成精準覆蓋問題，套用 DLX 做法來完成。

特別小心輸出的表示法，計算權重時，有可能會有嚴重的 overflow，可以用大數比大小、或者 double 來完成。

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
224
225
226
227
228
229
230
231
232
233
234
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
char pattern[32][4][32][32]; // [id][rotate][x][y]
char prob_out[4][32][32], out[32][32];
int n, m;
int mx[30];
void out_update() {
    int mxrt = -1;
    for (int rt = 1; rt < 4; rt++) {
        for (int p = 0; p < n; p++) {
            for (int q = 0; q < n; q++) {
                prob_out[rt][p][q] = prob_out[rt-1][q][n - 1 - p];
            }
        }
    }
    for (int rt = 0; rt < 4; rt++) {
        int sum[30] = {};
        for (int p = 0; p < n; p++) {
            for (int q = 0; q < n; q++)
                sum[q] += prob_out[rt][p][n - q - 1] - '0';
        }
        for (int p = 0; p < 29; p++)
            sum[p+1] += sum[p]/10, sum[p] %= 10;
        int flag = 0;
        for (int p = 29; p >= 0; p--) {
            if (sum[p] != mx[p]) {
                flag = sum[p] > mx[p] ? 1 : -1;
                break;
            }
        }
        if (flag == 1) {
            for (int p = 29; p >= 0; p--)
                mx[p] = sum[p];
            mxrt = rt;
        }
    }
    if (mxrt >= 0) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) 
                out[i][j] = prob_out[mxrt][i][j];
    }
}
class DLX {
    public:
    struct DancingLinks {
        int left, right, up, down, ch;
        int id, rotate, px, py; // extra data
    } DL[131072 + 256];
    int s[512], o[512], head, size;		
    void remove(int c) {
        DL[DL[c].right].left = DL[c].left;
        DL[DL[c].left].right = DL[c].right;
        int i, j;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            for(j = DL[i].right; j != i; j = DL[j].right) {
                DL[DL[j].down].up = DL[j].up;
                DL[DL[j].up].down = DL[j].down;
                s[DL[j].ch]--;
            }
        }
    }
    void resume(int c) {
        int i, j;
        for(i = DL[c].down; i != c; i = DL[i].down) {
            for(j = DL[i].left; j != i; j = DL[j].left) {
                DL[DL[j].down].up = j;
                DL[DL[j].up].down = j;
                s[DL[j].ch]++;
            }
        }
        DL[DL[c].right].left = c;
        DL[DL[c].left].right = c;
    }
    int found;
    void print(int dep) {
        for (int i = 0; i < dep; i++) {
            int id = DL[o[i]].id, rt = DL[o[i]].rotate;
            int px = DL[o[i]].px, py = DL[o[i]].py;
            for (int p = 0; p < n; p++) {
                for (int q = 0; q < n; q++) {
                    if (pattern[id][rt][p][q] != ' ')
                        prob_out[0][px + p][py + q] = pattern[id][rt][p][q];
                }
            }
        }
        out_update();
    }
    void dfs(int dep) {
        if (found) return;
        if (DL[head].right == head) {
        	print(dep);
            found++;
            return;
        }
        int tmp = 0x3f3f3f3f, c, i, j;
        for(i = DL[head].right; i != head; i = DL[i].right)
            if(s[i] < tmp)
                tmp = s[i], c = i;
        remove(c);
        for(i = DL[c].down; i != c; i = DL[i].down) {
            o[dep] = i;
            for(j = DL[i].right; j != i; j = DL[j].right)
                remove(DL[j].ch);
            dfs(dep+1);
            for(j = DL[i].left; j != i; j = DL[j].left)
                resume(DL[j].ch);
        }
        resume(c);
    }
    int getnode(int u, int d, int l, int r) {
        DL[size].up = u, DL[size].down = d;
        DL[size].left = l, DL[size].right = r;
        DL[u].down = DL[d].up = DL[l].right = DL[r].left = size;
        assert(size < 131072);
        return size++;
    }
    void newrow(int r[], int rn, int id, int rotate, int px, int py) {
        int i, j, h;
        for(i = 0; i < rn; i++) {
            DL[size].ch = r[i], s[r[i]]++;
            DL[size].id = id; // extra data
            DL[size].rotate = rotate; // extra data
            DL[size].px = px; // extra data
            DL[size].py = py; // extra data
            if(i) {
                j = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, DL[h].left, h);
            } else {
                h = getnode(DL[DL[r[i]].ch].up, DL[r[i]].ch, size, size);
            }
        }
    }
    void init(int c) {// total column
        size = 0;
        head = getnode(0,0,0,0);
        int i;
        for(i = 1; i <= c; i++) {
            getnode(i, i, DL[head].left, head);
            DL[i].ch = i, s[i] = 0;
        }
    }
} DLX;
int validPos(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n; 
}
char in[32767][128];
int main() {
    while (scanf("%d %d", &n, &m) == 2 && n) {
        while (getchar() != '\n');
        DLX.init(n * n + m);
        
        int t = 0;
        while (gets(in[t]) && in[t][0] != '#') {
            t++;
        }
        memset(pattern, ' ', sizeof(pattern));
        
        int test = 0;
        for (int i = 0, idx = 0; i < m; i++) {
            int r = 0, c = 0;
            char label = -1;
            for (int j = 0; in[idx][j]; j++)
                if (in[idx][j] >= '0' && in[idx][j] <= '9')
                    label = in[idx][j];
                    
            for (r = 0; ; r++) {
                int ok = 0;
                for (int j = 0; in[idx][j]; j++)
                    if (in[idx][j] == label)
                        ok = 1;
                if (ok == 0)	break;
                for (int j = 0; in[idx][j]; j++) {
                    if (in[idx][j] == label) {
                        pattern[i][0][r][j] = in[idx][j];
                        c = max(c, j + 1);
                        test++;
                    }
                }
                idx++;
            }
            r = c = max(r, c);
            assert(r <= n && c <= n && r > 0);
            for (int rt = 1; rt < 4; rt++) {
                for (int p = 0; p < r; p++) {
                    for (int q = 0; q < c; q++) {
                        pattern[i][rt][p][q] = pattern[i][rt-1][q][r - 1 - p];
                    }
                }
            }
            for (int rt = 0; rt < 1; rt++) {
                for (int p = -20; p <= n; p++) { 
                    for (int q = -20; q <= n; q++) { // top-left corner
                        int ok = 1, row[512], rn = 0;
                        for (int p1 = 0; p1 < r && ok; p1++) {
                            for (int q1 = 0; q1 < c && ok; q1++) {
                                if (pattern[i][rt][p1][q1] != ' ') {
                                    ok &= validPos(p1 + p, q1 + q);
                                    row[rn++] = (p1 + p) * n + (q1 + q) + 1;
                                }
                            }
                        }
                        if (ok) {
                            row[rn++] = n * n + i + 1;
                            DLX.newrow(row, rn, i, rt, p, q);
                        }
                    }
                }	
            }
//			for (int kind = 0; kind < 4; kind++) {
//				for (int p = 0; p < r; p++, puts("")) {
//					for (int q = 0; q < c; q++)
//						printf("%c", pattern[i][kind][p][q]);
//				}
//				puts("---");
//			}
        }
        memset(mx, 0, sizeof(mx));
        DLX.found = 0;
        DLX.dfs(0);
        assert(DLX.found && test == n*n);
        if (DLX.found) {
            for (int i = 0; i < n; i++, puts("")) {
                for (int j = 0; j < n; j++) {
                    putchar(out[i][j]);
                    assert(out[i][j] != ' ');
                }
            }
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 738 - A Logical Problem

Problem

給予 AND, OR, NOT 結合的電路圖，保證最多 26 個變數，分別由大寫字母表示，接著對於每一組詢問輸出電路結果。

Sample Input

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
A-:\
  : )-?
B-:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
  +-A
  |
  +-:\
    : >o-:\
  +-:/   : )-?
  |+----o:/
B-+|
 C-+
*
00000000000000000000000000
11100000000000000000000000
*
A-:\
  : )-?
A-:/
*
00000000000000000000000000
10000000000000000000000000
*

Sample Output

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

Solution

不想轉化成 graph，那麼就直接針對盤面做遞迴分析，特別要記錄之前的方向位置，以免電路接錯路徑。而題目沒有說明 ? 銜接的方向，有可能四個方向都有。一開始沒有注意到這個問題，導致刷了很多 RE。

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
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <assert.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 512
char g[MAXN][MAXN], val[MAXN];
int n;
int validPos(int x, int y) {
    return x >= 0 && x < MAXN && y >= 0 && y < MAXN;
}
int query(int x, int y, int dir, char pre) {
    if (g[x][y] == '?')
        return query(x, y - 1, 2, '?');
    if (g[x][y] >= 'A' && g[x][y] <= 'Z')
        return val[g[x][y] - 'A'] - '0';
    if (g[x][y] == 'o')
        return !query(x, y - 1, 2, 'o');
    if (g[x][y] == ')')
        return query(x - 1, y - 3, 2, ')') && query(x + 1, y - 3, 2, ')');
    if (g[x][y] == '>')
        return query(x - 1, y - 3, 2, '>') || query(x + 1, y - 3, 2, '>');
    if (g[x][y] == '-') {
        if (dir == 2)
            return query(x, y - 1, 2, '-');
        if (dir == 3)
            return query(x, y + 1, 3, '-');
        assert(false);
    }
    if (g[x][y] == '|') {
        if (dir == 0)
            return query(x - 1, y, 0, '|');
        if (dir == 1)
            return query(x + 1, y, 1, '|');
        assert(false);
    }
    if (g[x][y] == '+') {
        if (dir != 1 && validPos(x-1, y) && g[x-1][y] == '|')
            return query(x - 1, y, 0, '|');
        if (dir != 0 && validPos(x+1, y) && g[x+1][y] == '|')
            return query(x + 1, y, 1, '|');
        if (dir != 3 && validPos(x, y-1) && g[x][y-1] == '-')
            return query(x, y - 1, 2, '-');
        if (dir != 2 && validPos(x, y+1) && g[x][y+1] == '-')
            return query(x, y + 1, 3, '-');
        assert(false);
    }
    assert(g[x][y] == ' ' && pre != '?');
    return 0;
}
int main() {
    memset(g, ' ', sizeof(g));
    while (gets(g[0])) {
        int qx = -1, qy = -1;
        for (n = 1; gets(g[n]) && g[n][0] != '*'; n++);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < MAXN; j++) {
                if (g[i][j] == '?') {
                    qx = i, qy = j;
                }
            }
        }
        
        int dir = -1;
        if (validPos(qx-1, qy) && g[qx-1][qy] == '|')
        	qx--, dir = 0;
        else if (validPos(qx+1, qy) && g[qx+1][qy] == '|') 
        	qx++, dir = 1;
        else if (validPos(qx, qy-1) && g[qx][qy-1] == '-') 
        	qy--, dir = 2;
        else if (validPos(qx, qy+1) && g[qx][qy+1] == '-') 
        	qy++, dir = 3;
        assert(qx >= 0 && qy >= 0);
        while (scanf("%s", val) == 1 && val[0] != '*')
            printf("%d\n", query(qx, qy, dir, '?'));
        puts("");
        memset(g, ' ', sizeof(g));
        while (getchar() != '\n');
    }
    return 0;
}
/*
A-:\
  : )-?
B-:/
*
00000000000000000000000000
10000000000000000000000000
01000000000000000000000000
11000000000000000000000000
*
  +-A
  |
  +-:\
    : >o-:\
  +-:/   : )-?
  |+----o:/
B-+|
 C-+
*
00000000000000000000000000
11100000000000000000000000
*
A-:\
  : )-?
A-:/
*
00000000000000000000000000
10000000000000000000000000
*
A-o:\
   : )o-?
A-o:/
*
00000000000000000000000000
10000000000000000000000000
*
        ? 
A-o:\   | 
   : )o-+
A-o:/
*
00000000000000000000000000
10000000000000000000000000
*
 */
Read More +
解題區/解題區 - UVa

UVa 12905 - Volume of Revolution

Problem

給定一個方程式，接著繞 x 軸旋轉，計算區間 [l, r] 的體積。

考慮積分與數值積分的情況，計算兩者之間計算的誤差。其中會給定數值積分在 x 軸劃分的依準，以及繞行 x 軸轉換要切幾等分。

Sample Input

1
2
3
2
2 1 -4 5 1 4 4 3
1 1 0 1 4 4 3

Sample Output

1
2
Case 1: 27.9042
Case 2: 36.3380

Solution

這題最麻煩就是計算椎台體積

在幾何學中，錐台又稱平截頭體，指的是圓錐或稜錐被兩個平行平面所截後，位於兩個平行平面之間的立體。根據所截的是圓錐還是稜錐，可分為圓台與稜台。

參照 wiki Frustum

兩平行的上下底面積 S1, S2，根據高度 h，得到體積 V = (S1 + S2 + sqrt(S1 * S2)) /3 * h。之後就模擬劃分計算體積。

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>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
double P[32], Q[32];
const double pi = acos(-1);
#define eps 1e-6
void integral(double Q[]) {
    for (int i = 31; i >= 1; i--)
        Q[i] = Q[i-1] / (i);
    Q[0] = 0;
}
double calcVal(double Q[], double x) {
    double ret = 0;
    for (int i = 31; i >= 0; i--)
        ret = ret * x + Q[i];
    return ret;
}
int main() {
    int testcase, cases = 0;
    int n, slices, stacks;
    double a, b;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        memset(P, 0, sizeof(P));
        memset(Q, 0, sizeof(Q));
        for (int i = n; i >= 0; i--)
            scanf("%lf", &P[i]);
            
        scanf("%lf %lf", &a, &b);
        scanf("%d %d", &slices, &stacks);
        
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                Q[i+j] += P[i] * P[j];
        integral(Q);
        double trueVal = (calcVal(Q, b) - calcVal(Q, a)) * pi;
        double apprVal = 0;
        double dx = (b - a) / stacks, dtheta = 2 * pi / slices;
        for (double x = a; x + dx - eps <= b; x += dx) {
            double x1 = x, x2 = x + dx, x12;
            double fx1, fx2, S1, S2, fx12, S12;
            fx1 = calcVal(P, x1);
            fx2 = calcVal(P, x2);
            S1 = fx1 * fx1 * sin(dtheta) /2;
            S2 = fx2 * fx2 * sin(dtheta) /2;
            apprVal += dx * (S1 + S2 + sqrt(S1 * S2)) /3 * slices;
        }
        printf("Case %d: %.4lf\n", ++cases, fabs(trueVal - apprVal) * 100 / trueVal);
    }
    return 0;
}
/*
2
2 1 -4 5 1 4 4 3
1 1 0 1 4 4 3
*/
Read More +
解題區/解題區 - UVa

UVa 12904 - Load Balancing

Problem

給定一些學生的成績，希望建造一個分級制度，使得每一級的人數差距越少越好。

分級制度化分成 A, B, C, D 四級，每一級都是一個連續區間，假設現在有 N 個人，期望能將每一堆分成 N/4 個人，把每一堆人數與期望的 N/4 的差總和越小越好。

輸出字典順序最小的劃分方式。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
8
0
40
41
80
85
120
150
155
9
0
40
41
80
85
120
121
150
155

Sample Output

1
2
Case 1: 40 80 120
Case 2: 40 80 120

Solution

如何直接窮舉劃分線，想必也要消耗 O(160^3) 的時間。這花費太昂貴。

發現到每一個人的分數並不高，落在 0 - 160 之間的整數，那麼先統計每個分數有多少人。

接著考慮 dp[i][j] 前 i 個分級制度，劃分線為 j 的最小差總和。接著加入下一級，得到

1
dp[i+1][k+1] = min(dp[i+1][k+1], fabs(peopleCount[j, k] - avg) + dp[i][j]);

因此需要 O(4 * 160 * 160) 來完成。考慮輸出最小字典順序的劃分方式，一樣採用 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
91
92
93
94
95
96
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define MAXV 165
#define eps 1e-6
int main() {
    int testcase, n, x;
    int cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int A[MAXV] = {};
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            A[x]++;
        }
        for (int i = 1; i < MAXV; i++)
            A[i] += A[i-1];
        double dp[5][MAXV];
        int used[5][MAXV] = {};
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < MAXV; j++) {
                dp[i][j] = 1e+30;
            }
        }
        dp[0][0] = 0;
        double avg = n/4.0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < MAXV; j++) {
                if (dp[i][j] == 1e+30)
                    continue;
                for (int k = j; k < MAXV; k++) {
                    int cnt = A[k] - (j ? A[j-1] : 0);
                    dp[i+1][k+1] = min(dp[i+1][k+1], fabs(cnt - avg) + dp[i][j]);
                }
            }
        }
        used[4][MAXV - 1] = 1;
        for (int i = 3; i >= 0; i--) {
            for (int j = 0; j < MAXV; j++) {
                if (dp[i][j] == 1e+30)
                    continue;
                for (int k = j; k < MAXV; k++) {
                    int cnt = A[k] - (j ? A[j-1] : 0);
                    if (fabs(fabs(cnt - avg) + dp[i][j] - dp[i+1][k+1]) < eps)
                        used[i][j] |= used[i+1][k+1];
                }
            }
        }
        
        printf("Case %d:", ++cases);
        
        int pos = 0;
        for (int i = 0; i < 3; i++) {
            for (int k = pos; k < MAXV; k++) {
                int cnt = A[k] - (pos ? A[pos-1] : 0);
                if (fabs(fabs(cnt - avg) + dp[i][pos] - dp[i+1][k+1]) < eps && used[i+1][k+1]) {
                    printf(" %d", k);
                    pos = k+1;
                    break;
                }
            }
        }
        puts("");
    }
    return 0;
}
/*
2
8
0
40
41
80
85
120
150
155
9
0
40
41
80
85
120
121
150
155
Case 1: 40 80 120
Case 2: 40 80 120
*/
Read More +
解題區/解題區 - UVa

UVa 12897 - Decoding Baby Boos

Problem

每一個主字串，接著根據一大堆規則， 依序 將字母做替換。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A

Sample Output

1
2
ABBU_TUMI_CODING_PARO_NAH
CCCCBBY

Solution

由於主字串可能很長，不用針對每次詢問將每一個主字串都拿來修改。只需考量每一種字符轉換的可能，例如源頭 ‘A’ -> ‘Z’, ‘B’ -> ‘X’, ‘C’ -> ‘Z’, … 那麼，接下來遇到 ‘Z’ -> ‘W’，只需要針對 ‘A’ -> ‘W’, ‘C’ -> ‘W’ 即可。

因此，每一次詢問最多消耗 O(26) 完成。

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
#include <stdio.h> 
#include <string.h>
using namespace std;
char s[1048576];
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        scanf("%d", &n);
        
        char R[128], s1[10], s2[10];
        for (int i = 0; i < 128; i++)
            R[i] = i;
        for (int i = 0; i < n; i++) {
            scanf("%s %s", s1, s2);
            for (int j = 'A'; j <= 'Z'; j++)
                if (R[j] == s2[0])
                    R[j] = s1[0];
        }
        
        for (int i = 0; s[i]; i++)
            putchar(R[s[i]]);
        puts("");
    }
    return 0;
}
/*
2
AVVU_TUMI_COLING_PARO_NAY
3
B V
D L
H Y
AABBCCY
3
A B
B C
C A
*/
Read More +
解題區/解題區 - UVa

UVa 12874 - Blanket

Problem

寒冷的冬天，為街道上的人鋪設毛毯，現在有 n 個無限長毛毯，每一個毛毯都有其紋路，呈現厚薄厚薄厚薄 … 的順序，其中厚的長度為 ai，而薄的長度為 bi - ai。

現在長度為 1…m 的街道，請問蓋到 1 件、2 件、3 件、 …、n 件薄毛毯的人分別有多少人。

Sample Input

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

Sample Output

1
2
3
4
6
9
9
6

Solution

看到 ai, bi <= 16。

窮舉每個人，O(16) 計算蓋到幾件薄毛毯。

如果用 O(nm) 顯然太慢，由於 bi 很小，針對所有可能，預建表得到循環下累計結果。

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
#include <stdio.h> 
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int ret[131072];
int main() {
    int testcase, n, m;
//	scanf("%d", &testcase);
    ReadInt(&testcase);
    while (testcase--) {
//		scanf("%d %d", &n, &m);
        ReadInt(&n);
        ReadInt(&m);
        int A[20][20] = {}, a, b;
        for (int i = 0; i < n; i++) {
//			scanf("%d %d", &a, &b);
            ReadInt(&a);
            ReadInt(&b);
            A[b][a]++;
        }
        for (int i = 1; i <= 16; i++) {
            for (int j = 1; j <= 16; j++)
                A[i][j] += A[i][j-1];
        }
        for (int i = 0; i <= n; i++)
            ret[i] = 0;
        for (int i = 0; i < m; i++) {
            int cover = 0;
            for (int j = 1, t; j <= 16; j++) {
                t = i%j;
                cover += A[j][16] - A[j][t];
            }
            ret[cover]++;
        }
        for (int i = 0; i <= n; i++)
            printf("%d\n", ret[i]);
    }
    return 0;
}
/*
9999
3 30
2 5
3 5
3 6
2 15
1 2
3 4
*/
Read More +
解題區/解題區 - UVa

UVa 12846 - A Daisy Puzzle Game

Problem

有一套撥花瓣遊戲，一朵花有 n 片花瓣，每一片花瓣分別位置在 1…n，呈現環狀，首尾相連。兩個人輪流撥花瓣，每一次撥一片、或者撥相鄰的兩片，最後一個取走花瓣的人輸。

給已經撥去花瓣，請問現在她先手會不會勝利？

Sample Input

1
2
3
4
5
2
13 1
7
5 3
1 3 4

Sample Output

1
2
Case 1: yes
Case 2: no

Solution

看出是一道 SG 博奕遊戲，假設有 n 個連續花瓣，取中間一片、或連續兩片，將會變成兩段連續花瓣，藉此建造 SG 函數，求出連續 n 個連續花瓣的 SG 值，隨後統計有多少段連續花瓣，並且各自擁有多少花瓣，接著套用 nim 遊戲得到結果。

特別小心是環狀的，題目沒有描述得很清楚。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int SG[1024];
void buildSG() {
    int mex[1024] = {};
    SG[0] = 0;
    for (int i = 1; i < 50; i++) {
        memset(mex, 0, sizeof(mex));
        for (int j = 0; j < i; j++) {
            mex[SG[j] ^ SG[i-j-1]] = 1;
            if (i-j-2 >= 0)
                mex[SG[j] ^ SG[i-j-2]] = 1;
        }
        int sg = 0;
        for (sg; mex[sg]; sg++);
        SG[i] = sg;
    }
}
int main() {
    buildSG();
    int testcase, cases = 0, n, m, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        int used[64] = {}, last = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            x--;
            used[last = x] = 1;
        }
        
        vector<int> nim;
        for (int i = 0, tmp = 0, pos; i < n; i++) {
            pos = (last + i)%n;
            if (used[pos] == 0)
                tmp++;
            if (used[pos] || i == n-1) {
                if (tmp)
                    nim.push_back(tmp);
                tmp = 0;
            }
        }
        
        int ret = 0;
        for (int i = 0; i < nim.size(); i++)
            ret ^= SG[nim[i]];
        printf("Case %d: %s\n", ++cases, ret ? "yes" : "no");
    }
    return 0;
}
/*
9999
13 1
7
5 3
1 3 4
6 2
1 5
1 1
1
1 0
*/
Read More +
解題區/解題區 - UVa

UVa 12837 - Hasmot Ali Professor

Problem

給定一個主字串 S，接著數筆詢問有多少不同的子字串以 X 開頭、Y 結尾。

Sample Input

1
2
3
4
5
6
1
abab
3
a a
a b
ba ab

Sample Output

1
2
3
4
Case 1:
2
2
1

Solution

由於題目是要找不同的子字串，必然會造成比對速度上的問題，由於主子串長度最多 1000，而詢問的 X、Y 長度都小於 10，顯然地窮舉是相當有利。但是詢問次數最多 50000，窮舉起來必須有效率地映射到答案中，因此建議離線把詢問建成一個 Trie，同時避免重複的詢問。

窮舉每個子字串，為了加速匹配，最多跑 O(len * len * 10 * 10)，當決定子字串為 [l, r] 時，遞增起頭指針、遞減結尾指針，對於每一組詢問串成 X#inv(Y)，那麼只需要循序走訪一棵 trie，如此一來速度就提升了不少。

接著考慮如何去重複，關鍵點在於窮舉每個子字串，也依序插入 trie 中，當有新增新的節點時再進行答案的驗證。

也許這類型的題目可以先建造一個 suffix tree，然後想辦法詢問，仔細想想不容易就放棄。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct TrieNode {
    int n;
    int link[27];
} Node[1048576<<2];
int TrieSize;
int rename(char c) {
    if ('a' <= c && c <= 'z')
        return c - 'a';
    return 26;
}
void insertTrie(const char* str, int root) {
    static int i, idx, c;
    for(i = 0, idx = root; str[i]; i++) {
        c = rename(str[i]);
        if(Node[idx].link[c] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[c] = TrieSize;
        }
        idx = Node[idx].link[c];
    }
}
TrieNode* getTrieNode(const char* str, int root) {
    static int i, idx, c;
    for(i = 0, idx = root; str[i]; i++) {
        c = rename(str[i]);
        if(Node[idx].link[c] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[c] = TrieSize;
        }
        idx = Node[idx].link[c];
    }
    return &Node[idx];
}
const int MAXQL = 10 - 1;
const int MAXQ = 50000;
char ms[MAXQ][32];
int main() {
    int testcase, q, cases = 0;
    char s1[32], s2[32], s[1024];
    int A[1024], B[1024];
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%s", s);
        scanf("%d", &q);
        int sn = strlen(s), s1n, s2n, an, bn;
        TrieSize = 2;
        int root1 = 0, root2 = 1;
        memset(&Node[root1], 0, sizeof(Node[root1]));
        memset(&Node[root2], 0, sizeof(Node[root2]));
        for (int i = 0; i < q; i++) {
            scanf("%s %s", s1, s2);
            s1n = strlen(s1), s2n = strlen(s2);
            int m = 0;
            for (int j = 0; j < s1n; j++)
                ms[i][m++] = s1[j];
            ms[i][m++] = '#';
            for (int j = s2n - 1; j >= 0; j--)
                ms[i][m++] = s2[j];
            ms[i][m] = '\0';
            insertTrie(ms[i], root2);
        }
        
        for (int i = 0; i < sn; i++) {
            int idx = root1, idx2, c;
            for (int j = i; j < sn; j++) { // add s[l, r]
                c = rename(s[j]);
                if(Node[idx].link[c] == 0) {
                    TrieSize++;
                    memset(&Node[TrieSize], 0, sizeof(Node[0]));
                    Node[idx].link[c] = TrieSize;
                    // create new node == create distinct substring
                    int idx2 = root2;
                    int L = min(j, i + MAXQL);
                    for (int k = i; k <= L; k++) { // brute head
                        if (Node[idx2].link[rename(s[k])] == 0)	break;
                        idx2 = Node[idx2].link[rename(s[k])];
                        if (Node[idx2].link[rename('#')]) {
                            int idx3 = Node[idx2].link[rename('#')];
                            int R = max(i, j - MAXQL);
                            for (int l = j; l >= R; l--) { // brute tail
                                if (Node[idx3].link[rename(s[l])] == 0)	break;
                                idx3 = Node[idx3].link[rename(s[l])];
                                Node[idx3].n ++; // [l, r] = strA + ... + strB
                            }
                        }
                    }
                }
                idx = Node[idx].link[c];
            }
        }
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
            TrieNode *p = getTrieNode(ms[i], root2);
            printf("%d\n", p->n);
        }
    }
    return 0;
}
/*
1
abab
3
a a
a b
ba ab
*/
Read More +
解題區/解題區 - UVa

UVa 12875 - Concert Tour

Problem

現在有位歌手，要舉辦演唱會，在各地的百貨公司打算邀請歌手來演唱，藉以吸引更多的顧客來消費。每個百貨公司提供在哪一天歌手來演唱時可以得到的獲益，歌手必須自費從另一個地點到另一個地點，因此會給定兩地之間的自費費用。可以留在原地。

求歌手在 m 天內可以獲得的最大利益為何，假設第一天到任何場地都是 0 花費，沒有指派最後一天所在的位置。

Sample Input

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

Sample Output

1
2
3
170
60
65

Solution

定義狀態 dp[stores][days]，在第幾天到哪一個城鎮。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 128
#define MAXM 64
long long dp[MAXN][MAXM];
int profit[MAXN][MAXM], cost[MAXN][MAXN];
int main() {
    int testcase, n, m;
    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", &profit[i][j]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &cost[i][j]);
                
        memset(dp, 0, sizeof(dp));
        
        long long ret = 0;
        for (int i = 0; i < n; i++)
            dp[i][0] = profit[i][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    dp[k][i+1] = max(dp[k][i+1], dp[j][i] + profit[k][i+1] - cost[j][k]);
                }
            }
        }
        for (int i = 0; i < n; i++)
            ret = max(ret, dp[i][m-1]);
        printf("%lld\n", ret);
    }
    return 0;
}
Read More +