注：本文根据以前笔记整理而成，若有问题可以留言 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)。。。。。。。
详情参阅国家集训队 黄劲松 的论文。