A
Knights of the Round Table |
模型:
给出一张图(|V| <= 1000),求所有包含在奇数环中的点。
算法分析:
对每一个连通的子图,找出图中的割点,然后这些割点可以将图分为几部分,对于每一部分,每个点都至少在一个环中,
因此如果该部分存在一个奇数环,则该部分所有点都属于一个奇数环。
对于某一个图中是否存在奇数环的问题,只需黑白染色判断是否是二分图即可~
复杂度|V| + |E|。
注意那些度数<=1的点,我的实现方法需要预先删除这些点。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
CODE
1
// Central Europe 2005, Knights of the Round Table
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
#include <queue>
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
using namespace std;
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
const int MaxN = 1000 + 10;
13
bool g[MaxN][MaxN], conv[MaxN], vis[MaxN], ins[MaxN];
14
int n, m, dfs_time[MaxN], d_t, color[MaxN], low[MaxN];
15
bool bad[MaxN];
16
int deg[MaxN];
17![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
18![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
19
void init();
20
void work();
21
void dfs_c(int u, int fa, int r);
22
bool dfs_w(int u, int c);
23
void dfs_get(int u);
24![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (; ;)
{
27
scanf("%d%d", &n, &m);
28
if (n == 0 && m == 0) break;
29
init();
30
work();
31
}
32
return 0;
33
}
34![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
35![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void init()
{
36
fill(g[0], g[MaxN], true);
37
for (int i = 0; i < n; ++i) g[i][i] = false;
38![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
44
fill(bad, bad + n, false);
45
queue<int> q;
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (deg[i] <= 1)
{
52
q.push(i); bad[i] = true;
53
}
54
}
55![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
56![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (; !q.empty(); q.pop())
{
57
int u = q.front();
58
for (int i = 0; i < n; ++i)
59![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (g[u][i] && !bad[i])
{
60![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (--deg[i] <= 1)
{
61
q.push(i); bad[i] = true;
62
}
63
}
64
}
65![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
66
}
67![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void work()
{
69
fill(conv, conv + MaxN, false);
70
fill(vis, vis + MaxN, false);
71
d_t = 0;
72![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < n; ++i)
{
73
if (bad[i]) continue;
74
if (!vis[i]) dfs_c(i, -1, i);
75
}
76![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < n; ++i)
{
83
if (bad[i]) continue;
84![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (!conv[i] && !vis[i])
{
85
fill(ins, ins + MaxN, false);
86
dfs_get(i);
87
if (!dfs_w(i, c))
88![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
96
int ans = 0;
97
for (int i = 0; i < n; ++i) if (mark[i]) ++ans;
98
cout << n - ans << endl;
99
}
100![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
101![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (g[u][i] && i != fa)
{
106
if (bad[i]) continue;
107![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
108![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
119![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool dfs_w(int u, int c)
{
120
color[u] = c;
121![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < n; ++i)
{
122
if (bad[i]) continue;
123![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
124
if (g[u][i] && ins[i])
125![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
133![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void dfs_get(int u)
{
134
ins[u] = true; vis[u] = true;
135
if (conv[u]) return;
136![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (int i = 0; i < n; ++i)
{
137
if (bad[i]) continue;
138![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
139
if (g[u][i] && !ins[i]) dfs_get(i);
140
}
141
}
142![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
B
|
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 + 剪枝。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
CODE
1
// Central Europe 2005, The Warehouse
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
#include <set>
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
using namespace std;
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
const int MaxQ = 100000, dx[4] =
{-1, 0, 0, 1}, dy[4] =
{0, -1, 1, 0};
13
struct queuenode
14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
15
int data[8][8], x, y;
16
}queue[MaxQ];
17
int n, sx, sy, fx, fy, init_st[8][8];
18
set<queuenode> exist;
19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20
void init();
21
void bfs();
22
bool operator<(const queuenode& a, const queuenode& b);
23![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
24
int main()
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
26
while (true)
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
36
void init()
37![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
38
for (int i = 0; i < n; ++i)
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
40
char tmp[10];
41
scanf("%s", tmp);
42
for (int j = 0; j < n; ++j)
43![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
44
if (tmp[j] == 'E')
45![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
54
void bfs()
55![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
62
int ntail = tail;
63
++step;
64
while (head < tail)
65![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
66
queuenode now(queue[head]);
67
for (int i = 0; i < 4; ++i)
68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
69
now.x += dx[i]; now.y += dy[i];
70
if (now.x == fx && now.y == fy)
71![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
82
++head; continue;
83
}
84![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
85
for (int i = 0; i < 4; ++i)
86![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
104
queue[ntail++] = now; exist.insert(now);
105
}
106
}
107
++head;
108
}
109
tail = ntail;
110
}
111
printf("Impossible.\n");
112
}
113![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
114
bool operator<(const queuenode& a, const queuenode& b)
115![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
123![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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,求这些圆覆盖的面积和。
算法分析:
此题比赛时没有队过。
一种做法是解出所有交点连同圆的左右两边一起离散,切大条做,但传说中圆解交点误差很大……
一份解题报告中提出的做法是每次把空间一切为四然后每部分的面积加起来,递归处理。如果某一部分只和一个圆相交那么用解析的方法算出其精确值。
当每部分小到一定程度的时候用类似于撒点随机化之类的方法。