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