注：本文根據以前筆記整理而成，若有問題可以留言 or 詢問我～
Finding Nemo
BFS，我用了SPFA
Searching the Web
模擬題，我用了一堆STL~~~
Argus
用個堆來維護一下就行了。
Fun Game
做的真辛苦@@@
厄，首先如果只有1個方向并且是形成鏈的話很容易想出O(2 ^ 16 * 16 * 16)的算法
2個方向的問題容易解決，同時考慮正向和反向，復雜度變為O(2 ^ 16 * 32 * 32)
關于鏈的問題，容易想到的方法是再加一維記錄頭，不過這樣的復雜度好像有點大。
事實上，我們只要考察以第一種string為頭的方案，然后最后再企圖用最后一個和頭合并一下就可以了。。。自己證。。。
然后就勉強AC了~~~
CODE
1
// Beijing 2002, Fun Game
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <string>
8#include <algorithm>
9#include <vector>
10
11using namespace std;
12
13struct queuenode
{
14
int st, last;
15
}queue[(1 << 16) * 32];
16int n, opt[40][40], d[1 << 16][32], len[20];
17vector<string> s;
18
19bool init();
20void work();
21
22int main() {
23 for (; init(); ) work();
24 return 0;
25}
26
27bool init() {
28 cin >> n;
29 if (n == 0) return false;
30 s.resize(n);
31 for (int i = 0; i < n; ++i) cin >> s[i];
32 int p = 0;
33
while (p < s.size()) {
34 bool bein = false;
35 for (int i = 0; i < s.size(); ++i)
36 if (p != i && s[i].find(s[p]) != string::npos) {
37 bein = true; break;
38
}
39 if (bein) s.erase(s.begin() + p);
40 else ++p;
41 }
42 n = s.size();
43 for (int i = 0; i < n; ++i) len[i] = s[i].size();
44 for (int i = 0; i < n * 2; ++i)
45 for (int j = 0; j < n * 2; ++j) {
46 string p1 = s[i / 2], p2 = s[j / 2];
47 if (i % 2 == 1) reverse(p1.begin(), p1.end());
48 if (j % 2 == 1) reverse(p2.begin(), p2.end());
49 for (int len = min(p1.size(), p2.size()) - 1; len >= 0; --len)
50 if (p1.substr(p1.size() - len, len) == p2.substr(0, len)) {
51 opt[i][j] = len; break;
52 }
53 }
54 return true;
55}
56
57void work() {
58 int ans = 1000000000;
59 fill(d[0], d[0] + (1 << 16) * 32, 1000000000);
60 d[1][0] = len[0];
61 int head = 0, tail = 1;
62 queue[0].st = 1; queue[0].last = 0;
63 for (int i = 1; i < (1 << n); ++i)
64 for (int j = 0; j < n * 2; ++j) {
65 if (d[i][j] == 1000000000) continue;
66 for (int k = 0; k < n * 2; ++k) {
67 int st = i | (1 << (k >> 1));
68 d[st][k] = min(d[st][k], d[i][j] + len[k >> 1] - opt[j][k]);
69 }
70 }
71
72 for (int j = 0; j < n * 2; ++j) ans = min(ans, d[(1 << n) - 1][j] - opt[j][0]);
73 if (ans == 1) ans = 2;
74 cout << ans << endl;
75}
76
Square
根據Steiner Tree的結論可以得到
n == 1時是這種形狀最優
\/
/\
n >= 2時是這種形狀最優
\_/
/ \
然后枚舉......
p.s. 求Steiner Tree的題：
Dhaka 2002 Hermes' Colony
Ural1460 Wires
Color a Tree
不錯的題呢~
厄，首先如果沒有限制，顯然c的從大到小順序就可以了。
類似的想法，我們先考察c最大的那個節點。
如果它沒有father那么顯然排在開頭。
否則，它應當緊跟它的father（否則向前調整）
于是這兩個節點可以合為一個。。。繼續作。
注意k個節點合成一個后它的c用所有節點的平均數來算。。。（自己想）
似乎可以用heap + disjoint set做到O(nlogn)，不過這么小的范圍寫O(n^2)也不錯哈。。。:D
Kid's Problem
熟練搞出來一個模線性方程組。
Gauss消元的時候注意一點用類似于gcd的方法加來減去，這樣保證方程組與原來同解。
最后再搜索就行了。。。（因為模的不一定是質數）
Gauss消元系列問題：
PKU1395 Cog-Wheels （最后需要搜索）
PKU2055 Kid's Problem （這兩題如出一轍）
PKU2947 Widget Factory
URAL1561 Winnie the Pooh （非常推薦，上一題就是這道題的子問題啊～～～。。。）
CODE
1// Beijing 2002, Kid's Problem
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <algorithm>
8
9using namespace std;
10
11int a[25][25], b[25], x[25], poline[25], k, n, ans;
12
13bool init();
14void work();
15void search(int lid, int xid, int now);
16
17int main() {
18 for (; init(); ) work();
19 return 0;
20}
21
22bool init() {
23 cin >> k >> n;
24 if (k == 0 && n == 0) return false;
25 fill(a[0], a[0] + 25 * 25, 0);
26 fill(b, b + 25, 0);
27 for (int i = 0; i < k; ++i) {
28 cin >> b[i]; --b[i];
29 }
30 for (int i = 0; i < k; ++i) {
31 int p;
32 cin >> p;
33 for (int j = 0; j < p; ++j) {
34 int ta, tb;
35 cin >> ta >> tb;
36 a[--ta][i] = n - tb;
37 }
38
39 }
40 return true;
41}
42
43void work() {
44 int p = 0;
45 for (int i = 0; i < k; ++i) {
46 if (a[p][i] == 0) {
47 for (int j = p + 1; j < k; ++j) {
48 if (a[j][i] != 0) {
49 int tmp[25];
50 copy(a[p], a[p] + k, tmp);
51 copy(a[j], a[j] + k, a[p]);
52 copy(tmp, tmp + k, a[j]);
53 swap(b[p], b[j]);
54 break;
55 }
56 }
57 if (a[p][i] == 0) {
58 poline[i] = -1; continue;
59 }
60 }
61 poline[i] = p;
62 for (int j = p + 1; j < k; ++j)
63 while (a[j][i] != 0)
64 if (a[p][i] > a[j][i]) {
65
66 for (int l = 0; l < k; ++l) {
67 a[p][l] = (a[p][l] - a[j][l] + n) % n;
68 }
69 b[p] = (b[p] - b[j] + n) % n;
70 }
71 else {
72
73 for (int l = 0; l < k; ++l) {
74 a[j][l] = (a[j][l] - a[p][l] + n) % n;
75
76
77 }
78 b[j] = (b[j] - b[p] + n) % n;
79 }
80 ++p;
81 }
82 for (int i = p; i < k; ++i)
83 if (b[i] != 0) {
84 cout << "No solution" << endl; return;
85 }
86 ans = 1000000000;
87 search(p - 1, k - 1, 0);
88 if (ans == 1000000000) cout << "No solution" << endl;
89 else cout << ans << endl;
90}
91
92void search(int lid, int xid, int now) {
93 if (now >= ans) return;
94 if (lid == -1 || xid == -1) {
95 ans = now; return;
96 }
97 if (poline[xid] == -1)
98 for (x[xid] = 0; x[xid] < n; ++x[xid]) search(lid, xid - 1, now + x[xid]);
99 else {
100 int sum = 0;
101
102 lid = poline[xid];
103
104 for (int i = xid + 1; i < k; ++i) sum = (sum + a[lid][i] * x[i]) % n;
105 for (x[xid] = 0; x[xid] < n; ++x[xid])
106 if ((sum + a[lid][xid] * x[xid]) % n == b[lid])
107 search(lid - 1, xid - 1, now + x[xid]);
108 }
109}
110
The Separator in Grid
簡單的讀題題。好像從上往下BFS下就行了。
The Lost House
推薦啊。。。
首先是動態規劃。
令suc[u] = 在以i為root的tree上找到house的sum of expect values
fail[u] = 在以i為root的tree上沒有找到house的sum of expect values
fail[u]容易算，就是Sigma(2 + fail[v]), v是u的son.
suc[u]的算法嘛。。。假設我們知道訪問它的sons的順序是v[]，于是計算流程如下：
int now = 0;
for (int i = 0; i < u_sons; ++i) {
suc[u] += (now + 1) * leaf[v[i]] + suc[v[i]];
now += 2 + fail[v[i]];
}
至于這個順序怎么確定么，8!的搜索或者2 ^ 8 * 8的動態規劃似乎都能過。
不過有一個很牛B的貪心。
對于某兩個兒子v1, v2，我們現在要確定它的順序。
則先v1的方案好于先v2的方案
<=> (now + 1) * leaf[v1] + suc[v1] + (now + 1 + 2 + fail[v2]) * leaf[v2] + suc[v2] <
(now + 1) * leaf[v2] + suc[v2] + (now + 1 + 2 + fail[v1]) * leaf[v1] + suc[v1]
<=> （2 + fail[v1]) * leaf[v2] < (2 + fail[v2]) * leaf[v1]
嗯。。。然后。。。排序。。。復雜度O(n * log2k)。。。。。。。
詳情參閱國家集訓隊 黃勁松 的論文。