注:本文根据以前笔记整理而成,若有问题可以留言 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了~~~
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
CODE
1
// Beijing 2002, Fun Game
2
// Written By FreePeter
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
#include <cstdio>
5
#include <cstring>
6
#include <iostream>
7
#include <string>
8
#include <algorithm>
9
#include <vector>
10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11
using namespace std;
12![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct queuenode
{
14
int st, last;
15
}queue[(1 << 16) * 32];
16
int n, opt[40][40], d[1 << 16][32], len[20];
17
vector<string> s;
18![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
19
bool init();
20
void work();
21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
23
for (; init(); ) work();
24
return 0;
25
}
26![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (p < s.size())
{
34
bool bein = false;
35
for (int i = 0; i < s.size(); ++i)
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (p1.substr(p1.size() - len, len) == p2.substr(0, len))
{
51
opt[i][j] = len; break;
52
}
53
}
54
return true;
55
}
56
57![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int j = 0; j < n * 2; ++j)
{
65
if (d[i][j] == 1000000000) continue;
66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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 (非常推荐,上一题就是这道题的子问题啊~~~。。。)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
CODE
1
// Beijing 2002, Kid's Problem
2
// Written By FreePeter
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
#include <cstdio>
5
#include <cstring>
6
#include <iostream>
7
#include <algorithm>
8![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
9
using namespace std;
10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11
int a[25][25], b[25], x[25], poline[25], k, n, ans;
12![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
13
bool init();
14
void work();
15
void search(int lid, int xid, int now);
16![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
18
for (; init(); ) work();
19
return 0;
20
}
21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < k; ++i)
{
28
cin >> b[i]; --b[i];
29
}
30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < k; ++i)
{
31
int p;
32
cin >> p;
33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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
43![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void work()
{
44
int p = 0;
45![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < k; ++i)
{
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (a[p][i] == 0)
{
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int j = p + 1; j < k; ++j)
{
48![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (a[p][i] > a[j][i])
{
65
66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
72![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
73![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
92![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void search(int lid, int xid, int now)
{
93
if (now >= ans) return;
94![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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)。。。。。。。
详情参阅国家集训队 黄劲松 的论文。