解題區►解題區 - UVa

UVa 10454 - Trexpression

Problem

給一個只有加法、乘法和括弧的運算式，在不改變最後的答案下，有多少種不同的運算順序 (不同的 parse tree)。

Input

1
2
3
4
1+2+3+4
(1+2)+(3+4)
1+2+3*4
1+2+(3*4)

Output

1
2
3
4
5
1
2
2

Solution

類似矩陣鏈乘積的 O(n^3) 解法。

dp[l, r] 表示表達式 exp[l, r] 正確的方法數。當運算式存在加法時，不能拆分乘法運算。只剩下乘法運算時，才能拆分乘法運算。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 256;
long long dp[MAXN][MAXN];
char s[MAXN];
long long dfs(int l, int r) {
	if (l == r)			return 1;
	if (dp[l][r] != -1)	return dp[l][r];
	long long &ret = dp[l][r];
	ret = 0;
	int left = 0, o1 = 0, o2 = 0;
	for (int i = l; i <= r; i++) {
		if (s[i] == '(')
			left++;
		else if (s[i] == ')')
			left--;
		else {
			if (left == 0) {
				if (s[i] == '+')	
					o1 = 1;
				if (s[i] == '*')
					o2 = 1;
			}				
		}
	}
	if (o1 == 0 && o2 == 0)
		ret += dfs(l+1, r-1);
	for (int i = l; i <= r; i++) {
		if (s[i] == '(')
			left++;
		else if (s[i] == ')')
			left--;
		else {
			if (left == 0) {
				if (s[i] == '+')
					ret += dfs(l, i-1) * dfs(i+1, r);
				if (s[i] == '*' && o1 == 0)
					ret += dfs(l, i-1) * dfs(i+1, r);
			}				
		}
	}
	return ret;
}
int main() {
	while (gets(s)) {
		memset(dp, -1, sizeof(dp));
		long long v = dfs(0, strlen(s) - 1);
		printf("%lld\n", v);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 10413 - Crazy Savages

Problem

瘋狂的島嶼上有 n 個野蠻人、m 個山洞，山洞呈現環狀分佈。

每個野蠻人一開始各自在自己的洞窟 Ci，每隔一天就會移動到下 Pi 個山洞，在島上待 Li 天後就會死亡。

兩個野蠻人若剛好移動到相同洞窟，則會發生爭吵，請問至少要幾個洞窟，才能不發生爭吵。

Input

1
2
3
4
5
6
7
8
9
10
11
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10

Output

1
2
6
33

Solution

窮舉洞窟數量 m，檢查是否存在爭吵。

檢查任兩個野蠻人 i, j 是否會在生存時間內相遇，假設會在第 k 天相遇，滿足公式

1
2
ci + k * pi = a * m  --- (1)
cj + k * pj = b * m  --- (2)

將公式整理後

1
2
3
(2)-(1) 	=> (ci - cj) + k * (pi - pj) = m * (a - b)
			=> (a - b) * m + k * (pj - pi) = ci - cj
check k in [0, min(L[i], L[j])] has a

檢查 k 最小為多少，使得等式解存在。

套用擴充歐幾里德算法，得到 ax + by = gcd(x, y) 的第一組解 (a, b)，其 a, b 的參數式為

1
2
3
4
5
g = gcd(x, y)
a = a + lcm(x, y)/x * k
b = b + lcm(x, y)/y * k
=> a = a + y / g * k
=> b = b + x / g * k

最小化 a 參數，滿足 a >= 0，隨後檢查可行解即可。

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
#include <stdio.h> 
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 32;
const int INF = 0x3f3f3f3f;
int C[MAXN], P[MAXN], L[MAXN];
// a x + by = g
void exgcd(int x, int y, int &g, int &a, int &b) {
	if (y == 0)
		g = x, a = 1, b = 0;
	else
		exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
int hasCollision(int m, int n) {
	// assume m caves arranged in a circle
	// ci + k * pi = a * m  --- (1)
	// cj + k * pj = b * m  --- (2)
	// (2)-(1) 	=> (ci - cj) + k * (pi - pj) = m * (a - b)
	//			=> (a - b) * m + k * (pj - pi) = ci - cj
	// check k in [0, min(L[i], L[j])] has a solution.
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			int x = P[j] - P[i], y = m, z = C[i] - C[j];
			int a, b, g;
			int limitR = min(L[i], L[j]), limitL = 0;
			exgcd(x, y, g, a, b);
		
			if (z%g)	continue;
			a = a * (z / g);
			// ax + by = z
			// a = a + lcm(x, y)/x * k, b = b + lcm(x, y)/y * k
			// a = a + y / g * k, b = b + x / g * k
			// minmum a, a >= 0
			if (g < 0)	g = -g;
			a = (a%(y/g) + y/g) % (y/g);
			if (a <= limitR)
				return true;
		}
	}
	return false;
}
int main() {
	int testcase, n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n);
		
		int m = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d %d %d", &C[i], &P[i], &L[i]);
			m = max(m, C[i]);
		}
			
		int ret = -1;
		for (int i = m; i < 99999999; i++) {
			
			if (!hasCollision(i, n)) {
				ret = i;
				break;
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}
/*
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10
*/
Read More +
解題區►解題區 - UVa

UVa 10412 - Big Big Trees

Problem

有隻猴子在樹間，每一棵樹有平行的分支，猴子可以在兩棵樹的分支端點跳躍，並且跳躍距離不超過歐幾里德距離 K，並且跳躍的時候只能跳端點的直線上，同時不能撞到其他分支，否則視如跳躍失敗。

猴子從樹幹走到分支端點、端點走到樹幹是需要計算步行花費，請問從第一棵樹走到最後一棵樹，最少的步行花費為何。

Input

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

Output

1
2
5
28

Solution

分支數量很少，直接暴力嘗試跳躍的可行性。使用外積解決線段交問題，隨後計算跳躍的最少花費，記錄狀態 dp[i] 表示從第一棵樹走到第 i 棵樹的最少步行成本。

特別小心當跳躍都無法時，可以走在地面上，由於這一點掛了好多 WA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <string.h>
#include <assert.h>
#include <vector>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
	}
    bool operator<(const Pt &a) const {
		if (fabs(x - a.x) > eps)
			return x < a.x;
		if (fabs(y - a.y) > eps)
			return y < a.y;
		return false;
	}
	double length() {
		return hypot(x, y);
	}
	void read() {
		scanf("%lf %lf", &x, &y);
	}
};
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
	Pt s, e;
	double angle;
	int label;
	Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
//		angle = atan2(e.y - s.y, e.x - s.x);
	}
	bool operator<(const Seg &other) const {
		if (fabs(angle - other.angle) > eps)
			return angle > other.angle;
		if (cross(other.s, other.e, s) > -eps)
			return true;
		return false;
	}
	bool operator!=(const Seg &other) const {
		return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
	}
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
	if (as == at && bs == bt)
		return as == bs;
	if (as == at)
		return onSeg(bs, bt, as);
	if (bs == bt)
		return onSeg(as, at, bs);
	if(cross(as, at, bs) * cross(as, at, bt) <= 0 &&
		cross(at, as, bs) * cross(at, as, bt) <= 0 &&
		cross(bs, bt, as) * cross(bs, bt, at) <= 0 &&
		cross(bt, bs, as) * cross(bt, bs, at) <= 0)
		return 1;
	return 0;
}
Pt getIntersect(Seg a, Seg b) {
	Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
	return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
	double x, y;
	x = a.x * cos(radian) - a.y * sin(radian);
	y = a.x * sin(radian) + a.y * cos(radian);
	return Pt(x, y);
}
const double pi = acos(-1);
int cmpZero(double v) {
	if (fabs(v) > eps) return v > 0 ? 1 : -1;
	return 0;
}
const int MAXN = 1024;
int HN[MAXN], H[MAXN][32];
int main() {
	int testcase, N, M, K;
	
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d %d", &N, &M, &K);
		for (int i = 0; i < N; i++) {
			scanf("%d", &HN[i]);
			for (int j = 0; j < HN[i]; j++)
				scanf("%d", &H[i][j]);
		}
		int dp[MAXN];
		
		memset(dp, 63, sizeof(dp));
		dp[0] = 0;
		
		for (int i = 0; i+1 < N; i++) {
//			printf("%d\n", dp[i]);
			for (int j = 0; j < HN[i]; j++) {
				for (int k = 0; k < HN[i+1]; k++) {
					int dx, dy;
					dx = M - H[i][j] - H[i+1][k];
					dy = abs(j - k);
					if (dx * dx + dy * dy > K * K)
						continue;	
//					printf("%d %d, %d %d\n", j, k, dx, dy);
					int ok = 1;
					for (int p = 0; p < HN[i]; p++) {
						if (p == j)	continue;
						if (intersection(Pt(H[i][j], j), Pt(M-H[i+1][k], k), Pt(0, p), Pt(H[i][p], p)))
							ok = 0;
					}
					for (int p = 0; p < HN[i+1]; p++) {
						if (p == k)	continue;
						if (intersection(Pt(H[i][j], j), Pt(M-H[i+1][k], k), Pt(M, p), Pt(M-H[i+1][p], p)))
							ok = 0;
					}
					if (ok) {
//						printf("--- %d %d %d\n", j, k, H[i][j], H[i+1][k]);
						dp[i+1] = min(dp[i+1], dp[i] + H[i][j] + H[i+1][k]);
					}
				}	
			}
			dp[i+1] = min(dp[i+1], dp[i] + M); // WTF !!!!!!!!!!!!!!! 
		}
		
		printf("%d\n", dp[N-1]);
	}
	return 0;
}
/*
1
5 10 12
1 2
3 2 1 4
8 2 4 4 1 4 0 0 0
8 1 1 2 0 4 1 3 3
10 1 4 0 1 1 1 1 2 1 4
999
5 10 3
2 0 2
1 1
10 1 2 0 1 2 2 0 4 4 4
9 3 1 2 1 2 1 4 1 3
8 0 1 2 1 3 1 0 0
2
2 7 3
4 3 2 2 0
5 3 0 1 0 0
3 50 40
4 15 3 16 10
8 12 12 12 21 12 15 6 14
13 15 23 20 18 14 1 21 9 9 18 23 10 4
999
3 5 100
3 0 0 1
2 0 0
3 0 0 1
2 7 5
1 3
4 3 3 2 1
2 10 2
1 4
2 0 4
2 10 4
1 4
2 0 4
2 10 2
2 0 4
2 0 4
*/
Read More +
解題區►解題區 - UVa

UVa 10351 - Cutting Diamonds

Problem

給一個橢球的三個參數，一刀縱切橢球，問切割橢球的截面積為何。

Input

1
2
7 6 4 8 6 4
4 8 8 8 8 8

Output

1
2
3
4
Set #1
8.246681
Set #2
50.265482

Solution

回顧積分公式，得到橢圓面積。將橢球固定一個參數，調整計算截面積。公式如代碼中所附。

$$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 \\ \text{area } = ab\pi \\ \frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} = 1 \\ \frac{x^2}{(a \sqrt{1 - z^2 / c^2})^2} + \frac{y^2}{(b \sqrt{1 - z^2 / c^2})^2} = 1 \\ \text{cross-sectional area} = ab (1 - z^2 / c^2) \pi \\$$ 
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
#include <stdio.h> 
#include <math.h>
using namespace std;
/*
	x^2 / a^2 + y^2 / b^2 = 1 
		area = ab pi
	
	x^2 / a^2 + y^2 / b^2 + z^2 / c^2 = 1
	
	x^2 / (a \sqrt{1 - z^2 / c^2})^2 + y^2 / (b \sqrt{1 - z^2 / c^2})^2 = 1;
	cross-sectional area = ab (1 - z^2 / c^2) pi
	
	volume 	ab (1 - z^2 / c^2) pi dz
			ab pi (z - z^3 / 3 / c^2), for z in [l, r]
*/
const double pi = acos(-1);
int main() {
	int a, b, c, ra, rb, rc;
	int cases = 0;
	while (scanf("%d %d %d %d %d %d", &ra, &rb, &rc, &a, &b, &c) == 6) {
		printf("Set #%d\n", ++cases);
		double ta, tb, tc, l, r;
		if (ra > a || rb > b || rc > c) {
			printf("%.6lf\n", 0.0); // WTF
			continue;
		}
		if (ra < a) {
			ta = b/2.0, tb = c/2.0, tc = a/2.0;
			r = a/2.0, l = r - fabs(a - ra);
		} else if (rb < b) {
			ta = a/2.0, tb = c/2.0, tc = b/2.0;
			r = b/2.0, l = r - fabs(b - rb);
		} else if (rc < c) {
			ta = a/2.0, tb = b/2.0, tc = c/2.0;
			r = c/2.0, l = r - fabs(c - rc);
		} else {
			printf("%.6lf\n", 0.0); // WTF
			continue;
		}
		double area;
		area = ta * tb * pi * (1 - l*l/tc/tc);
		printf("%.6lf\n", area);
	}
	return 0;
}
/*
7 6 4 8 6 4
4 8 8 8 8 8
2 6 4 8 6 4
8 6 4 8 6 4
*/
Read More +
解題區►解題區 - UVa

UVa 10280 - Old Wine Into New Bottles

Problem

給予 n 種酒瓶，每一種酒瓶有其裝酒的容積上下限 [min, max] 毫升，請問將 m 公升的酒裝入酒瓶，最後剩餘的最少量為多少。

每一種酒瓶可以無限使用。

Input

1
2
3
4
5
6
7
8
9
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750

Output

1
2
3
250
0

Solution

這一題需要剪枝，無法單純地運行背包 dp，單純的背包 dp 很容易造成 TLE。

發現到只考慮使用一種酒瓶，那麼當酒量大於某個定值後，保證都能裝完。假設使用單一酒瓶的數量為 k 個以上時，能裝出所有量，則能覆蓋的區間為

1
[min, max], ..., [k*min, k*max], [(k+1)*min, (k+1)*max]

當第 k+1 個區間的左端點小於第 k 個區間的右端點時，可以得到接下來的所有區間都會發生重疊。推導得到 (k+1)*min >= k*max 最後條件 k >= min / (max - min)。

滿足保證能裝出，直接輸出答案 0，否則做背包 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
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
/*
	k bottles
	[min, max], ..., [k*min, k*max], [(k+1)*min, (k+1)*max]
	
	always have solution for [k*min, k*max], [(k+1)*min, (k+1)*max] 
	sat. (k+1)*min >= k*max 
			k >= min / (max - min)
	all interval cover each other after k-bottles.
*/
const int MAXN = 128;
int mx[MAXN], mn[MAXN];
int main() {
	int testcase, L, N;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &L, &N);
		L *= 1000;
		
		int lower_full = 0x3f3f3f3f; 
		for (int i = 0; i < N; i++) {
			scanf("%d %d", &mn[i], &mx[i]);
			lower_full = min(lower_full, mn[i] * mn[i] / (mx[i] - mn[i]));
		}
		
		if (L >= lower_full) {
			puts("0");
			if (testcase)
				puts("");
			continue;
		}
		
		// limit L <= 4500 * 4500 / (4500 * 0.01)
		int A[4505] = {}, ret = 0;
		
		for (int i = 0; i < N; i++)
			for (int j = mn[i]; j <= mx[i]; j++)
				A[j] = 1;
			
		memset(mark, 0, sizeof(mark)); 
		SET(0);
		for (int i = 1; i <= 4500; i++) {
			if (A[i] == 0)
				continue;
			for (int j = i, k = 0; j <= L; j++, k++) {
				if (GET(k))
					SET(j), ret = max(ret, j);
			}
		}
		
		printf("%d\n", L - ret);
		if (testcase)
			puts("");
	}
	return 0;
}
/*
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750
*/
Read More +
解題區►解題區 - 其他題目

2015 Google Code Jam Round 1B

windows format to linux format 

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt

題解

  • A. Counter Culture
  • B. Noisy Neighbors
  • C. Hiking Deer

［A. Counter Culture］

給定一個數字 N，要求藉由兩種操作從 1 變成 N，第一種操作將當前數字 x 變成 x + 1，第二種操作為 x 變成 reverse(x)，並且消除前導為零。求操作的最少次數。

由於 N 很大，搜索沒有搞頭，但關於反轉數字能理解到，當後半部恰好等於目標的前半部時，此時反轉最有利，根據貪心策略進行反轉操作，但要防止前導為 0。關於 x + 1 部分，主要是增加位數。

這時候來逆推吧！降位數 (1000 -> 999, 10000 -> 9999)、反轉貪心 (123654 -> 100321)、WTF 的情況 (19 -> 11 -> 10)。在 WTF 的情況中，反轉無效，怒降一個數字。

［B. Noisy Neighbors］

在 R x C 的網格上，每一格可以租給一個用戶，當用戶之間共享一個邊時，將會增加不滿意程度，求租給 K 名用戶，建築的不滿意程度最低為何。

考慮 K 小的時候，將網格黑白染色，必然只放置在黑色或白色網格上，此時不滿意程度皆為 0。當 K 多餘白色格子或黑色格子時，將會增加不滿意程度，每當增加一格，勢必會挑選相對的顏色 (填滿白色格子後，選黑色格子來填)，那麼每一次必須挑最少相鄰邊的格子。

為什麼一定會填滿其中一種顏色？假設最優解存在其中一種顏色未填滿，且存在這一格 x 附近沒有使用的格子，那麼必然存在將一個產生不滿意的格子移動到 x 會是一個更優解。不斷地迭代下去，就是貪心的來源！

［C. Hiking Deer］

跟蹤狂 H 在一個圓從 0 出發繞一圈，H 很討厭人群，因此盡可能不與其他人碰面，H 的能力可以跟蹤在任何人身後。現在知道一群人會不斷地繞著這個圓，並且分別以各自的速度、當前位置，全部人都按著順時針方式繞行，不存在兩個人在相同地點以相同速度。現在從 time = 0 開始，請問 H 至少會發生幾次碰面。

由於是一個環狀，又要考慮繞行的區間最少人數，朝著掃描線思路邁進！保證答案 (碰面次數) 不超過總人數 N，一開始瞬間移動到最快抵達終點的人身上，只會碰到 N - 1 個人！

根據抵達終點的時間排序，維護當前需要的碰面次數 e，假設尾隨編號 i 的人，需要碰面 e 個人！經過掃描一些人後，又遇到 i，表示 i 又繞了一圈，那麼碰面次數 e = e + 1，讓尾隨後面的點時，都會遇到那該死的 i！

A code

GCJ20151B - Counter Culture
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>
long long reverseNumber(long long x) {
	static char buf[32];
	sprintf(buf, "%lld", x);
	
	long long y = 0;
	for (int i = strlen(buf) - 1; i >= 0; i--)
		y = y * 10 + buf[i] - '0';
	return y;
}
long long f(long long n) {
	if (n < 10)
		return n;
	long long half = 1;
	while (half * half <= n)	
		half *= 10;
	if (n % half == 0)	// 1000 -> 999, 10000 -> 9999
		return 1 + f(n - 1);
	else {				
		long long v = reverseNumber(n - n%half + 1);
		if (v != n - n%half + 1)	// 123654 -> 100321, subtract & reverse
			return n%half + f(v);
		else						// 19 -> 11, but 11 is palindrome, without reverse -> 10
			return n%half + f(v-1);
	}
}
int main() {
	int testcase, cases = 0;
	long long n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%lld", &n);
		printf("Case #%d: %lld\n", ++cases, f(n));
	}
	return 0;
}

B code

GCJ20151B - Noisy Neighbors
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
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
	int testcase, cases = 0;
	int N, M, K;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d %d", &N, &M, &K);
		
		vector<int> B, W;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int adj = 0;
				for (int k = 0; k < 4; k++) {
					int x = i + dx[k], y = j + dy[k];
					if (x >= 0 && y >= 0 && x < N && y < M)
						adj++;
				}
				if ((i+j) %2 == 0)
					B.push_back(adj), W.push_back(0);
				else
					B.push_back(0), W.push_back(adj);
			}
		}
		
		sort(B.begin(), B.end());
		sort(W.begin(), W.end());
		
		int cost1 = 0, cost2 = 0, ret = -1;
		for (int i = 0; i < K; i++) {
			cost1 += B[i];
			cost2 += W[i];
		}
		ret = min(cost1, cost2);
		printf("Case #%d: %d\n", ++cases, ret);
	}
	return 0;
}

C code

GCJ20151B - Hiking Deer
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
#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
const int MAXN = 524288;
int N, pass[MAXN];
struct Node {
	long long arrive_time, v;
	int id;
	Node(long long a = 0, int b = 0, long long c = 0):
		arrive_time(a), id(b), v(c) {}
	bool operator<(const Node &a) const {
		if (arrive_time != a.arrive_time)
			return arrive_time < a.arrive_time;
		return v < a.v;
	}
};
int main() {
	int testcase, cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &N);
		
		set<Node> pQ;
		int id = 0;
		long long D, H, M;
		for (int i = 0; i < N; i++) {
			scanf("%lld %lld %lld", &D, &H, &M);
			for (int j = 0; j < H; j++) {
				long long arrive_time = (360 - D) * (M + j);
				pQ.insert(Node(arrive_time, id, M + j));
				pass[id] = 0, id++;
			}
		}
		
		int ret = id, encounter = id;
		
		for (; encounter <= 2 * id; ) {
			Node u = *pQ.begin(); 			// extract minimum
			
			ret = min(ret, encounter);
			
			if (pass[u.id])
				encounter++;
			else
				encounter--;
			pass[u.id] = 1;
			
			pQ.erase(pQ.begin());
			pQ.insert(Node(u.arrive_time + u.v * 360, u.id, u.v));
		}
		
		printf("Case #%d: %d\n", ++cases, ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1502 - GRE Words

Problem

依序背單字，下一個單字中要出現當前單字為 substring 的情況，每一個單字都有各自的權重，求背一次能得到的最高權重總合為多少。

如範例輸入背的順序為 a -> ab -> abb -> abbab 答案為 1 + 2 + 3 + 8 = 14。

Sample Input

1
2
3
4
5
6
7
1
5
a 1
ab 2
abb 3
baba 5
abbab 8

Sample Output

1
Case #1: 14

Solution

這一題的測資有問題，輸入中出現非小寫字母，導致存取發生錯誤，部分程序沒有考慮這一點，居然就通過了？
一群人 Invalid Memory Access 通過，而我因寫法比較不同成了 RE 下亡魂，測試數據格式錯誤啊！坑爹啊，害我掛載好多 assert 抓哪裡溢出 …

原本想說是一道有趣的 AC 自動機複習，將 fail 指針 (suffix link) 整理成另一棵樹，對其 fail tree 壓樹 (走訪)，套上線段樹等數據結構，就能支持多字串匹配的數據查找。當匹配時將會一直攀爬 fail 指針，最後爬到 root，中間經過的節點都是匹配的字串，也因此單看 fail 指針，也肯定是 tree。

在走訪時，會匹配 fail link 上的所有節點 (都是其 suffix string)。dp[i] 表示使用第 i 個字串為背單字序列結尾的最大權重，則 dp[i] = max(dp[j]) + w，其中滿足 j < i 且 word[j] 是 word[i] 的 substring。

窮舉第 i 字符串的後綴匹配節點，找尋匹配節點藉由 fail link 到 root 上節點的最大值 (max(dp[j]))。

利用線段樹完成區間最大值更新、單點查詢 (找尋節點到 root 的最大值，更新一個點的權重時，相當於作區間最大值更新，藉由壓樹其子樹被表示成區間)。

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
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
// NOTES: has error test data, there are some characters which aren't lowercase letters.
// FUCK
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <assert.h>
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MAXCHAR = 26;
const int MAXNODE = 1048576;
class ACmachine {
public:
    struct Node {
        Node *next[MAXCHAR], *fail;
        int cnt, val, id, nid;
        void init() {
            fail = NULL;
            cnt = val = 0;
            nid = id = -1;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    vector<int> fg[MAXNODE];
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init(), p->nid = size-1;
        assert(size < MAXNODE);
        fg[p->nid].clear();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    int toIndex(char c) {
    	assert(c - 'a' >= 0 && c - 'a' < MAXCHAR);
        return c - 'a';
    }
    void dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt |= v->cnt;
                dfs(u, v);
            }
        }
    }
    void merge(const ACmachine &other) {
        dfs(root, other.root);
    }
    void insert(const char str[], int sid) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt = 1;
        if (sid >= 0)	p->id = sid;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    void build() { // AC automation    
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            if (u != root) {
            	assert(u->fail != NULL);
            	assert(u->nid != u->fail->nid);
            	fg[u->nid].push_back(u->fail->nid);
            	fg[u->fail->nid].push_back(u->nid);
            }
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] == NULL)
                    continue;
                Q.push(u->next[i]);
                p = u->fail;
                while (p != NULL && p->next[i] == NULL)
                    p = p->fail;
                if (p == NULL || p->next[i] == NULL)
                    u->next[i]->fail = root;
                else
                    u->next[i]->fail = p->next[i];
                u->next[i]->val = u->next[i]->fail->val + u->next[i]->cnt;
                u->next[i]->id = u->next[i]->fail->id | u->next[i]->id;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next[idx] == NULL && u != root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
};
const int MAXN = 1048576;
class SegmentTree {
public:
	struct Node {
		long long mx;
		pair<int, long long> label;
		void init() {
			mx = -1LL<<60;
			label = make_pair(0, 0);
		}
	} nodes[MAXN];
	void pushDown(int k, int l, int r) {
		int mid = (l + r)/2;
		if (nodes[k].label.first) {
			maxUpdate(k<<1, l, mid, nodes[k].label.second);
			maxUpdate(k<<1|1, mid+1, r, nodes[k].label.second);
			nodes[k].label = make_pair(0, 0); // cancel
		}
	}
	void pushUp(int k) {
		nodes[k].mx = max(nodes[k<<1].mx, nodes[k<<1|1].mx);
	}
	void build(int k, int l, int r) { 
		nodes[k].init();
		if (l == r) {
			nodes[k].mx = 0;
			return ;
		}
		int mid = (l + r)/2;
		build(k<<1, l, mid);
		build(k<<1|1, mid+1, r);
		pushUp(k);
	} 
	// operator, assign > add
	void maxUpdate(int k, int l, int r, long long val) {
		if (nodes[k].label.first)
			val = max(val, nodes[k].label.second);
		nodes[k].label = make_pair(1, val);
		nodes[k].mx = max(nodes[k].mx, val);
	}
	void assign(int k, int l, int r, int x, int y, int val) {
		if (x <= l && r <= y) {
			maxUpdate(k, l, r, val);
			return;
		}
		pushDown(k, l, r);
		int mid = (l + r)/2;
		if (x <= mid)
			assign(k<<1, l, mid, x, y, val);
		if (y > mid)
			assign(k<<1|1, mid+1, r, x, y, val);
		pushUp(k);
	}
	// query 
	long long r_mx;
	void qinit() {
		r_mx = -1LL<<60;
	}
	void query(int k, int l, int r, int x, int y) {
		if (x <= l && r <= y) {
			r_mx = max(r_mx, nodes[k].mx);
			return ;
		}
		pushDown(k, l, r);
		int mid = (l + r)/2;
		if (x <= mid)
			query(k<<1, l, mid, x, y);
		if (y > mid)
			query(k<<1|1, mid+1, r, x, y);
	}
};
ACmachine ac;
SegmentTree tree;
vector<string> words;
vector<int> wvals;
char s[1048576];
int bPos[MAXN], ePos[MAXN], inIdx;
void prepare(int u, int p) {
	bPos[u] = ++inIdx;
	for (int i = 0; i < ac.fg[u].size(); i++) {
		if (ac.fg[u][i] == p)	continue;
		prepare(ac.fg[u][i], u);
	}
	ePos[u] = inIdx;
} 
void solve() {
	for (int i = 0; i < ac.size; i++)
		bPos[i] = ePos[i] = 0;
	inIdx = 0;
	for (int i = 0; i < ac.size; i++) {
		if (bPos[i] == 0) {
			prepare(i, -1); // interval [1, inIdx]
		}
	}
			
	assert(inIdx < MAXN/2);
	tree.build(1, 1, inIdx);
	
	long long ret = 0;
	for (int i = 0; i < words.size(); i++) {
		ACmachine::Node *u = ac.root;
		int idx;
		long long dpval = 0;
		for (int j = 0; j < words[i].length(); j++) {
			idx = ac.toIndex(words[i][j]);
			while (u->next[idx] == NULL && u != ac.root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? ac.root : u;
            
            tree.qinit();
            tree.query(1, 1, inIdx, bPos[u->nid], bPos[u->nid]);
            dpval = max(dpval, tree.r_mx);
		}
		dpval += wvals[i];
		tree.assign(1, 1, inIdx, bPos[u->nid], ePos[u->nid], dpval);
		ret = max(ret, dpval);
	}
	printf("%lld\n", ret);
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int testcase, cases = 0;
	int N, val;
	scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d", &N);
    	    	
       	ac.init();
       	words.clear(), wvals.clear();
       	for (int i = 0; i < N; i++) {
       		scanf("%s %d", s, &val);
       		ac.insert(s, i);
       		words.push_back(s), wvals.push_back(val);
       	}
       	
       	ac.build();
       	
       	printf("Case #%d: ", ++cases);
       	solve(); 
       	
        ac.free();
    }
    return 0;
}
/*
999
4
abbaaa 49
bba 41
ba 19
bbba 20
8
abbaaa 49
bba 41
ba 19
bbba 20
abbbabaaa 21
b 47
ababba 26
a 0
3
abaab 35
ab 9
abaabaaabbabababaaab 35
8
aabbbbbababbaaaab 14
abaabbaaaaaabbaabbba 13
babaaababaaaaabababa 17
abaab 35
ab 9
abaabaaabbabababaaab 35
bbbaaa 31
aabab 34
32
aa 19
bababbabbbaabaaaab 40
aabbbaaaaaa 48
ababaaabbabbbaabbb 38
a 42
bbbbbaabbbaa 10
baabbbababaab 41
aabbabbabba 28
baaab 3
aaaaaaaaa 15
bbbabbababaaabab 16
aab 18
baaab 2
abbbab 2
bababa 4
bbabbbbbaabbaaaababb 35
bbbaabba 34
bbbb 24
bbbb 17
babbbabbababababaa 9
ababaaaa 38
bbbb 3
bba 31
aabaabaaa 34
aabbbbbaababaa 41
aabbbaabbbabaababbbb 45
abbbaabbababab 37
ababbaabb 3
bbabbbbbaba 8
a 10
babbabaabbbbab 34
bbababaaaaaaaaa 5
 */
Read More +
解題區►解題區 - UVa

UVa 1398 - Meteor

Problem

進行天文觀測，天空上有 n 個流星，以及拍攝的區域。

給定每一個流星的起始位置與速度，請問在哪一個時刻可以拍到最多顆流星在拍攝區域內部。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 
4 2 
2 
-1 1 1 -1 
5 2 -1 -1 
13 6 
7 
3 -2 1 3 
6 9 -2 -1 
8 0 -1 -1 
7 6 10 0 
11 -2 2 1 
-2 4 6 -1 
3 2 -5 -1

Sample Output

1
2
1 
2

Solution

將每一個流星進入和離開拍攝區域的時間求出，並且組合成 (enter_time, 1), (leave_time, -1) 的方式，根據時間由小排到大，利用掃描線算法統計累計的最大值即可。

求流星進出區域的時間，可以將 x, y 座標分開考慮，對進入時間取最大值、離開時間取最小值。

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
// sweep line algorithm
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int LCM = 2520; // gcd(1, 2, 3, ..., 10) = 2520, /vx, /vy, vx, vy <= 10
int W, H;
pair<int, int> getTime(int sx, int sy, int vx, int vy) {
	int enter = 0, leave = INF;
	if (vx == 0) {
		if (sx <= 0 || sx >= W)
			leave = 0;
	} else if (vx < 0) {
		enter = max(enter, (sx - W) * LCM / (-vx));
		leave = min(leave, (sx - 0) * LCM / (-vx));
	} else {
		enter = max(enter, (0 - sx) * LCM / (vx));
		leave = min(leave, (W - sx) * LCM / (vx));
	}
	if (vy == 0) {
		if (sy <= 0 || sy >= H)
			leave = 0; 
	} else if (vy < 0) {
		enter = max(enter, (sy - H) * LCM / (-vy));
		leave = min(leave, (sy - 0) * LCM / (-vy));
	} else {
		enter = max(enter, (0 - sy) * LCM / (vy));
		leave = min(leave, (H - sy) * LCM / (vy));
	}
	return make_pair(enter, leave);
}
int main() {
	int testcase, N;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &W, &H);
		scanf("%d", &N);
		
		vector< pair<int, int> > D;
		for (int i = 0; i < N; i++) {
			int sx, sy, vx, vy;
			scanf("%d %d %d %d", &sx, &sy, &vx, &vy);
			pair<int, int> t = getTime(sx, sy, vx, vy);
			if (t.first < t.second) {
				D.push_back(make_pair(t.first, 1));
				D.push_back(make_pair(t.second, -1));
			}
		}
		
		sort(D.begin(), D.end());
		int ret = 0;
		for (int i = 0, s = 0; i < D.size(); i++) {
			s += D[i].second;
			ret = max(ret, s);
		}
		printf("%d\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1342 - That Nice Euler Circuit

Problem

一筆畫完成一個簡單多邊形，請問有多少個區域。

Sample Input

1
2
3
4
5
5
0 0 0 1 1 1 1 0 0 0 
7 
1 1 1 5 2 1 2 5 5 1 3 5 1 1 
0

Sample Output

1
2
Case 1: There are 2 pieces. 
Case 2: There are 5 pieces.

Solution

利用尤拉公式 $V - E + F = 2$ 來完成，藉由線段交找到所有頂點集合，去除掉重複點後，檢查邊的數量，如此一來就可以找到面的數量。

特別小心共線計算。

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
// Euler characteristic, V - E + F = 2
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.h>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
	}
	bool operator!=(const Pt &a) const {
    	return !(a == *this);
	}
    bool operator<(const Pt &a) const {
		if (fabs(x - a.x) > eps)
			return x < a.x;
		if (fabs(y - a.y) > eps)
			return y < a.y;
		return false;
	}
	double length() {
		return hypot(x, y);
	}
	void read() {
		scanf("%lf %lf", &x, &y);
	}
};
const double pi = acos(-1);
int cmpZero(double v) {
	if (fabs(v) > eps) return v > 0 ? 1 : -1;
	return 0;
}
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
	Pt s, e;
	int label;
	Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
	}
	bool operator!=(const Seg &other) const {
		return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
	}
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
	if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) < 0 &&
		cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) < 0)
		return 1;
	return 0;
}
Pt getIntersect(Seg a, Seg b) {
	Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
	return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
	double x, y;
	x = a.x * cos(radian) - a.y * sin(radian);
	y = a.x * sin(radian) + a.y * cos(radian);
	return Pt(x, y);
}
int inPolygon(vector<Pt> &p, Pt q) {
	int i, j, cnt = 0;
	int n = p.size();
	for(i = 0, j = n-1; i < n; j = i++) {
		if(onSeg(p[i], p[j], q))
			return 1;
		if(p[i].y > q.y != p[j].y > q.y &&
		q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
		cnt++;
	}
	return cnt&1;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
		area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
	double a, b, c, v;
	a = as.y - ae.y, b = ae.x - as.x;
	c = - (a * as.x + b * as.y);
	v = a * p.x + b * p.y + c;
	return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
// maybe collinear !!!!!!!!
int main() {
	const int MAXN = 305;
	int n, cases = 0;
	Pt D[MAXN];
	while (scanf("%d", &n) == 1 && n) {		
		int V = 0, E = 0; 
		vector<Pt> SV;
		
		for (int i = 0; i < n; i++)
			D[i].read(), SV.push_back(D[i]);
		for (int i = 0; i+1 < n; i++) {
			for (int j = i+1; j+1 < n; j++) {
				if (intersection(D[i], D[i+1], D[j], D[j+1])) {
					Pt p = getIntersect(Seg(D[i], D[i+1]), Seg(D[j], D[j+1]));
					SV.push_back(p);
				}
			}
		}
		
		sort(SV.begin(), SV.end());
		SV.resize(unique(SV.begin(), SV.end()) - SV.begin());
		V = SV.size(), E = n - 1;
		for (int i = 0; i < SV.size(); i++) {
			for (int j = 0; j+1 < n; j++) {
				if (onSeg(D[j], D[j+1], SV[i]) && SV[i] != D[j] && SV[i] != D[j+1])
					E++;
			}
		}
//		printf("%d %d\n", E, V);
		int ret = E - V + 2; // V - E + F = 2, F = E - V + 2
		printf("Case %d: There are %d pieces.\n", ++cases, ret);
	}
	return 0;
}
/*
7 
1 1 1 5 2 1 2 5 5 1 3 5 1 1 
0
*/
Read More +
解題區►解題區 - UVa

UVa 1326 - Jurassic Remains

Problem

博物館對於骨頭化石進行拼湊作業，每一個骨頭上用 A - Z 去標記。兩片骨頭可以連接則表示具有相同的英文字母。

現在有數組骨頭，上面會有數個街口。現在找一組骨頭集合，使得每一個接口都有其連接的對象，盡可能使集合越大越好。

Sample Input

1
2
3
4
5
6
7
6
ABD
EG
GE
ABE
AC
BCD

Sample Output

1
2
5
1 2 3 5 6

Solution

題目相當於問找一個集合，使得每一個字母數量出現偶數次。

由於 N = 24，這個數量使用 $O(2^{24})$ 相當消耗時間。使用中間相遇法 (在密碼學中可以見到，有點雙向 Bfs 的味道)，也就是分治算法的概念，將問題對切，從兩個統計結果中找交集。算法降至 $O(2^{12} \times 12)$

考慮前 N/2 個骨頭 A、後 N/2 個骨頭 B，分別找到在字母集出現狀態為 S 的最佳解 A1, B1，若將兩個相同狀態組合 $S \text{ XOR } S = 0$ 符合出現偶數次的條件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
	int n;
	char s[128];
	while (scanf("%d", &n) == 1) {
		int mask[32] = {};
		for (int i = 0; i < n; i++) {
			scanf("%s", s);
			int x = 0;
			for (int j = 0; s[j]; j++)
				x ^= (1<<(s[j] - 'A')); 
			mask[i] = x;
		}
		
		// D&C, dp, bitmask
		map<int, int> dp1, dp2;
		int div1 = n/2, div2 = n - n/2;
		for (int i = 0; i < (1<<div1); i++) {
			int x = 0;
			for (int j = 0; j < div1; j++) {
				if ((i>>j)&1)
					x ^= mask[j];
			}
			if (dp1.count(x) || __builtin_popcount(dp1[x]) < __builtin_popcount(i))
				dp1[x] = i;			
		}
		for (int i = 0; i < (1<<div2); i++) {
			int x = 0;
			for (int j = 0; j < div2; j++) {
				if ((i>>j)&1)
					x ^= mask[j + div1];
			}
			if (dp2.count(x) || __builtin_popcount(dp2[x]) < __builtin_popcount(i))
				dp2[x] = i;			
		}
		
		int retCnt = 0, retMask = 0;
		for (map<int, int>::iterator it = dp1.begin();
			it != dp1.end(); it++) {
			if (dp2.count(it->first)) {
				int x = it->second | ((dp2[it->first]) << div1);
				if (__builtin_popcount(x) > retCnt) {
					retCnt = __builtin_popcount(x);
					retMask = x;
				}
			}
		}
		printf("%d\n", retCnt);
		for (int i = 0, f = 0; i < n; i++) {
			if ((retMask>>i)&1) {
				if (f)	putchar(' ');
				f = 1;
				printf("%d", i+1);
			}
		}
		puts("");
	}
	return 0;
}
Read More +