解題區/解題區 - 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 +
解題區/解題區 - UVa

UVa 12887 - The Soldier's Dilemma

Problem

N 個人不同高，現在佔一排，任挑三個人的身高從左向右的相對高度，不存在矮、高、中的情況有多少種。

Sample Input

1
2
3
2
2
3

Sample Output

1
2
2
5

Solution

卡塔蘭數 (Catalan number)。

每一次考慮加入一個最高的人，窮舉最高的人應該佔在哪個位置，則其左、右側也要滿足定義，同時左側的人都要比右側的人高。最後得到公式如下，與卡塔蘭數相同。

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
#include <stdio.h> 
/*
add tallest people in position i
ways[n] = \sum ways[i] * ways[n-i-1].
			   ^^^^^^[1] ^^^^^^^^^^[2]
[1] left tree pos[0, i-1]
[2] right tree pos[i+1, n-1]
then label of right tree must small than label of left tree
=> Catalan number, an = (4n-2)/(n+1) * an-1
*/
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra, lb -= n/m*rb;
        } else {
            ra -= n/m*la, rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    return i ? (la%mod+mod)%mod : (ra%mod+mod)%mod;
}
#define MAXN 5005
long long Catalan[MAXN];
const long long mod = 1000000007LL;
int main() {
    Catalan[0] = Catalan[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        Catalan[i] = Catalan[i-1] * (4 * i - 2) %mod;
        Catalan[i] = Catalan[i] * inv(i+1, mod) %mod;
    }
    int n, testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        printf("%lld\n", Catalan[n]);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12880 - Book Club

Problem

有 N 個人的愛書俱樂部，他們會喜歡某些人的書，如果相互喜歡對方的書就可以進行交換，現在要問的是否每個人都能找到能夠交換的對象，讓每個人都獲得新書。

如果 A -> B, B -> C, C -> A，那麼他們可以環狀地交換新書。

Sample Input

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

Sample Output

1
YES

Solution

每個人只能找一個對象進行交換，找二分圖的 perfect matching。

二分圖中左側是每個人，右側是想要交換的對象，兩邊的個數都是 N。匹配完會找到數個環狀，這就是最後的交換情況。然而由於點數很多，用匈牙利算法可以減枝來加快，每一次擴充路徑都必須得成功。如果使用 maxflow，則盡可能減少邊的無效使用。

當然可以使用 maxflow 貪心預流、匈牙利貪心匹配過後，再套用算法，速度有可能會快上許多，以下的模板還真好用，減少無效使用於分層圖，所以速度快上很多。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
int main() {
    int n, m, x, y;
    while (scanf("%d %d", &n, &m) == 2) {
        g.Init(2 * n + 2);
        int source = 2 * n, sink = 2 * n + 1;
        for (int i = 0; i < n; i++)
            g.Addedge(source, i, 1), g.Addedge(i + n, sink, 1);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g.Addedge(x, y + n, 1);
        }
        
        int matching = g.Maxflow(source, sink);
        puts(matching == n ? "YES" : "NO");
    }
    return 0;
}
/*
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
*/
Read More +