A
Knights of the Round Table |
模型：
給出一張圖(|V| <= 1000)，求所有包含在奇數(shù)環(huán)中的點。
算法分析：
對每一個連通的子圖，找出圖中的割點，然后這些割點可以將圖分為幾部分，對于每一部分，每個點都至少在一個環(huán)中，
因此如果該部分存在一個奇數(shù)環(huán)，則該部分所有點都屬于一個奇數(shù)環(huán)。
對于某一個圖中是否存在奇數(shù)環(huán)的問題，只需黑白染色判斷是否是二分圖即可~
復(fù)雜度|V| + |E|。
注意那些度數(shù)<=1的點，我的實現(xiàn)方法需要預(yù)先刪除這些點。
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
算法分析：
設(shè)A能被其他集合B1, B2, ... Bi并得到，則B1, B2, ... Bi顯然都屬于A。
因此，我們可以找出所有屬于A的集合B1, B2, ... Bi，求它們的并，看是否等于A。
復(fù)雜度O(m ^ 2 * n)，具體實現(xiàn)可以使用bitset :)
C
Wild West模型：
給出n個長方體(0, 0, 0) - (ai, bi, ci)，求它們并的總體積。
n, a, b, c <= 100000
算法分析：
首先想到用一個平行于xy的平面去截這些長方體。方便起見我們從最大的c開始截。
注意到保證所有長方體必定是以(0, 0, 0)點作為一個頂點的，所以平面向下移動的過程中截到的內(nèi)容只增不減。
剩下的核心問題就是維護(hù)對長方形序列(0, 0) - (ai, bi)并動態(tài)報告它們的面積并。
注意到必定以(0, 0)為一個節(jié)點，所以我們每行只需要記錄延伸的長度。
用線段樹維護(hù)并且報告面積即可。
復(fù)雜度O(nlogn)
D
Pixel Shuffle算出目標(biāo)置換，然后算出每個cycle的長度，求LCM~
Ural1024 Permutations 是一道單純計算置換多少次可以回到原始的題。
ms就是Europe - Southwestern - 2005/2006的Pixel Shuffle，寒，歐洲人出題抄來抄去的。
uva3510
E
Find the Clones弱題，排序再掃描。
F
The Warehouse算法分析：
顯然是搜索。不過似乎官方數(shù)據(jù)不會太強，如下的數(shù)據(jù)比賽的時候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消元，注意判斷各種情況。
復(fù)雜度O(n ^ 3)
H
|
Martian Mining |
算法分析：
首先可以證明，對任一個n * m的部分，或者最后一列都用來bloggium, 或者最后一行都用來yeyenum。于是就可以dp了。
d[i, j] = 左上角的i * j部分的最大結(jié)果。
則d[i, j] = max(d[i - 1, j] + 最后一行的yeyenum和, d[i, j - 1] + 最后一列的bloggium和)
復(fù)雜度O(n * m)
I
Nuclear Plants模型：
給出一張圖，求最大的平均環(huán)長度。
|V| <= 676, |E| <= 100000
算法分析：
我的算法是二分答案w, 然后將每個(u, v)邊權(quán)當(dāng)作w - len(u, v)來做，然后用Bellman-Ford判是否存在負(fù)權(quán)回路，存在說明可以，否則說明不可行。
另外這個題有標(biāo)準(zhǔn)算法。見CLRS
J
Word Rings模型：
經(jīng)典問題了。給出一堆圓，半徑只可能是r1 = 0.58 或 r2 = 1.31，求這些圓覆蓋的面積和。
算法分析：
此題比賽時沒有隊過。
一種做法是解出所有交點連同圓的左右兩邊一起離散，切大條做，但傳說中圓解交點誤差很大……
一份解題報告中提出的做法是每次把空間一切為四然后每部分的面積加起來，遞歸處理。如果某一部分只和一個圓相交那么用解析的方法算出其精確值。
當(dāng)每部分小到一定程度的時候用類似于撒點隨機化之類的方法。