解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 A - Attack and Split

Problem

有一隻史萊姆可以進行分裂和合併，大小為 x 的史萊姆可以分裂成兩個小史萊姆 y 和 z，滿足 x = y + z。當兩個史萊姆大小 p, q 合併時，新的史萊姆為 r = p xor q。請問是否存在數次的分裂和合併，所有史萊姆都消失！

Sample Input

1
2
3
4
3
1 1
2 9 17
3 12 15 19

Sample Output

1
2
3
No
Yes
Yes

Solution

亂來的奇偶和判定！以下是不負責任的說法！對於一種合法解 {a1, a2}，則 {a1-1, 1, a2-1, 1} 也一定會合法，不斷地拆分下去，所有史萊姆的大小都是 1，也發現到總和一定是偶數。因此只要判斷總和的奇偶數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        int n;
        long long x, sum = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x);
            sum += x;
        }
        puts(sum%2 ? "No" : "Yes");
    }
    return 0;
}
/*
 3
 1 1
 2 9 17
 3 12 15 19
*/
Read More +
解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 Warmup C - Exploding CPU 2

Problem

詢問一個區間有多少 鄒賽爾數 (Zeisel number)

鄒賽爾數是一種無平方數因數的數，而且至少有三個質因數可以用下式表示，質因數由小排到大滿足 $p_{x} = A p_{x-1} + B$。

105, 1419, 1729, 1885, 4505, 5719, 15387, 24211, 25085, …

1
2
3
4
5
6
7
4505 = 1 * 5 * 17 * 53
A = 3, B = 2
p0 = 1
p1 = 3 * p0 + 2 = 5
p2 = 3 * p1 + 2 = 17
p3 = 3 * p2 + 2 = 53

找到 $10^{15}$ 以內的所有 Zeisel number。

Sample Input

1
2
3
2
4505 4505
0 5000

Sample Output

1
2
1
5

Solution

一開始設想，既然小於 $10^{15}$ 又要三個質數，那麼最小的質因數應該要小於 $10^5$，否則會超過指定範圍。

接著第一次嘗試時，窮舉變數 $A$ 針對第一個質因數 $p_{1}$ 得到 $B = p_{1} - A$，得到下一項在範圍內 … 這樣效率非常差。A 的範圍非常大，質因數也非常多，而且還要檢驗每一項是否質數，效能相當低落。

接著第二次嘗試時，窮舉 $p_{1}, p_{2}$，這樣的計算量是 $10^5$ 內的質數個數 n，至少為 $O(n^2)$，嘗試一下發現速度還是太慢，藉由聯立方程式解出 A, B，卻有不少 A 是不存在的整數解。

1
2
3
A + B = p1
p1 A + B = p2
A = (p2 - p1)/(p1 - 1), B = p1 - A

接著第三次嘗試時，反過來窮舉，先讓 $A$ 一定有解，再看 $p_{2}$ 是否為質數，因此 $p_2 = p_1 + k \times (p_1 - 1)$，由於 $p_{i} - 1$ 造成的增長幅度遠比質數個數快很多，效能上有顯著地提升。

現在還有一個疑問，保證 $p_1 \le 10^5$，但是當 $p_1$ 很小，$p_2$ 可能會大於 $10^5$ 嗎，甚至必須窮舉到 $\sqrt{10^{15}}$？

這裡我不確定，放大範圍去嘗試時，發現找到的 Zeisel number 最多 9607 個，放大搜索範圍不再增加，那就不斷地縮減，讓找到的時間縮小不逾時。

1.980s TLE

不是說好限制 2.000s？1.980s 得到 TLE，第一次使用 NTUJ 真歡樂。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXL (10000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
int P[5500000], Pt = 0;
vector<long long> ret;
void sieve() {
	register int i, j, k;
	SET(1);
	int n = 10000000;
	for(i = 2; i <= n; i++) {
		if(!GET(i)) {
			for (k = n/i, j = i*k; k >= i; k--, j -= i)
				SET(j);
			P[Pt++] = i;
		}
	}
}
long long MAXVAL = 1e+15;
int isprime(long long v) {
	if (v < 2)	
		return 0;
	if (v < 10000000)
		return !GET(v);
	for (int i = 0; i < Pt && (long long) P[i] * P[i] <= v; i++)
		if (v%P[i] == 0)
			return 0;
	return 1;
}
void make() {
	for (int i = 0; i < Pt && P[i] < 100000; i++) {
		for (int j = P[i] + P[i]-1; j < 1000000; j += P[i] - 1) {
			if (!isprime(j))
				continue;
			long long A = (j - P[i])/(P[i]-1);
			long long B = P[i] - A;
			long long m = P[i], cnt = 1, mm = P[i];
			while (mm <= MAXVAL) {
				if (A && MAXVAL / m / A <= 0)
					break;
				if (m * A + B <= m)
					break;
				m = m * A + B;
				if (MAXVAL / mm / m <= 0)
					break;
				if (!isprime(m))
					break;
//				printf("%lld ", m);
				mm = mm * m, cnt ++;
				if (cnt >= 3) {
					ret.push_back(mm);
//					printf("%lld %lld %lld\n", mm, A, B);
				}
			}
		}
	}
	sort(ret.begin(), ret.end());
	for (int i = 0; i < 243; i++)
		printf("%d\n", ret[i]);
//	printf("%d\n", ret.size());
}
int main() {
	sieve();
	make();
	int testcase;
	long long L, R;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%lld %lld", &L, &R);
		int r = 0;
		for (int i = 0; i < ret.size(); i++)
			r += ret[i] >= L && ret[i] <= R;
		printf("%d\n", r);
	}
	return 0;
}
/*
2
4505 4505
0 5000
*/
Read More +
解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 Warmup B - The Brush

Problem

給一個 $N \times N$ 的棋盤，放置城堡 (rook)，城堡只能攻擊同行同列，這裡更特別一些，只能攻擊右下角位置。

下方是一個 $5 \times 5$ 範例，其中 R 表示城堡的位置，* 表示城堡可攻擊的格子，也就是範例的第三組測資。

1
2
3
4
5
6
7
8
9
10
11
12
+-+-+-+-+-+
| | | | |R| 1
+-+-+-+-+-+ 
| | |R|*|*| 2
+-+-+-+-+-+
| |R|*|*|*| 3
+-+-+-+-+-+
|R|*|*|*|*| 4
+-+-+-+-+-+
|*|*|*|R|*| 5
+-+-+-+-+-+
 1 2 3 4 5

保證輸入中城堡不會出現在同行同列，請問可攻擊的格子有多少個 (意即計算 * 的數量)。

Sample Input

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

Sample Output

1
2
3
6
10
13

Solution

很明顯地發現，答案是 所有城堡可攻擊數量總和 扣除 交集點數量 ，兩兩城堡最多一個交集點，並且交集點不會重疊 (不同行列的關係)，而交集點只發生在逆序對中。因此找到逆序對總數，可以利用 D&C 的 merge sort 算法，或者套用 Binary indexed 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
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, A[131072];
int BIT[131072];
void modify(int x, int val) {
	while (x <= n) {
		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 testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n); 
		for (int i = 0; i < n; i++)
			scanf("%d", &A[i]);
		
		for (int i = 0; i <= n; i++)
			BIT[i] = 0;
		long long ret = 0;
		for (int i = 0; i < n; i++) {
			ret += n - A[i];
			ret += n - i - 1;
			ret -= i - query(A[i]-1);
			modify(A[i], 1);
		}
		printf("%lld\n", ret);
	}
	return 0;
}
/*
3
3
1 2 3
5
5 4 3 2 1
5
5 3 2 1 4
*/
Read More +
解題區►解題區 - 其他題目

[Tmt514] Beverage Cup 2 Warmup A - Euler's Criterion

Problem

日本電影《博士熱愛的算式》中，

博士只有八十分鐘的記憶，　　　　　　　　　
一旦超過這個時間，　　　　　　　　　　　　
他的記憶就自動歸零，重新開始。　　　　　　
然而，博士卻用一個簡單的數學公式，　　　　
驗證了愛的永恆。

  • 《博士熱愛的算式》
$$e^{i \pi} + 1 = 0 \\ e^{ix} = cos(x) + i sin(x) \\ e^{i \pi} = cos(\pi) + i sin(\pi) = -1$$

判斷 $a \equiv x^2 (\text{ mod } p)$ 中，$a$ 是否在模 $p$ 下是個平方數。則滿足

$$a^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 (\text{ mod } p)$$

從歐拉定理 $a^{\varphi (p)} \equiv 1 (\text{ mod } p)$ 可以推導得到上述。接著給定一個集合，分別帶入 $a$, $p$ 有多少組合法解。

Sample Input

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

Sample Output

1
2
5
7

Solution

窮舉帶入，利用快速冪乘積檢驗之。

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
#include <stdio.h>
long long mpow(long long x, long long y, long long mod) {
	long long ret = 1;
	while (y) {
		if (y&1)
			ret = (ret * x)%mod;
		y >>= 1, x = (x * x)%mod;
	}
	return ret;
}
int main() {
	int testcase;
	int n, p[128];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &n); 
		for (int i = 0; i < n; i++)
			scanf("%d", &p[i]);
			
		int ret = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j)
					continue;
				if (mpow(p[i], (p[j]-1)/2, p[j]) == 1)
					ret++;
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}
Read More +
解題區►解題區 - 其他題目

SRM 659 Div1 PublicTransitHard

Problem

給一棵樹圖，然後可以放置傳送門與兩地，可以在一地經過傳送門，從另一個地點飛出，請問放置方法有多少種使得最遠兩點移動距離不大於 X。

Solution

看題解作！但我相信仍然是噁心的！

首先需要做樹形 dp 找到最長路徑，保留通過自己子樹最深三條、不通過自己子樹擁有最長路徑。

窮舉所有建設方案 $O(N^2)$，用 $O(log n)$ 時間驗證方案正確性。固定其中一個點 $A$，接著 Dfs 走訪另一點 $B$，$A$ 到 $B$ 之間只會有一條路徑 $A,u_1, u_2, …, B$，壓縮其中的路徑變成一維，對於中間的每一點找到 hanging value，hanging value 也就是葉子到 u 的最長距離。

假設從 A 到 B 上的點特徵表示成 $(p_0, v_0), (p_1, v_1), (p_2, v_2), …, (p_n, v_n)$ 其中 $p_i$ 表示從 A 出發的距離，$v_i$ 表示 hanging value。

Example

1
2
3
4
5
6
7
|        |    |         | ...    |
|        |    |    |    |        |
A(u0) - u1 - u2 - u3 - u4 ... - B(un)
|        |    |    |    |        |
|        |    |    |    |
|        |              Y        
|        X

一個 | 表示子樹的距離 1，從上圖中可以得到 $(p_0, v_0) = (0, 4)$, $(p_1, v_1) = (1, 3)$, $(p_2, v_2) = (2, 2)$, $(p_3, v_3) = (3, 2)$, $(p_4, v_4) = (4, 2)$ …

如果要從 u1 分支 X 抵達 u4 分枝 Y，

  • 經過 u1 - u2 - u3 - u4 的最短距離為 $dist = p_4 - p_1 + v_1 + v_4 = 8 $
  • 經過 u1 - A - B - un-1 - ... - u4 的最短距離為 $dist = n - p_4 + p_1 + v_1 + v_4$

特別小心下列情況

1
2
3
4
5
6
7
| 
|                 |
A(u0) ---------- u1 - u2 - u3 - u4 ... - B(un)
|                /|
|\              / |\      <---- inner longest path > X, Stop Dfs
| \            /    \
|  \          /      \

假設 $X = 5$ 有可能 $v_i \le 5$ 但是內部的最長路徑本身就超過，就要停止 Dfs。

More

那移動的距離方案為通過、不通過傳送點兩種，任意兩點 p2 > p1，不滿足的方案滿足下列兩等式

  • $p_2 - p_1 + v_1 + v_2 > X$，轉化變成 $v_1 - p_1 > X - p_2 - v_2$
  • $LIM = X - (n - p_2 + p_1 + v_1 + v_2) < 0$，為了檢查不滿足，則 LIM 要最小化，則 $v_1 + p_1$ 要最大化。

根據 Dfs 逐漸加點，將問題轉化成 RMQ (對一條不滿足下的情況下，第二條要盡可能滿足，利用最大值找到最慘情況。)。

檢查從新加入的點 u，則查找區間 $[X-p_2-v_2, \infty]$ 的最大值 $v_i+p_i$，帶入得到 $LIM$。若 $LIM \geq 0$，得到建造方案合法。Dfs 傳遞下去時，另一種 $LIM$ (屏除子樹 $v_i$ 的計算會不同) 將會限制最多再往下 $LIM$ 層 ($LIM$ 相當於說距離限制還差多少，當往後搜索時，路徑上的節點計算出的 $LIM$ 會逐漸減少 1，若發上路徑上的所有 $LIM < 0$ 則不合法。)，超過這個限制會造成不經過 u 的兩點最短路徑大於 X。

最後特別小心，如果子樹內的最長路徑大於 X 也要停止走訪！接著就實作持久化線段樹，要完成噁心的樹走訪下，不同狀態的線段樹恢復與傳遞變化。

Code

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
class SegementTree {
public:
	struct Node {
	    int l, r, lson, rson;
	    int mx;
	} node[1048576];
	int nodesize;
	int init(int l, int r) {
		nodesize = 0;
		int root = build(l, r);
		return root;
	}
	int build(int l, int r) {
	    if (l > r)  return 0;
	    int k = nodesize++;
	    node[k].l = l, node[k].r = r, node[k].mx = -9999;
	    node[k].lson = node[k].rson = 0;
	    if (l == r) return k;
	    int m = (l + r)/2;
	    node[k].lson = build(l, m);
	    node[k].rson = build(m+1, r);
	    return k;
	}
	int change(int p, int x, int val) {
	    int k = nodesize++;
	    node[k] = node[p];
	    node[k].mx = max(node[p].mx, val);
	    if (node[k].l == node[k].r) return k;
	    int m = (node[k].l + node[k].r)/2;
	    if (x <= m)
	        node[k].lson = change(node[p].lson, x, val);
	    else
	        node[k].rson = change(node[p].rson, x, val);
	    return k;
	}
	int query(int k, int l, int r) {
	    if (l <= node[k].l && node[k].r <= r)
	        return node[k].mx;
	    int m = (node[k].l + node[k].r)/2;
	    if (r <= m)
	        return query(node[k].lson, l, r);
	    else if (l > m)
	        return query(node[k].rson, l, r);
	    else
	    	return max(query(node[k].lson, l, r), query(node[k].rson, l, r));
	}
} segTree;
const int MAXN = 2048;
const int SHIFT = 4096, MAXR = 8192;	
class PublicTransitHard {
public:
	vector<int> g[MAXN];
	int dp[MAXN][3];
	int dp2[MAXN][2];
	int ret1, ret2, limitX, testA;
	void dfs(int u, int p) {
		dp[u][0] = 0, dp[u][1] = 0, dp[u][2] = 0;
		dp2[u][0] = 0, dp2[u][0] = 0;
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if (v == p)
				continue;
			dfs(v, u);
			int d = dp[v][0]+1;
			if (d > dp[u][2])
				dp[u][2] = d;
			if (dp[u][2] > dp[u][1])
				swap(dp[u][2], dp[u][1]);
			if (dp[u][1] > dp[u][0])
				swap(dp[u][1], dp[u][0]);
				
			d = max(dp[v][0] + dp[v][1], dp2[v][0]);
			if (d > dp2[u][1])
				dp2[u][1] = d;
			if (dp2[u][1] > dp2[u][0])
				swap(dp2[u][0], dp2[u][1]);
		}
	}
	void dfs2(int u, int p, int segId, int depth, int mnLIM) {
		int p2 = depth, v2 = dp[u][0];
		int mx = segTree.query(segId, limitX - p2 - v2 + 1 + SHIFT, MAXR);
		int LIM = limitX - (depth - p2 + mx + v2);
//		printf("query [%d, oo] = %d\n", limitX - p2 - v2 + 1, mx);
//		printf("testA %d - %d, %d %d, LIM = %d, mx = %d\n", testA, u, p2, v2, LIM, mx);
		if (depth > mnLIM)
			return ;
		if (LIM >= 0 && dp[u][0] + dp[u][1] <= limitX && dp2[u][0] <= limitX) {
//			printf("----- connect %d %d, \n", testA, u);
			if (testA == u)	ret1++;
			else			ret2++;
		}
			
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if (v == p)
				continue;
				
			int d = dp[v][0]+1;
			if (d != dp[u][0])
				v2 = dp[u][0];
			else
				v2 = dp[u][1];
			
			if (d == dp[u][0]) {
				if (dp[u][1] + dp[u][2] > limitX)
					continue;
			} else if (d == dp[u][1]) {
				if (dp[u][0] + dp[u][2] > limitX)
					continue;
			} else {
				if (dp[u][0] + dp[u][1] > limitX)
					continue;
			}
			
			d = max(dp[v][0] + dp[v][1], dp2[v][0]);
			if (d == dp2[u][0]) {
				if (dp2[u][1] > limitX)
					continue;
			} else {
				if (dp2[u][0] > limitX)
					continue;
			}
			
			
//			printf("dfs %d %d, update [%d] = %d\n", p2, v2, v2 - p2, v2 + p2);
			int mx = segTree.query(segId, limitX - p2 - v2 + 1 + SHIFT, MAXR);
			int LIM2 = limitX - (depth - p2 + mx + v2);
			int segId3 = segTree.change(segId, v2 - p2 + SHIFT, v2 + p2);
//			printf("dfs %d %d, update [%d] = %d, LIM2 = %d\n", p2, v2, v2 - p2, v2 + p2, LIM2);
			dfs2(v, u, segId3, depth+1, min(mnLIM, depth+LIM2));
		}
	}
	int countValidTeleporters(int N, vector<int> edges, int X) {
		ret1 = ret2 = 0, limitX = X;
		for (int i = 0; i < N; i++)
			g[i].clear();
		
		for (int i = 0; i < edges.size(); i++) {
			int u = i+1, v = edges[i];
			g[u].push_back(v);
			g[v].push_back(u);
		}
		
		for (int A = 0; A < N; A++) {
			dfs(A, -1);
			int root = segTree.init(0, MAXR);
			testA = A;
//			puts("-----");
			dfs2(A, -1, root, 0, 9999);
		}
		return ret1 + ret2/2;
	}	
};
int main() {
	PublicTransitHard test;
//	int N = 4;
//	int edges[] = {0, 1, 2};
//	int X = 1;
//	int N = 3;
//	int edges[] = {0, 0};
//	int X = 2;
//	int N = 6;
//	int edges[] = {0, 0, 0, 1, 1};
//	int X = 2;
//	int N = 7;
//	int edges[] = {0, 1, 0, 1, 2, 4};
//	int X = 3;
	
//	int N = 16;
//	int edges[] = {0, 1, 0, 2, 0, 0, 4, 5, 8, 9, 10, 11, 8, 4, 6};
//	int X = 7;
	
	int N = 56;
	int edges[] = {0, 1, 1, 3, 1, 5, 1, 0, 8, 8, 10, 10, 12, 10, 10, 8, 16, 16, 18, 19, 19, 21, 19, 19, 24, 25, 25, 27, 18, 0, 30, 30, 30, 33, 34, 34, 34, 30, 38, 39, 39, 38, 42, 43, 0, 45, 45, 45, 48, 45, 45, 51, 45, 53, 54};
	int X = 12;
	
	int ret = test.countValidTeleporters(N, vector<int>(edges, edges + N - 1), X);
	printf("%d\n", ret);
	return 0;
}
Read More +
解題區►解題區 - 其他題目

SRM 659 Div1 CampLunch

Problem

有 M 個人連續 N 天都在同一個地方吃飯，請問它們購買餐點方案數。

  • 與當天坐在相鄰附近的人，一起購買雙人分享餐，解決這天。
  • 買一份雙人分享餐，連續吃兩天。
  • 買一份單人餐，解決這天。

Solution

淡淡地憂傷，一個人買雙人分享餐吃兩天 … 不過沒關係，一道插頭 dp，相當於插入 $1 \times 2$ 或 $2 \times 1$ 塞滿盤面。但每一天相鄰的人都不同，因此壓縮 bitmask 狀態會需要變動，統一紀錄 $[1<<M]$ ，表示 $i-bit$ 第 $i$ 個人是否已經解決今天，接著對應 (up = self, left = 查找位置)，滾動數組進行轉移。

可以參照 UVa 11270 的解法。現在要處理的是變化的 colume 填充。

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
#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const long long MOD = 1000000007;
const int MAXN = 17, MAXM = 17;
class CampLunch {
public:
	int dp[2][1<<MAXM];
	int count(int N, int M, vector <string> a) {
		memset(dp, 0, sizeof(dp));
		int flag = 0;
		dp[0][(1<<M)-1] = 1;
		for (int i = 0; i < N; i++) {			
			for (int j = 0; j < M; j++) {
				int p = flag, q = !flag;
				flag = 1 - flag;
				memset(dp[q], 0, sizeof(dp[q]));
				for (int k = (1<<M)-1; k >= 0; k--) {
					int L, U;
					int Lid, Uid;
					int ways = dp[p][k];
					
					if (ways == 0)
						continue;
					
					Lid = j == 0 ? -1 : (a[i][j-1] - 'A');
					Uid = a[i][j] - 'A';
					L = j == 0 ? 1 : ((k>>(Lid))&1);
					U = (k>>Uid)&1;
										
					if (L == 0 && U == 1) 	// plan 1, sit next to each other
						dp[q][k|(1<<Lid)] = (dp[q][k|(1<<Lid)] + ways)%MOD;
					if (U == 0) 			// plan 2, two consecutive days.
						dp[q][k|(1<<Uid)] = (dp[q][k|(1<<Uid)] + ways)%MOD;
					if (U == 1)				// plan 3, single
						dp[q][k|(1<<Uid)] = (dp[q][k|(1<<Uid)] + ways)%MOD;
					if (U == 1)				// reserve
						dp[q][k^(1<<Uid)] = (dp[q][k^(1<<Uid)] + ways)%MOD;
				}
			}
		}
		
		return dp[flag][(1<<M)-1];
	}
};
int main() {
	CampLunch cl;
	string v[] = {"ABC","ABC"};
	int vv = cl.count(2, 3, vector<string>(v, v+2));
	printf("%d\n", vv);
	return 0;
}
/*
 2
2
{"AB","AB"}
*/
Read More +
解題區►解題區 - 其他題目

SRM 659 Div1 ApplesAndOrangesEasy

Problem

給定長度為 $N$ 個序列，在這序列中表示吃蘋果或者是橘子的順序，必須保證的是任意連續區間長度為 $K$ 中，最多只會吃 $K/2$ 個蘋果，已知部分位置一定是蘋果，請問序列中最多有幾個蘋果。

Solution

嘗試要用 $O(N)$ 的貪心解法，弄了快一個小時沒出來。弄 $O(N^2)$ 做一下就過，從尾端開始往前掃，來決定未知的地方 $i$ 是否要放蘋果，假若後綴 $[i, i+K-1]$ 的蘋果樹，如果總量小於限制將這個地方設置為蘋果，反之超過，將最鄰近的 蘋果全部取消到符合規定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
class ApplesAndOrangesEasy {
public:
	int maximumApples(int N, int K, vector<int> info) {
		const int MAXN = 4096;
		int A[MAXN] = {}, apple = K/2;
		int ret = (int) info.size();
		memset(A, -1, sizeof(A));
		for (int i = 0; i < info.size(); i++)
			A[info[i]] = 1;
		for (int i = N+1; i <= N + K; i++)
			A[i] = 0;
		for (int i = N; i >= 1; i--) {
			int sum = 0;
			for (int j = i; j < i+K; j++)
				sum += A[j] >= 1;
			if (sum < apple && A[i] == -1)
				A[i] = 2, ret++, sum++;
			if (sum > apple) {
				for (int j = i; j < i+K; j++) {
					if (sum > apple && A[j] == 2) {
						A[j] = -1, ret--, sum--;
					}
				}
			}
		}
		return ret;
	}
};
int main() {
	ApplesAndOrangesEasy ap;
	int a[] = {1, 3};
	ap.maximumApples(3, 2, vector<int>(a, a + 2));
	return 0;
}
Read More +
解題區►解題區 - 其他題目

2015 Google Code Jam Round 1C

windows format to linux format 

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

題解

  • A. Brattleship
  • B. Typewriter Monkey
  • C. Less Money, More Problems

［A. Brattleship］

哥哥和弟弟玩遊戲，在一個 R * C 的網格中，弟弟會放置一個 1 * W 水平放置的戰艦，接著哥哥蒙上眼睛，問弟弟說 (x, y) 是否為戰艦的一部分，而弟弟很狡猾，可以在猜測過程中偷偷改答案，想辦法去搬移戰艦，使得哥哥猜測數量最多。請問哥哥至少要多少次才能猜到。

R * C 跟 1 * C 其實是一樣的，哥哥仍然必須猜完所有的行，因此至少花費 (R - 1) * floor(C/W) + LastLine 的花費，LastLine 怎麼求得呢？其一方法是貪心，其二方法是 dp 博弈最小化，由於 C <= 20，使用 2^C 進行博弈 dp 是不錯的選擇 (懶人系列，咱走這裡)。

［B. Typewriter Monkey］

給定猴子 K 個鍵盤按鈕，鍵盤按鈕對應的字母可能會重複，每個按鈕敲擊的機率均勻分布，接著希望猴子敲擊 S 次，統計出現目標長度 L 的字串 (在長度 S 字串中可能會重疊)，當猴子打出一個目標字串就給一條香蕉。人員要準備最慘情況的香蕉個數，請問猴子完成一次後，獎勵猴子後，手上剩餘的香蕉個數的期望值為何？

首先要找出最慘情況的香蕉個數，也就是去找到最大重疊長度 x，暴力搜索即可 (有機會咱們再來談談 KMP)，基本香蕉數量為 1 + (S - L) / (L - x)。接著找到猴子拼出目標字串的期望值，考慮目標字串的起始位置 i 的機率 expect = p(S) * 1^(S - L)，p(S) = \product(uniform(target[i])), i in [1, S - L + 1]
，最後答案顯而易見 = max_banana - expect * (S - L + 1)。

［C. Less Money, More Problems］

給定 D 種不同的面值，每一種面值最多使用 C 次，請問要湊出 [1, V] 之間所有價錢的交易方式，至少要增加幾個新面值。

貪心思路，假設能湊出 [1, S]，則對於新面值 x 而言，可以增加範圍 [1, S + x * C]。將 x 由小排到大，若 S < x - 1 則新增一個面值 S+1 下去，擴張到範圍 [1, S + (S+1) * C] … 如此類推，想辦法湊出 [1, V]。

A code

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1<<20], R, C, W;
int isEnd(int u) {
	int place = (1<<W)-1;
	int v = 0;
	for (int i = 0; i < C - W; i++) {
		if (((u>>i)&place) == 0) 
			return 0; 
		v = min(v, __builtin_popcount(((u>>i)&place)));
	}
	return W - v;
}
int dfs(int u) {
	if (isEnd(u))
		return isEnd(u);
	if (dp[u] != -1)
		return dp[u];
	int &ret = dp[u];
	ret = 0x3f3f3f3f;
	for (int i = 0; i < C; i++) {
		if ((u>>i)&1)
			continue;
		ret = min(ret, dfs(u|(1<<i)) + 1);
	}
	return ret;
}
int solve() {
	memset(dp, -1, sizeof(dp));
	int v = dfs(0);
	return v + (R-1) * (C/W);
}
int main() {
	int testcase, cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d %d", &R, &C, &W);
		printf("Case #%d: %d\n", ++cases, solve());
	}
	return 0;
}
/*
999
1 5 1
1 10 3
 
3
1 4 2
1 7 7
2 5 1
*/

B code

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 <string.h>
#include <algorithm>
using namespace std;
int K, L, S;
char keyboard[128], target[128];
double solve() {
	if (L > S)
		return 0;
	int a[128] = {};
	for (int i = 0; i < K; i++)
		a[keyboard[i]]++;
	for (int i = 0; i < L; i++)
		if (a[target[i]] == 0)
			return 0;
			
	double mx_banana = S / L, expect = 1;
	for (int i = 1; i < L; i++) {
		int ok = 1;
		for (int j = 0; target[i+j] && j < L; j++)
			ok &= target[j] == target[i+j];
		if (ok) {
			mx_banana = 1 + (S - L) / (i); 
			break;
		}
	}
	for (int i = 0; i < L; i++)
		expect = (expect * a[target[i]]) / K;
	return mx_banana - expect * (S - L + 1);
}
int main() {
	int testcase, cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d %d", &K, &L, &S);
		scanf("%s %s", keyboard, target);
		
		double ret = solve();
		printf("Case #%d: %lf\n", ++cases, ret);
	} 
	return 0;
}

C code

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
	int testcase, cases = 0;
	long long C, K, V, x[128];
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%lld %lld %lld", &C, &K, &V);
		
		long long sum = 0, ret = 0;
		for (int i = 0; i < K; i++) {
			scanf("%lld", &x[i]);
		}
		for (int i = 0; i < K; i++) {
			while (sum < V && sum < x[i] - 1) {
				ret++;
				long long ncoin = sum + 1;
				sum += ncoin * C;
			}
			sum += x[i] * C;
		}
		while (sum < V) {
			ret++;
			long long ncoin = sum + 1;
			sum += ncoin * C;
		}
		printf("Case #%d: %d\n", ++cases, ret);
	}
	return 0;
}
/*
*/
Read More +
解題區►解題區 - 其他題目

PTC 201504 D Bilibili's Railgun

Problem

科學超電磁砲 御坂美琴 (簡稱 Bilibili)，在學園都市中經常發生事件，每一個事件都會持續好幾天 [si, ei]，解決一個事件需要使用一次電磁砲。但是在一天中若使用 x 次，當天的消耗能量是 x * x (第 i 發能量為 2i - 1)。

為了解決所有事件，請問最少花費為多少。

Sample Input

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

Sample Output

1
2
3
4
3
3
9
12

Solution

Version 1

這裡先提供一個 TLE 的作法，之後再來看看如何用增廣路徑的思路。

對這個問題，可以建造最少費用流模型，在點數不大的情況下可以運行，而這一題額外限制能量消耗的線性關係，最少費用流會因為邊數過多造成 TLE。

建造的方案如 source - event - (day, i) - sink，藉由滿流保證每個事件都會被解決，而每個 event 都指派到第 day 天的第 i 發，約束流量為 1 費用 2i - 1 到 sink，保證每一天使用的能量消耗不重複。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <assert.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define MAXN 131072
#define MAXM (1048576<<2)
struct Node {
    int x, y, cap;
    double cost;// x->y, v
    int next;
} edge[MAXM];
int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
int dis[MAXN];
void addEdge(int x, int y, int cap, int cost) {
    assert(x < MAXN && y < MAXN && e < MAXM);
    edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
    edge[e].next = head[y], head[y] = e++;
}
int mincost(int s, int t, int n) {
    int mncost = 0;
    int flow, totflow = 0;
    int i, x, y;
    int oo = 0x3f3f3f3f;
    while (1) {
        for (int i = 0; i <= n; i++)
            dis[i] = oo;
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while (!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for (i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if (edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                    dis[y] = dis[x] + edge[i].cost;
                    pre[y] = x, record[y] = i;
                    if (inq[y] == 0) {
                        inq[y] = 1;
                        if (Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if (dis[t] == oo)
            break;
        flow = 0x3f3f3f3f;
        for (x = t; x != s; x = pre[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for (x = t; x != s; x = pre[x]) {
            int ri = record[x];
            edge[ri].cap -= flow;
            edge[ri^1].cap += flow;
            edge[ri^1].cost = -edge[ri].cost;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
int main() {
    int testcase, N, S[1024], E[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        int A[128] = {}, B[128] = {};
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &S[i], &E[i]);
            for (int j = S[i]; j <= E[i]; j++)
                A[j]++;
        }
        
        e = 0;
        memset(head, -1, sizeof(head));
        
        for (int i = 1; i <= 100; i++)
            B[i] = B[i-1] + A[i];
//        printf("%d\n", A[100]);
        int source = N + B[100] + 1, sink = N + B[100] + 2;
//        printf("source %d sink %d\n", source, sink);
        for (int i = 1; i <= 100; i++) {
//            printf("---- %d\n", A[i]);
            for (int j = 0, lj = B[i-1]; j < A[i]; j++, lj++) {
                addEdge(N + lj, sink, 1, j * 2 + 1);
                assert(N + lj < source);
//                printf("%d %d\n", N + lj, sink);
            }
        }
        for (int i = 0; i < N; i++) {
            addEdge(source, i, 1, 0);
            for (int j = S[i]; j <= E[i]; j++) {
                for (int k = 0, lk = B[j-1]; k < A[j]; k++, lk++) {
                    addEdge(i, N + lk, 1, 0);
                }
            }
        }
        
        int ret = mincost(source, sink, sink + 1);
        printf("%d\n", ret);
    }
    return 0;
}

Version 2

使用增廣路徑的想法，依序加入每一個 event 進來，移動 event 發生的時間。

當兩天原本的事件數 event[i] - event[j] = 1，那麼移動 event i 到另一天 j，總花費不會增加。接著可以保證，前 i 個 event 完成時，能夠移動 event 的情況 (直接或間接)，不會發生事件數差異大於等於 2！如果發生這種情況，則前 i 個事件的能量消耗不是最優解。

加入第 i+1 個事件，有機會發生可移動事件的天數之間的事件數差異大於等於 2，若發生這種情況，將其中一個事件移動到那一天執行。由於上述觀察，加入新的事件時，必然選擇可填入的最少能量消耗的日期，再去消除可以遞移的情況。否則會有一個更優解存在。

有沒有可能存在前 i-1 個事件不是最優解，加入第 i 個事件可以變成最優解？答案是否定的，既然不是最優解，一定存在事件數差異大於等於 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
#include <stdio.h> 
#include <assert.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
using namespace std;
const int MAXN = 1024;
const int MAXD = 105;
struct Time {
	int st, ed;
	bool operator<(const Time &a) const {
		if (st != a.st)	
			return st < a.st;
		return ed < a.ed;
	}
} T[MAXN];
int visited[MAXD], match[MAXN];
vector<int> event[MAXD];
int event_move[MAXD][MAXD];
int dfs(int u, int place) {
	visited[u] = 1;
	if (event[u].size() < place - 1)
		return 1;
	for (int i = 1; i < MAXD; i++) {
		if (!visited[i]) {
			if (event_move[u][i] > 0) { // find a object to move i-day
				if (dfs(i, place)) {
					int id = -1, id_pos = -1;
					for (int j = 0; j < event[u].size(); j++) {
						id = event[u][j], id_pos = j;
						if (T[id].st <= i && i <= T[id].ed)
							break;
					}
					assert(id >= 0);
					for (int j = T[id].st; j <= T[id].ed; j++) {
						event_move[u][j]--;
						event_move[i][j]++;
					}
					match[id] = i;
					event[u].erase(event[u].begin() + id_pos);
					event[i].push_back(id);
					return 1;
				}
			}
		}
	}
	return 0;
}
int main() {
	int testcase, N;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &N);
		for (int i = 0; i < N; i++)
			scanf("%d %d", &T[i].st, &T[i].ed);
		
		memset(event_move, 0, sizeof(event_move));
		for (int i = 0; i < MAXD; i++)
			event[i].clear();
		
		sort(T, T + N);
		for (int i = 0; i < N; i++) {
			int mn_day = T[i].st;
			for (int j = T[i].st; j <= T[i].ed; j++) {
				if (event[j].size() < event[mn_day].size())
					mn_day = j;
			}
			
			match[i] = mn_day, event[mn_day].push_back(i);
			for (int j = T[i].st; j <= T[i].ed; j++) {
				event_move[mn_day][j]++;
			}			
			
			memset(visited, 0, sizeof(visited));
			dfs(mn_day, event[mn_day].size());
		}
		
		int ret = 0;
//		for (int i = 0; i < N; i++)
//			printf("%d\n", match[i]);
		for (int i = 1; i < MAXD; i++)
			ret += event[i].size() * event[i].size();
		printf("%d\n", ret);
	}
	return 0;
}

Version 3

費用流的做法不難、想法也很簡單，但是速度一直提升不上來，原因是邊數過多，費用流 O(VVE)，最暴力的費用流 E = 10^5、V = 10^5，病急投靠夢月來優化，由於費用流每次增廣流量都為 1，最後一層的邊使用跟回溯只會有兩種，因此將 (day, i) 的狀態縮小為 (day)，接著用特殊邊來可函數的邊花費 (？)，大幅度地降點後，終於來到 E = 10^5、V = 10^3。

深感欣慰的同時 TLE 也來報喜。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <assert.h>
#include <algorithm>
using namespace std;
#define MAXN 2048
#define MAXM (526244)
struct Node {
    int x, y, cap;
    int cost;// x->y, v
    int next, sp;
} edge[MAXM];
int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
int dis[MAXN];
void addEdge(int x, int y, int cap, int cost, int sp) {
    assert(x < MAXN && y < MAXN && e < MAXM);
    if (sp == 0) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].sp = 0, edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].sp = 0, edge[e].next = head[y], head[y] = e++;
    } else {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].sp = sp, edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = cap, edge[e].cost = -cost;
        edge[e].sp = -sp, edge[e].next = head[y], head[y] = e++;
    }
}
int pass[MAXN];
int f(Node &e) {
    if (e.sp == 0)
        return e.cost;
    if (e.sp == 1)
        return e.cost * pass[e.x] * 2 + 1;
    if (e.sp == -1) {
        if (pass[e.y] == 0)
            return 0x3f3f3f3f;
        return -(e.cost * pass[e.y] * 2 + 1);
    }
    assert(false);
}
int mincost(int s, int t, int n) {
    int mncost = 0;
    int flow, totflow = 0, x, y;
    int INF = 0x3f3f3f3f;
    for (int i = 0; i < n; i++)
        pass[i] = 0;
    while (1) {
        for (int i = 0; i <= n; i++)
            dis[i] = INF;
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while (!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for (int i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                int ecost = f(edge[i]);
                if (edge[i].cap > 0 && dis[y] > dis[x] + ecost) {
                    dis[y] = dis[x] + ecost;
                    pre[y] = x, record[y] = i;
                    if (inq[y] == 0) {
                        inq[y] = 1;
                        if (Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if (dis[t] == INF)
            break;
        flow = INF;
        for (x = t; x != s; x = pre[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for (x = t; x != s; x = pre[x]) {
            int ri = record[x];
            if (edge[ri].sp == 0)
                edge[ri].cap -= flow;
            if (edge[ri^1].sp == 0)
                edge[ri^1].cap += flow;
                
            if (edge[ri].sp == 1)
                pass[edge[ri].x] ++;
            if (edge[ri].sp == -1)
                pass[edge[ri].y] --;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
const int MAXD = 105;
int main() {
    int testcase, N, S[1024], E[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        
        for (int i = 0; i < N; i++)
            scanf("%d %d", &S[i], &E[i]);
        
        e = 0;
        memset(head, -1, sizeof(head));
        
        int source = N + MAXD + 2, sink = N + MAXD + 3;
        for (int i = 0; i < N; i++) {
            addEdge(source, i, 1, 0, 0);
            for (int j = S[i]; j <= E[i]; j++)
                addEdge(i, N + j, 1, 0, 0);
        }
        
        for (int i = 1; i < MAXD; i++)
            addEdge(N + i, sink, 1, 1, 1);
        
        int ret = mincost(source, sink, sink + 1);
        printf("%d\n", ret);
    }
    return 0;
}

Version 4

既然思路明確，再努力觀察一下規則。

等著夢月弄出更高端的寫法，由於第一層的節點連接是一個區間，又因為邊 cost 都是單向往 sink 流去，回溯邊根本派不上用場，掃描線思路放進去找增廣路徑，速度有了突破性地進展。

根據區間的右端點排序，依序加入事件。每一次加入後往左掃描，當找到可以交換的日期時，把當時的工作抓出來擴充交換區間，擴充的區間只會往左端點增長。

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 <algorithm>
#include <set>
using namespace std;
const int MAXN = 1024;
const int MAXD = 105;
struct Time {
    int st, ed;
    bool operator<(const Time &a) const {
        return ed < a.ed;
    }
} T[MAXN];
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++)
            scanf("%d %d", &T[i].st, &T[i].ed);
            
        sort(T, T + N);
        int ret = 0;
        int from[MAXD], assign[MAXN];
        set<int> event[MAXD];
        for (int i = 0; i < N; i++) {
            int l = T[i].st, r = T[i].ed;
            for (int j = r; j >= l; j--)                        // argument path
                from[j] = i;
            
            int day = r;    // choose
            for (int j = r; j >= l; j--) {
                if (event[j].size() < event[day].size())
                    day = j;
                if (event[day].size() == 0)
                    break;
                for (set<int>::iterator it = event[j].begin();
                    it != event[j].end(); it++) {
                    if (T[*it].st < l) {
                        for (int k = l-1; k >= T[*it].st; k--)  // argument path
                            from[k] = *it;
                        l = T[*it].st;
                    }
                }
            }
            
            ret += event[day].size() * 2 + 1;
            while (true) {
                int u = from[day];
                int d = assign[u];
                event[day].insert(u), assign[u] = day;
                if (u == i) break;
                event[d].erase(u), day = d;
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}
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 +