A
Knights of the Round Table |
模型：
给出一张图(|V| <= 1000)，求所有包含在奇数环中的点。
算法分析：
对每一个连通的子图，找出图中的割点，然后这些割点可以将图分为几部分，对于每一部分，每个点都至少在一个环中，
因此如果该部分存在一个奇数环，则该部分所有点都属于一个奇数环。
对于某一个图中是否存在奇数环的问题，只需黑白染色判断是否是二分图即可~
复杂度|V| + |E|。
注意那些度数<=1的点，我的实现方法需要预先删除这些点。
CODE
1
// Central Europe 2005, Knights of the Round Table
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <algorithm>
8#include <queue>
9
10using namespace std;
11
12const int MaxN = 1000 + 10;
13bool g[MaxN][MaxN], conv[MaxN], vis[MaxN], ins[MaxN];
14int n, m, dfs_time[MaxN], d_t, color[MaxN], low[MaxN];
15bool bad[MaxN];
16int deg[MaxN];
17
18
19void init();
20void work();
21void dfs_c(int u, int fa, int r);
22bool dfs_w(int u, int c);
23void dfs_get(int u);
24
25int main() 
{
26
for (; ;) {
27
scanf("%d%d", &n, &m);
28 if (n == 0 && m == 0) break;
29 init();
30 work();
31
}
32 return 0;
33
}
34
35void init() {
36 fill(g[0], g[MaxN], true);
37 for (int i = 0; i < n; ++i) g[i][i] = false;
38 for (; m > 0; --m) {
39 int a, b;
40 scanf("%d%d", &a, &b); --a; --b;
41 g[a][b] = false; g[b][a] = false;
42 }
43
44 fill(bad, bad + n, false);
45 queue<int> q;
46 for (int i = 0; i < n; ++i) {
47 int cnt = 0;
48 for (int j = 0; j < n; ++j)
49 if (g[i][j]) ++cnt;
50 deg[i] = cnt;
51 if (deg[i] <= 1) {
52 q.push(i); bad[i] = true;
53 }
54 }
55
56 for (; !q.empty(); q.pop()) {
57 int u = q.front();
58 for (int i = 0; i < n; ++i)
59 if (g[u][i] && !bad[i]) {
60 if (--deg[i] <= 1) {
61 q.push(i); bad[i] = true;
62 }
63 }
64 }
65
66}
67
68void work() {
69 fill(conv, conv + MaxN, false);
70 fill(vis, vis + MaxN, false);
71 d_t = 0;
72 for (int i = 0; i < n; ++i) {
73 if (bad[i]) continue;
74 if (!vis[i]) dfs_c(i, -1, i);
75 }
76
77 fill(color, color + MaxN, 0);
78 bool mark[MaxN];
79 fill(mark, mark + MaxN, false);
80 fill(vis, vis + MaxN, false);
81 int c = 10;
82 for (int i = 0; i < n; ++i) {
83 if (bad[i]) continue;
84 if (!conv[i] && !vis[i]) {
85 fill(ins, ins + MaxN, false);
86 dfs_get(i);
87 if (!dfs_w(i, c))
88 for (int j = 0; j < n; ++j) {
89 if (bad[i]) continue;
90 if (ins[j]) mark[j] = true;
91 }
92 c++;
93 }
94 }
95
96 int ans = 0;
97 for (int i = 0; i < n; ++i) if (mark[i]) ++ans;
98 cout << n - ans << endl;
99}
100
101void dfs_c(int u, int fa, int r) {
102 bool first = true;
103 dfs_time[u] = d_t++; low[u] = dfs_time[u]; vis[u] = true;
104 for (int i = 0; i < n; ++i)
105 if (g[u][i] && i != fa) {
106 if (bad[i]) continue;
107
108 if (!vis[i]) {
109 if (u == r && !first) conv[u] = true;
110 first = false;
111 dfs_c(i, u, r);
112 low[u] = min(low[u], low[i]);
113 if (low[i] >= dfs_time[u] && u != r) conv[u] = true;
114 }
115 else if (vis[i] && dfs_time[i] < dfs_time[u]) low[u] = min(low[u], dfs_time[i]);
116 }
117}
118
119bool dfs_w(int u, int c) {
120 color[u] = c;
121 for (int i = 0; i < n; ++i) {
122 if (bad[i]) continue;
123
124 if (g[u][i] && ins[i])
125 if (abs(color[i]) != c) {
126 if (!dfs_w(i, -c)) return false;
127 }
128 else if (color[i] != -c) return false;
129 }
130 return true;
131}
132
133void dfs_get(int u) {
134 ins[u] = true; vis[u] = true;
135 if (conv[u]) return;
136 for (int i = 0; i < n; ++i) {
137 if (bad[i]) continue;
138
139 if (g[u][i] && !ins[i]) dfs_get(i);
140 }
141}
142B
|
The Cow Doctor |
模型：
给出m个集合，里面存在n种元素。求这些集合中可以被其他集合并得到的（精确相等）。
m <= 200, n <= 300
算法分析：
设A能被其他集合B1, B2, ... Bi并得到，则B1, B2, ... Bi显然都属于A。
因此，我们可以找出所有属于A的集合B1, B2, ... Bi，求它们的并，看是否等于A。
复杂度O(m ^ 2 * n)，具体实现可以使用bitset :)
C
Wild West模型：
给出n个长方体(0, 0, 0) - (ai, bi, ci)，求它们并的总体积。
n, a, b, c <= 100000
算法分析：
首先想到用一个平行于xy的平面去截这些长方体。方便起见我们从最大的c开始截。
注意到保证所有长方体必定是以(0, 0, 0)点作为一个顶点的，所以平面向下移动的过程中截到的内容只增不减。
剩下的核心问题就是维护对长方形序列(0, 0) - (ai, bi)并动态报告它们的面积并。
注意到必定以(0, 0)为一个节点，所以我们每行只需要记录延伸的长度。
用线段树维护并且报告面积即可。
复杂度O(nlogn)
D
Pixel Shuffle算出目标置换，然后算出每个cycle的长度，求LCM~
Ural1024 Permutations 是一道单纯计算置换多少次可以回到原始的题。
ms就是Europe - Southwestern - 2005/2006的Pixel Shuffle，寒，欧洲人出题抄来抄去的。
uva3510
E
Find the Clones弱题，排序再扫描。
F
The Warehouse算法分析：
显然是搜索。不过似乎官方数据不会太强，如下的数据比赛的时候AC的程序就跑不出来。
8 6 1E...2.............222222................22222222..........2..2..我用BFS + SET做的。似乎还可以DFS + 剪枝。
CODE
1// Central Europe 2005, The Warehouse
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <algorithm>
8#include <set>
9
10using namespace std;
11
12const int MaxQ = 100000, dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
13struct queuenode
14{
15 int data[8][8], x, y;
16}queue[MaxQ];
17int n, sx, sy, fx, fy, init_st[8][8];
18set<queuenode> exist;
19
20void init();
21void bfs();
22bool operator<(const queuenode& a, const queuenode& b);
23
24int main()
25{
26 while (true)
27 {
28 scanf("%d%d%d", &n, &sx, &sy);
29 if (n == 0 && sx == 0 && sy == 0) break;
30 init();
31 bfs();
32 }
33 return 0;
34}
35
36void init()
37{
38 for (int i = 0; i < n; ++i)
39 {
40 char tmp[10];
41 scanf("%s", tmp);
42 for (int j = 0; j < n; ++j)
43 {
44 if (tmp[j] == 'E')
45 {
46 fx = i; fy = j; init_st[i][j] = 0;
47 continue;
48 }
49 init_st[i][j] = (tmp[j] == '.' ? 0 : tmp[j] - 48);
50 }
51 }
52}
53
54void bfs()
55{
56 int head = 0, tail = 1, step = 0;
57 copy(init_st[0], init_st[0] + 8 * 8, queue[0].data[0]);
58 queue[0].x = --sx; queue[0].y = --sy;
59 exist.clear(); exist.insert(queue[0]);
60 while (head < tail)
61 {
62 int ntail = tail;
63 ++step;
64 while (head < tail)
65 {
66 queuenode now(queue[head]);
67 for (int i = 0; i < 4; ++i)
68 {
69 now.x += dx[i]; now.y += dy[i];
70 if (now.x == fx && now.y == fy)
71 {
72 printf("%d\n", step); return;
73 }
74 if (now.x >= 0 && now.x < n && now.y >= 0 && now.y < n && now.data[now.x][now.y] != 0 && exist.find(now) == exist.end())
75 {
76 queue[ntail++] = now; exist.insert(now);
77 }
78 now.x -= dx[i]; now.y -= dy[i];
79 }
80 if (now.data[now.x][now.y] == 1)
81 {
82 ++head; continue;
83 }
84
85 for (int i = 0; i < 4; ++i)
86 {
87 now = queue[head];
88 int len = now.data[now.x][now.y];
89 bool suc = true;
90 for (int j = 1; j <= len; ++j)
91 {
92 int x = now.x + dx[i] * j, y = now.y + dy[i] * j;
93 if (x < 0 || x >= n || y < 0 || y >= n || now.data[x][y] >= 1 || (x == fx && y == fy))
94 {
95 suc = false; break;
96 }
97 now.data[x][y] = 1;
98 }
99 if (!suc) continue;
100 now.data[now.x][now.y] = 0;
101 now.x += dx[i]; now.y += dy[i];
102 if (exist.find(now) == exist.end())
103 {
104 queue[ntail++] = now; exist.insert(now);
105 }
106 }
107 ++head;
108 }
109 tail = ntail;
110 }
111 printf("Impossible.\n");
112}
113
114bool operator<(const queuenode& a, const queuenode& b)
115{
116 for (int i = 0; i < n; ++i)
117 for (int j = 0; j < n; ++j)
118 if (a.data[i][j] < b.data[i][j]) return true;
119 else if (a.data[i][j] > b.data[i][j]) return false;
120 return a.x < b.x || (a.x == b.x && a.y < b.y);
121}
122
123
G
Widget Factory算法分析：
Gauss消元，注意判断各种情况。
复杂度O(n ^ 3)
H
|
Martian Mining |
算法分析：
首先可以证明，对任一个n * m的部分，或者最后一列都用来bloggium, 或者最后一行都用来yeyenum。于是就可以dp了。
d[i, j] = 左上角的i * j部分的最大结果。
则d[i, j] = max(d[i - 1, j] + 最后一行的yeyenum和, d[i, j - 1] + 最后一列的bloggium和)
复杂度O(n * m)
I
Nuclear Plants模型：
给出一张图，求最大的平均环长度。
|V| <= 676, |E| <= 100000
算法分析：
我的算法是二分答案w, 然后将每个(u, v)边权当作w - len(u, v)来做，然后用Bellman-Ford判是否存在负权回路，存在说明可以，否则说明不可行。
另外这个题有标准算法。见CLRS
J
Word Rings模型：
经典问题了。给出一堆圆，半径只可能是r1 = 0.58 或 r2 = 1.31，求这些圆覆盖的面积和。
算法分析：
此题比赛时没有队过。
一种做法是解出所有交点连同圆的左右两边一起离散，切大条做，但传说中圆解交点误差很大……
一份解题报告中提出的做法是每次把空间一切为四然后每部分的面积加起来，递归处理。如果某一部分只和一个圆相交那么用解析的方法算出其精确值。
当每部分小到一定程度的时候用类似于撒点随机化之类的方法。