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)。。。。。。。