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 * C1 * 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 +

UVa 1091 - Barcodes

條碼中有一種編碼方式為 Code 11,只會針對數字 0 - 9 以及 - 進行編碼。對於每一個編碼結果都使用 5 個黑白相間 (BWBWB)的條紋表示,用 5 個 bits 表示黑白線的狀態,若 bit 為 1 則表示為粗線,反之為細線。為了間隔相鄰,都會使用白色細線間隔。

對應表如下

Character Encoding
0 00001
1 10001
2 01001
3 11000
4 00101
5 10100
6 01100
7 00011
8 10010
9 10000
- 00100
Start/Stop 00110

由於條碼掃描時,可能由左往右或由左往右掃描,藉由 START/STOP 來包裹內容,藉由非回文的編碼來導正順序。例子 START-1-3-2-STOP

同時會加入兩個檢查碼,分別為 C, K 公式如題目所附,所以會變成 START-1-3-3-C-K-STOP

現在給定一組條碼寬度陣列 (BWBWB …),粗線寬度為細線寬度的兩倍,可能會發生誤差,誤差範圍為標準寬度的 5% 以內。請問是否存在合法的條碼。

Sample Input

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

Sample Output

1
2
3
Case 1: 123-45
Case 2: bad code
Case 3: bad K

Solution

由於要加入檢查碼,保證輸入的解碼至少 4 個字元 (START-C-K-STOP),由於必須在字元編碼之間加入細白線,加設編碼 n 個字元,則陣列大小為 5n + n - 1

接著要找細線、粗線到底使用什麼寬度,可以考慮把所有寬度找到,找一組合適的閥值 ((max_value + min_value)/2) 區分兩者,接著考慮粗線和細線的寬度是否能在 5% 內,由於是兩倍,放大兩倍之後誤差也會放大兩倍,那麼統一大小後,查看範圍是否落在 0.95 ~ 1.05 之間。

接著小心解碼,要支持順或逆的方式去讀,也要滿足每個編碼都存在,而且檢查碼要正確,同時要符合 START-???-C-K-STOP 的格式 … 等。

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
class Code11 {
public:
map<string, int> code;
Code11() {
code["00001"] = 0, code["10001"] = 1;
code["01001"] = 2, code["11000"] = 3;
code["00101"] = 4, code["10100"] = 5;
code["01100"] = 6, code["00011"] = 7;
code["10010"] = 8, code["10000"] = 9;
code["00100"] = 10; // -
code["00110"] = -1;
}
string scan(int n, int b[]) {
if (n%6 != 5) return "bad code";
if ((n + 1)/6 < 5) return "bad code"; // S?CKE
int m = (n + 1)/6;
int mxw, mnw;
mxw = 0, mnw = 0x3f3f3f3f;
for (int i = 0; i < n; i++)
mxw = max(mxw, b[i]), mnw = min(mnw, b[i]);
double t = (mnw + mxw) / 2.0;
mxw = 0, mnw = 0x3f3f3f3f;
for (int i = 0; i < n; i++) {
int v = 0;
if (b[i] < t)
v = b[i] * 2;
else
v = b[i];
mxw = max(mxw, v), mnw = min(mnw, v);
}
if (mxw * 95 > mnw * 105) // 5% larger or smaller than intended
return "bad code";
string bcode[256];
for (int i = 0, j = 0; i < n; i += 6, j++) {
bcode[j] = "";
for (int k = i; k < i+5; k++) {
if (b[k] < t)
bcode[j] = bcode[j] + "0";
else
bcode[j] = bcode[j] + "1";
}
if (i+5 < n && b[i+5] >= t) // separate bar = 0
return "bad code";
}
if (bcode[0] == "01100") { // modify decode order to START-XXX-STOP
reverse(bcode, bcode + m);
for (int i = 0; i < m; i++)
reverse(bcode[i].begin(), bcode[i].end());
}
if (bcode[0] != "00110" || bcode[m-1] != "00110")
return "bad code";
for (int i = 0; i < m; i++) { // undefine code
if (!code.count(bcode[i]))
return "bad code";
if (i > 0 && i < m-1 && code[bcode[i]] == -1)
return "bad code";
}
int C = 0, K = 0;
for (int i = 1; i < m - 3; i++)
C = (C + (((m - 4) - i)%10 + 1) * code[bcode[i]])%11;
for (int i = 1; i < m - 2; i++)
K = (K + (((m - 4) - i + 1)%9 + 1) * code[bcode[i]])%11;
if (C != code[bcode[m - 3]])
return "bad C";
if (K != code[bcode[m - 2]])
return "bad K";
string res;
for (int i = 1; i < m - 3; i++) {
int v = code[bcode[i]];
if (v < 10) res += (char)(v + '0');
else res += (char)('-');
}
return res;
}
} g;
int main() {
int n, b[256], cases = 0;
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%d", &b[i]);
string response = g.scan(n, b);
printf("Case %d: %s\n", ++cases, response.c_str());
}
return 0;
}
Read More +

UVa 982 - Cube

Problem

有一天醒來,發現自己身處一個方體房間,六個面上都有門可以通往其他房間,不幸地是這裏沒有食物,若不趕緊走出去就會死在這裡。

搜索途中遇到其他人,他們說有些房間藏著陷阱,一碰到就會致死。為了逃離這裡,發現每個房間的角落都有一個數字,這個數字隱藏著出口的方向,指引著下一個要打開的門,但即使這樣,仍然不知道門後的房間是否有致死陷阱。

若房間的數字為 N 時,下一個門的座標為

  • x = (N 出現幾次偶數位數) / (N 的總位數)
  • y = (N 出現幾次質數位數) / (N 的總位數)
  • z = (N 出現幾次小於 5 的奇數位數) / (N 的總位數)
  • 化簡分數,保證測資只會產生 0, 1/2, 1 三種情況
  • 得到 (x, y, z)。接著,再計算一個向量 (vx, vy, vz)
    • vx = N 的第一位數 / N 的第二位數
    • vy = N 的第三位數 / N 的第四位數
    • vz = N 的第五位數 / N 的第六位數
  • 內積 (x, y, z)(vx, vy, vz) = x * vx + y * vy + z * vz 化簡若發生分子為合數 (非質數非 1 的數),則保證下一個房間是安全的。

例如給定數字

1
2
3
4
5
6
7
8
9
10
11
N = 24556789
x = |[2, 4, 6, 8]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 1/2
y = |[2, 5, 5, 7]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 1/2
z = |[]| / |[2, 4, 5, 5, 6, 7, 8, 9]| = 0
vx = 2 / 4 = 1 / 2
vy = 5 / 5 = 1
vz = 6 / 7
x * vx + y * vy + vz = 3 / 4, 3 is prime, FATAL
1
2
3
4
5
6
7
8
9
10
11
N = 74974652
x = |[4, 4, 6, 2]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 1/2
y = |[7, 7, 5, 2]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 1/2
z = |[]| / |[7, 4, 9, 7, 4, 6, 5, 2]| = 0
vx = 7 / 4
vy = 9 / 7
vz = 4 / 6 = 2 / 3
x * vx + y * vy + vz = 7 / 8 + 9 / 14 = 85 / 56, 85 is not prime, SAFE.

Sample Input

1
2
24556789
74974652

Sample Output

1
2
3
4
1/2 1/2 0
FATAL
1/2 1/2 0
SAFE

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
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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
#include <assert.h>
using namespace std;
struct Frac {
long long x, y;
Frac(long long a = 0, long long b = 1) {
x = a, y = b;
normal();
}
void normal() {
if (y < 0) x = -x, y = -y;
long long g = llgcd(x, y);
x /= g, y /= g;
if (y < 0) x = -x, y = -y;
}
long long llgcd(long long x, long long y) const {
if (x == 0) return y;
if (y == 0) return x;
long long t;
while (x%y)
t = x, x = y, y = t % y;
return y;
}
Frac operator-(const Frac &a) const {
long long va = 0, vb = a.y / llgcd(y, a.y) * y;
va = vb / y * x - vb / a.y * a.x;
return Frac(va, vb);
}
Frac operator+(const Frac &a) const {
long long va = 0, vb = a.y / llgcd(y, a.y) * y;
va = vb / y * x + vb / a.y * a.x;
return Frac(va, vb);
}
Frac operator*(const Frac a) const {
long long g1 = llgcd(x, a.y), g2 = llgcd(a.x, y);
long long va = 0, vb = 0;
va = (x / g1) * (a.x / g2);
vb = (y / g2) * (a.y / g1);
return Frac(va, vb);
}
Frac operator/(const Frac a) const {
long long g1 = llgcd(y, a.y), g2 = llgcd(x, a.x);
long long va = 0, vb = 0;
va = (a.y / g1) * (x / g2);
vb = (y / g1) * (a.x / g2);
return Frac(va, vb);
}
bool operator==(const Frac &a) const {
return x - a.x == 0 && y - a.y == 0;
}
bool operator<(const Frac &a) const {
return x * a.y < a.x * y;
}
void print() {
if (y == 1)
printf("%lld", x);
else
printf("%lld/%lld", x, y);
}
};
Frac getX(char s[]) {
int a = 0, b = 0;
for (int i = 0; s[i]; i++) {
a += (s[i] - '0')%2 == 0;
b ++;
}
return Frac(a, b);
}
Frac getY(char s[]) {
int a = 0, b = 0;
for (int i = 0; s[i]; i++) {
int d = s[i] - '0';
if (d == 2 || d == 3 || d == 5 || d == 7)
a++;
b ++;
}
return Frac(a, b);
}
Frac getZ(char s[]) {
int a = 0, b = 0;
for (int i = 0; s[i]; i++) {
int d = s[i] - '0';
if (d < 5 && d%2 == 1)
a++;
b ++;
}
return Frac(a, b);
}
int getTestXYZ(char s[], Frac &x, Frac &y, Frac &z) {
int n = (int) strlen(s);
if (s[1%n] == '0' || s[3%n] == '0' || s[5%n] == '0')
return 0;
x = Frac(s[0%n] - '0', s[1%n] - '0');
y = Frac(s[2%n] - '0', s[3%n] - '0');
z = Frac(s[4%n] - '0', s[5%n] - '0');
return 1;
}
int isprime(int x) {
if (x == 1)
return 0;
for (int i = 2; i * i <= x; i++)
if (x%i == 0)
return 0;
return 1;
}
int main() {
char s[64];
while (scanf("%s", s) == 1) {
Frac x = getX(s), y = getY(s), z = getZ(s);
Frac rx, ry, rz;
x.print(), printf(" ");
y.print(), printf(" ");
z.print(), printf("\n");
assert(x == Frac(0, 1) || x == Frac(1, 2) || x == Frac(1, 1));
assert(y == Frac(0, 1) || y == Frac(1, 2) || y == Frac(1, 1));
assert(z == Frac(0, 1) || z == Frac(1, 2) || z == Frac(1, 1));
int f = getTestXYZ(s, rx, ry, rz);
if (!f) {
assert(false);
continue;
}
// rx.print(), printf(" ");
// ry.print(), printf(" ");
// rz.print(), printf("\n");
Frac dot = rx * x + ry * y + rz * z;
if (!isprime((int)dot.x) && dot.x != 1) {
puts("SAFE");
} else {
puts("FATAL");
}
// dot.print();
// puts("");
}
return 0;
}
/*
18540
385
1222
123456
1234
24556789
74974652
*/
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 +

UVa 715 - Substitution Cipher

Problem

給一串加密過後的字典,其這一段字典按照原先的字典順序。假設只使用小寫字母的前 k 個單字,請問是否能正確解密,並且輸出明文是什麼。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
cad
aac
bca
bdac

Output

1
2
abcde
Message cannot be decrypted.

Solution

給定加密過後的字典,可以做相鄰的單詞比較,來得到字母間的大小關係,藉由拓撲排序得到與原先字母的對應關係。為了要正確解密,檢查拓撲過程中的瓶頸,相當於當前 queue 的大小為 1 來保證這個字母的對應關係。若不是瓶頸,則存在模稜兩可的解密。

由於密文不會使用所有的字母,只需要考慮密文使用的字母都能正確解密即可,意即前 k 個字母只有部分可逆轉換,密文仍然可以解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
char word[1024][1024], msg[1024];
char sbox[128];
int sfail[128];
int buildGraph(int n, int m) {
vector<int> g[128];
int indeg[128] = {};
for (int i = 1; i < n; i++) {
int p = i-1, q = i;
for (int j = 0; word[p][j] && word[q][j]; j++) {
if (word[p][j] != word[q][j]) {
g[word[p][j]].push_back(word[q][j]);
indeg[word[q][j]]++;
break;
}
}
}
deque<int> Q;
for (int i = 'a'; i < 'a' + m; i++) {
if (indeg[i] == 0)
Q.push_front(i);
}
int fail[128] = {}, order[128], ocnt = 0, u;
while (!Q.empty()) {
u = Q.front(), Q.pop_front();
if (Q.size() >= 1) {
for (deque<int>::iterator it = Q.begin();
it != Q.end(); it++)
fail[*it] = 1;
}
order[ocnt++] = u;
for (int i = 0; i < g[u].size(); i++) {
if (--indeg[g[u][i]] == 0) {
Q.push_back(g[u][i]);
}
}
}
for (int i = 'a'; i < 'a' + m; i++)
if (indeg[i] > 0)
sfail[i] = 1;
for (int i = 0; i < 128; i++)
sbox[i] = i;
for (int i = 0; i < ocnt; i++)
sbox[order[i]] = 'a' + i, sfail[order[i]] = fail[order[i]];
return 1;
}
int decode(char msg[]) {
for (int i = 0; msg[i]; i++) {
if (sfail[msg[i]])
return 0;
msg[i] = sbox[msg[i]];
}
return 1;
}
int main() {
int testcase, n, m;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &m, &n);
for (int i = 0; i < n; i++)
scanf("%s", word[i]);
while (getchar() != '\n');
gets(msg);
buildGraph(n, m);
int f = decode(msg);
if (!f) {
puts("Message cannot be decrypted.");
} else {
puts(msg);
}
}
return 0;
}
/*
tricky case:
1
5 5
a
eb
eec
eeed
eeee
e
*/
Read More +

UVa 265 - Dining Diplomats

Problem

有 10 個外交官,各自代表自己的國家,並且也存在他們擅長的語言。現在 10 個外交官圍成一桌,相鄰的兩個外交官必須有相同語言,同時彼此的國家要是邦交關係。

提出一種可行的做法。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF USA GBR FRA FRG
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
TLC ADBE TQA DAO FHH NUW FAB PSR FEQ QPA KCW
TQA EB TLC DAO PSR FEQ KCW
DAO B TLC TQA FHH FAB PSR FEQ QPA KCW
FHH B TLC DAO PSR KCW
NUW DBE TLC
FAB D TLC DAO PSR FEQ QPA
PSR AC TLC TQA DAO FHH FAB QPA
FEQ CB TLC TQA DAO FAB QPA
QPA D TLC DAO FAB PSR FEQ KCW
KCW AE TLC TQA DAO FHH QPA

Output

1
2
3
4
5
6
7
8
9
10
11
12
1 F USA E
2 E CHN E
3 E GBR E
4 E KOR E
5 E ISR H
6 H JPN G
7 G POR E
8 E FRG R
9 R USR F
10 F FRA F
NO SOLUTION EXISTS

Solution

簡單的銷售員旅遊問題 (TSP: Travelling salesman problem),這裏使用動態規劃來完成,殺雞用牛刀,窮舉 O(10!) 也許是可行的。定義 dp[2^n][n] = dp[i][j] 表示當前經過的狀態 i,最後停留的點為 j,接著進行轉移,記錄走法。

特別小心有相同國家的外交官,建造相鄰邊時,邦交國中必然有自己國,否則會造成判斷錯誤。

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
#include <stdio.h>
#include <string.h>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <assert.h>
#include <algorithm>
using namespace std;
struct State {
string name, lang;
set<string> g;
int lang_mask[128];
int read() {
string line;
if (getline(cin, line)) {
assert(line.length() > 0);
g.clear();
stringstream sin(line);
sin >> name >> lang;
while (sin >> line)
g.insert(line);
g.insert(name); // what the fuck, same country in test data.
memset(lang_mask, 0, sizeof(lang_mask));
for (int i = 0; i < lang.length(); i++)
lang_mask[lang[i]] = 1;
return 1;
} else {
return 0;
}
}
int hasCommon(const State &a) {
for (int i = 0; i < 128; i++)
if (lang_mask[i] && a.lang_mask[i])
return 1;
return 0;
}
char common(const State &a) {
for (int i = 0; i < 128; i++)
if (lang_mask[i] && a.lang_mask[i])
return i;
return '-';
}
} C[10];
int g[10][10];
int dp[1<<10][10], from[1<<10][10];
int tsp(int u, int last) {
if (dp[u][last] != -1) return dp[u][last];
int &ret = dp[u][last];
ret = 0;
for (int i = 0; i < 10; i++) {
if (((u>>i)&1) && g[last][i]) {
int f = tsp(u^(1<<i), i);
if (f) {
from[u][last] = i;
return ret = 1;
}
}
}
return ret;
}
int main() {
while (true) {
for (int i = 0; i < 10; i++) {
if (!C[i].read())
return 0;
}
memset(g, 0, sizeof(g));
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (C[i].g.count(C[j].name) && C[j].g.count(C[i].name)
&& C[i].hasCommon(C[j])) {
g[i][j] = 1;
}
}
}
// for (int i = 0; i < 10; i++, puts(""))
// for (int j = 0; j < 10; j++)
// printf("%d ", g[i][j] > 0);
memset(dp, -1, sizeof(dp));
dp[0][0] = 1;
int flag = tsp((1<<10)-1, 0);
if (flag) {
int p = (1<<10)-1, q = 0;
int seat[10];
for (int i = 0; i < 10; i++) {
seat[i] = q;
q = from[p][q];
p = p^(1<<q);
}
for (int i = 0; i < 10; i++)
printf("%d %c %s %c\n", i+1, C[seat[i]].common(C[seat[(i-1+10)%10]]),
C[seat[i]].name.c_str(), C[seat[i]].common(C[seat[(i+1+10)%10]]));
} else {
puts("NO SOLUTION EXISTS");
}
puts("");
while (getchar() != '\n');
}
return 0;
}
/*
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF USA GBR FRA FRG
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
TLC ADBE TQA DAO FHH NUW FAB PSR FEQ QPA KCW
TQA EB TLC DAO PSR FEQ KCW
DAO B TLC TQA FHH FAB PSR FEQ QPA KCW
FHH B TLC DAO PSR KCW
NUW DBE TLC
FAB D TLC DAO PSR FEQ QPA
PSR AC TLC TQA DAO FHH FAB QPA
FEQ CB TLC TQA DAO FAB QPA
QPA D TLC DAO FAB PSR FEQ KCW
KCW AE TLC TQA DAO FHH QPA
*/
Read More +

UVa 1548 - The Game of Master-Mind

Problem

擴充版的 1A1B 問題,A 表示猜的數列有多少位置正確,B 表示有多少位置錯,但使用的數字有在正確答案中。現在考慮使用的數字不只有 0 - 9,將會使用 1 - C,同時數列長度為 P,又給定當前的猜測情況,已知數種數列得到的 AB。

找一組滿足所有猜測結果,字典順序最小的那一組答案。

Input

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

Output

1
2
3
1 1 1 3
You are cheating!
9 9 9 9 9 9 9 9

Solution

原題使用黑色和白色數量分別表示 AB。

現在考慮回過頭來思考 A B 如何計算。A 就是序列的交集個數,而 B 是集合的交集個數扣除 A 的答案。

這麼一來,窮舉過程中統計序列交集和集合交集會更為方便。依序窮舉每一位的答案,過程中檢查是否存在 A 或 B 超過某一組猜測。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXM = 128;
const int MAXP = 11;
const int MAXC = 128;
int P, C, M;
int B[MAXM], W[MAXM], G[MAXM][MAXP], CG[MAXM][MAXC];
int path[MAXP], bcnt[MAXM], bwcnt[MAXM], CGcnt[MAXC];
// B[i] = |vector_intersection(G, S)|
// W[i] = |set_intersection(G, S)| - B[i]
// ===>|set_intersection(G, S)| = B[i] + W[i]
int checkValid(int p, int c) {
for (int i = 0; i < M; i++) {
if (G[i][p] == c && bcnt[i] == B[i])
return 0; // BLACK exceeded
if (CGcnt[c] < CG[i][c] && bwcnt[i] == B[i] + W[i])
return 0; // |set_intersection(G, S)| > B[i] + W[i]
}
return 1;
}
void remove(int p, int c) {
for (int i = 0; i < M; i++) {
if (G[i][p] == c)
bcnt[i]++;
if (CGcnt[c] < CG[i][c])
bwcnt[i]++;
}
CGcnt[c]++;
}
void resume(int p, int c) {
for (int i = 0; i < M; i++) {
if (G[i][p] == c)
bcnt[i]--;
if (CGcnt[c] <= CG[i][c])
bwcnt[i]--;
}
CGcnt[c]--;
}
int dfs(int idx) {
if (idx == P) {
int ok = 1;
for (int i = 0; i < M && ok; i++)
ok &= bcnt[i] == B[i] && bwcnt[i] == B[i] + W[i];
return ok;
}
for (int i = 1; i <= C; i++) {
if (!checkValid(idx, i))
continue;
remove(idx, i);
path[idx] = i;
if (dfs(idx+1))
return 1;
resume(idx, i);
}
return 0;
}
int main() {
int testcase;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d %d", &P, &C, &M);
for (int i = 0; i < M; i++) {
memset(CG[i], 0, sizeof(CG[i]));
for (int j = 0; j < P; j++) {
scanf("%d", &G[i][j]);
CG[i][G[i][j]]++;
}
scanf("%d %d", &B[i], &W[i]);
}
memset(bcnt, 0, sizeof(bcnt));
memset(bwcnt, 0, sizeof(bwcnt));
memset(CGcnt, 0, sizeof(CGcnt));
int f = dfs(0);
if (f) {
for (int i = 0; i < P; i++)
printf("%d%c", path[i], i == P-1 ? '\n' : ' ');
} else {
puts("You are cheating!");
}
}
return 0;
}
Read More +

UVa 10748 - Knights Roaming

Problem

給予無限大盤面上,每一個騎士擁有自己的起始位置、限定走 k 步,請問盤面上有多少騎士可以抵達的點座標。

Input

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

Output

1
2
3
5
33
155

Solution

對於所有騎士同時運行 Bfs 很容易造成 TLE。這裏介紹其中一種優化策略,對於獨立的騎士直接計算可抵達的地點總數 (預處理只有一個騎士的盤面的答案)。

獨立騎士能步行的範圍為曼哈頓距離在 3 k[i] 內的所有點,對於兩兩騎士做交集判定,若不存在任何重疊區域,則該騎士為獨立。

為了加速運算,可以使用 hash 來防止重複運算,或者平移座標到可以在 500 x 500 內的陣列中做 Bfs。

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
#include <stdio.h>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
const unsigned int hash_mod = 100019;
set< pair<int, int> > R[hash_mod];
unsigned int hash(int x, int y) {
unsigned int a = 63689, b = 378551;
unsigned int value = 0;
int c[4] = {x, y, y, x};
for (int i = 0; i < 4; i++) {
value = value * a + c[i];
a *= b;
}
return value % hash_mod;
}
const int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
int bfs(int sx[], int sy[], int dstep[], int n) {
for (int i = 0; i < hash_mod; i++)
R[i].clear();
queue<int> X[64], Y[64];
int step, tx, ty, x, y;
for (int i = 63; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (dstep[j] == i) {
X[i].push(sx[j]), Y[i].push(sy[j]);
R[hash(sx[j], sy[j])].insert(make_pair(sx[j], sy[j]));
}
}
while (!X[i].empty()) {
x = X[i].front(), X[i].pop();
y = Y[i].front(), Y[i].pop();
if (i == 0) continue;
for (int k = 0; k < 8; k++) {
tx = x + dx[k], ty = y + dy[k];
if (!R[hash(tx, ty)].count(make_pair(tx, ty))) {
R[hash(tx, ty)].insert(make_pair(tx, ty));
X[i-1].push(tx), Y[i-1].push(ty);
}
}
}
}
int ret = 0;
for (int i = 0; i < hash_mod; i++)
ret += R[i].size();
return ret;
}
int main() {
int x[64], y[64], step[64];
int n;
int h[64] = {};
for (int i = 0; i <= 50; i++) {
x[0] = y[0] = 0, step[0] = i;
h[i] = bfs(x, y, step, 1);
}
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%d %d %d", &x[i], &y[i], &step[i]);
int independent = 0;
for (int i = 0; i < n; i++) {
int d = 0x3f3f3f3f;
for (int j = 0; j < n; j++) {
if (i == j) continue;
d = min(d, max(abs(x[i] - x[j]) + abs(y[i] - y[j]) - 3 * (step[i] + step[j]), 0));
}
if (d > 0)
independent += h[step[i]], step[i] = -1;
}
int ret = bfs(x, y, step, n) + independent;
printf("%d\n", ret);
}
return 0;
}
/*
5
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
5
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
4
-1 -1 2
2 2 1
3 3 3
4 4 3
30
0 0 50
1 1000 50
2 2000 50
3 3000 50
4 4000 50
5 5000 50
6 6000 50
7 7000 50
8 8000 50
9 9000 50
10 10000 50
11 11000 50
12 12000 50
13 13000 50
14 14000 50
15 15000 50
16 16000 50
17 17000 50
18 18000 50
19 19000 50
20 20000 50
21 21000 50
22 22000 50
23 23000 50
24 24000 50
25 25000 50
26 26000 50
27 27000 50
28 28000 50
29 29000 50
*/
Read More +

UVa 10725 - Triangular Square

Problem

給三角形的三邊,放置一個最大面積的正方形於三角形中。

求最大面積為何。

Input

1
2
3
2
6 6 6
2 2 2

Output

1
2
7.754051
0.861561

Solution

把三角形的最大邊找到,考慮是鈍角還是銳角三角形,接著把正方形的某一邊貼在三角形上,用幾何計算三角形的三點座標,拉 45 度分角線得到正方形另一點座標,計算正方形邊長。

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
#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));
}
int main() {
int testcase, e[3];
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d %d", &e[0], &e[1], &e[2]);
sort(e, e+3);
double sq_len = 0;
if (e[0]*e[0] + e[1]*e[1] <= e[2]*e[2]) { // right/obtuse triangle
double a = e[2], b = e[1], c = e[0]; // a > b > c
double theta = acos((a*a + b*b - c*c)/(2*a*b));
Pt A = rotateRadian(Pt(1, 0), theta) * b;
Pt vAC = rotateRadian(Pt(0, 0) - A, pi/4), vAB = rotateRadian(Pt(a, 0) - A, -pi/4);
Pt p = getIntersect(Seg(Pt(0, 0), Pt(a, 0)), Seg(A + vAC, A));
Pt q = getIntersect(Seg(Pt(0, 0), Pt(a, 0)), Seg(A + vAB, A));
sq_len = max((A - p).length(), (A - q).length()) / sqrt(2);
} else {
double a = e[2], b = e[1], c = e[0]; // a > b > c
double s = (a+b+c)/2;
double area = sqrt(s*(s-a)*(s-b)*(s-c));
double h = 2 * area / a;
h = 2 * area / b;
sq_len = max((b*h) / (b + h), sq_len);
h = 2 * area / c;
sq_len = max((c*h) / (c + h), sq_len);
}
double a = e[2], b = e[1], c = e[0]; // a > b > c
double s = (a+b+c)/2;
double area = sqrt(s*(s-a)*(s-b)*(s-c));
double h = 2 * area / a;
// h - x : h = x : a
// x = ah / (h + a)
sq_len = max((a*h) / (a + h), sq_len);
printf("%.6lf\n", sq_len * sq_len);
}
return 0;
}
/*
3
3 4 5
6 4 3
6 7 8
2
6 6 6
2 2 2
*/
Read More +

UVa 10615 - Rooks

Problem

給一個 n x n 個棋盤,放置 * 於棋盤上,著色所有的 * 使得同行同列的 * 都是不同顏色。

使用最小顏色總數,給出一種可行解。

Input

1
2
3
4
5
6
7
8
9
10
11
2
2
*.
**
4
*.*.
*.*.
***.
..**

Output

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

Solution

最小著色數為同行同列的最多 * 總數
為了輸出可行解,進行二分匹配。對於著色座標 (row, column) = (i, j) 拉一條 i->j 的邊,匹配一條邊,相當於著色一個點。

假設最少著色數是 c,則進行補邊,使得二分圖的 X-Y 集合中的每一個點都是 degree = c

進行 c 次的二分匹配,每一次匹配都是完美匹配,因符合性質`degree = c。這一次的所有匹配邊 (i, j) 表示相同顏色。
每一次完美匹配,會將所有的 degree - 1,因此便能將所有邊使用完畢。這裏有 Hall’s marriage theorem 的意味在,來保證完美匹配的存在。

如果不補邊,每一次最大匹配若不是完美匹配,最大匹配會造成下一次匹配不一定是最大,c 次二分匹配後,會有殘留的邊!也就是造成點未著色。

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
// Hall's marriage theorem, bipartite graph matching, maxflow
// for all subset X sat. |X| <= |Neighborhood(X)| = |Y|
//
#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 testcase;
int n, x, y;
char s[128][128];
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%s", s[i]);
vector<int> bigraph[128];
int row_deg[128] = {}, col_deg[128] = {};
int place_color[128][128];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (s[i][j] == '*') {
row_deg[i]++, col_deg[j]++;
bigraph[i].push_back(j);
}
}
}
int mx_colors = 0;
for (int i = 0; i < n; i++) {
mx_colors = max(mx_colors, row_deg[i]);
mx_colors = max(mx_colors, col_deg[i]);
}
// increase edge, make perfect matching
for (int i = 0; i < n; i++) {
if (row_deg[i] < mx_colors) {
for (int j = 0; j < n; j++) {
while (row_deg[i] < mx_colors && col_deg[j] < mx_colors) {
row_deg[i]++, col_deg[j]++;
bigraph[i].push_back(j);
}
}
}
}
// bipartite graph matching
for (int color = 0; color < mx_colors; color++) {
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 j = 0; j < bigraph[i].size(); j++)
g.Addedge(i, bigraph[i][j] + n, 1);
}
int matching = g.Maxflow(source, sink);
assert(matching == n); // perfect matching
// make sure, matching pair won't collision.
for (int i = 0; i < n; i++) {
for (Edge *p = g.adj[i]; p != NULL; p = p->next) {
int x = i, y = p->v, flow = p->flow;
if (flow == 0 && y - n >= 0 && y - n < n) {
// match x - (y - n) in bipartite graph
int r = x, c = y - n;
if (s[r][c] == '*')
place_color[r][c] = color;
// remove edge
bigraph[r].erase(find(bigraph[r].begin(), bigraph[r].end(), c));
}
}
}
}
for (int i = 0; i < n; i++)
assert(bigraph[i].size() == 0);
printf("%d\n", mx_colors);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (s[i][j] == '*') printf("%d", place_color[i][j] + 1);
else printf("%d", 0);
printf("%c", j == n-1 ? '\n' : ' ');
}
}
}
return 0;
}
/*
9999
4
****
****
****
****
4
***.
.***
.**.
....
4
****
.*.*
..**
...*
4
*...
.*..
..*.
...*
4
*...
.*..
..*.
..*.
2
*.
**
4
*.*.
*.*.
***.
..**
*/
Read More +