CS academy Round 66

假期里的第二套。。。

题目链接,A、B、C都很水。

D Flipping Matrix

题意是给出一个$N*N$的01格子,可以交换任意两行,任意两列。问最终可否形成对角线都为1的矩形。并给出交换方案。

这里只需考虑交换任意两行即可。之前知乎上有一个问题就是判定是否存在$N$个$1$使得其在矩阵的不同行不同列。问题链接

若val[i][j]=1,i到j建一条边。最终跑二分图匹配。记录最终匹配情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
int n;
int vis[maxn];
bool mat[maxn][maxn];
int left_match[maxn],right_match[maxn];
int findmatch(int x)
{
if(vis[x])
{
return false;
}
vis[x] = true;
for(int i=1;i<=n;i++)
{
if(mat[x][i] && left_match[i] == 0)
{
right_match[x] = i;
left_match[i] = x;
return true;
}
}
for(int i=1;i<=n;i++)
{
if(mat[x][i] && findmatch(left_match[i]))
{
right_match[x] = i;
left_match[i] = x;
return true;
}
}
return false;
}
map<pair<int,int>,int>hax;
void solve()
{
sa(n);
repp(i,1,n)
{
repp(j,1,n)
{
sa(mat[i][j]);
}
}
memset(left_match,0,sizeof(left_match));
memset(right_match,0,sizeof(right_match));
bool flag = true;
do{
flag = false;
for(int i=1;i<=n;i++)
{
vis[i] = 0;
}
for(int i=1;i<=n;i++)
{
if(right_match[i]==0 && findmatch(i))
{
flag = true;
}
}
}while(flag);
int k = 0;
repp(i,1,n)
{
k += right_match[i] != 0;
}
if(k != n)
{
puts("-1");
return;
}
repp(i,1,n)
{
vis[i] = i;
}
repp(i,1,n)
{
if(right_match[i]==vis[i])continue;
int j = 1;
for(;j<=n;j++)
{
if(vis[j]==right_match[i])
{
break;
}
}
cout<< "R "<<vis[j]<<" "<<vis[i]<<endl;
int t = vis[j];
vis[j] = vis[i];
vis[i] = t;
}
}

E Domino Train

题意是给出了$N$个骨牌,即$N$对数。然后你要进行N-1步操作,每个操作处理两个骨牌的前后位置,最终使得相邻骨牌数字相同最多。

这个题目又是想了很久。。。其实就跑欧拉回路就好了。。。

每一个骨牌$(A_i,B_i)$,建立一个A_i到B_i的边,然后以每一个联通块为单位处理,对于有多个度为奇数的点,连一条边,然后从度为奇数的点作为起点,跑欧拉回路即可。。。

记录每一个点的最终位置,使用并查集得到处理的方案。

从答案出发感觉一切都不难,然而如何搞定真是难啊。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
int n;
map<int, int>edge[maxn];
struct f
{
int fa[maxn];
int getfa(int x)
{
if (x == fa[x])return x;
else
{
fa[x] = getfa(fa[x]);
return fa[x];
}
}
}A, L, R;
int deg[maxn];
int flag[maxn], ans[maxn], pos[maxn];
vector<int>nums[maxn];
vector<int>path;
void dfs(int x)
{
while (edge[x].size())
{
int id = edge[x].begin()->first;
int to = edge[x].begin()->second;
edge[x].erase(id);
edge[to].erase(-id);
dfs(to);
path.push_back(id);
}
}
void solve()
{
sa(n);
repp(i, 1, n)
{
A.fa[i] = i;
}
repp(i, 1, n)
{
int x, y;
sa(x), sa(y);
edge[x][i] = y;
edge[y][-i] = x;
deg[x] ++;
deg[y] ++;
A.fa[A.getfa(x)] = A.getfa(y);
}
repp(i, 1, n)
{
nums[A.getfa(i)].push_back(i);
}
int cnt = 0;
int m = n;
repp(i, 1, n)
{
if (nums[i].size() == 0)continue;
vector<int>odd;
rep(k, 0, nums[i].size()) {
if (deg[nums[i][k]] % 2) {
odd.push_back(nums[i][k]);
}
}
while (odd.size()>2)
{
int k1 = odd.back(); odd.pop_back();
int k2 = odd.back(); odd.pop_back();
m++;
edge[k1][m] = k2;
edge[k2][-m] = k1;
}
int start = i;
if (odd.size())start = odd[0];
dfs(start);
while (path.size() != 0)
{
int id = path.back();
path.pop_back();
if (abs(id) <= n)
{
if (id<0)
{
flag[abs(id)] = 1;
}
ans[++cnt] = abs(id);
}
}
}
repp(i, 1, n)
{
L.fa[i] = i;
R.fa[i] = i;
pos[ans[i]] = i;
}
repp(i, 1, n - 1)
{
int x;
sa(x);
x = pos[x];
x = L.getfa(x);
if (x == 1)
{
int y = R.getfa(x) + 1;
printf("%d %d\n", ans[x], ans[y]);
R.fa[R.getfa(x)] = y;
L.fa[L.getfa(y)] = x;
}
else
{
int y = L.getfa(x - 1);
printf("%d %d\n", ans[y], ans[x]);
R.fa[R.getfa(y)] = x;
L.fa[L.getfa(x)] = y;
}
}
repp(i, 1, n)
{
if (i>1)printf(" ");
printf("%d", flag[i]);
}
}