【解题报告】 Codeforces Round 599 (Div. 2)

解题报告貌似鸽了好几天了,毕竟是晚上爆肝打的比赛,第二天早上起来还要 % 拟 ……
其实之前还有场 Div. 3 ,不过打的太烂就不写解题报告了……

先是掉分经过:
开场 15min 切 A,B1 签到不多说,然后去看 B2 ,觉得它不显然;就去看 C 题,然后觉得这个东西貌似可以分解质因数然后搞一搞,结果后来代码一直锅掉,调了将近一个小时才过……期间去看 D 题,也没有什么本质的想法,然后就睡觉去了,大概在 0:20 a.m. 左右,目测掉分预定。
第二天早上起来发现 C 题居然没锅,然后就神奇的 rating +19 ,不过依然是 $\text{Specialist}$ 。

A. Maximum Square

Source

签到题。当时切了 C 题去 room 里砍人,居然发现这题有人写二分……无言以对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int CN = 2e3+3;
int read(){/* omitted */}
int q,n,a[CN];
int main(){
q = read();
while(q--){
n = read(); for(int i=1;i<=n;i++) a[i] = read();
for(int i=n;i;i--){
int cnt = 0;
for(int j=1;j<=n;j++) if(a[j] >= i) cnt++;
if(cnt >= i) {printf("%d\n",i); break;}
}
}
return 0;
}

B1. Character Swap (Easy Version)

Source

依然签到。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int CN = 2e4+4;
int read(){/* omitted */}
int k,n; char s[CN],t[CN];
int main(){
k = read();
while(k--){
n = read(); cin>>s>>t;
int cnt = 0;
for(int i=0;i<n;i++) if(s[i] != t[i]) cnt++;
if(cnt != 2) printf("No\n");
else{
int p[20],q = 0;
for(int i=0;i<n;i++) if(s[i] != t[i]) p[q++] = i;
swap(s[ p[0] ], t[ p[1] ]);
cnt = 0;
for(int i=0;i<n;i++) if(s[i] != t[i]) cnt++;
if(!cnt) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}

B2 不会,skip 。

C. Tile Painting

Source

考虑有哪些格子的颜色相同,不难发现这个东西跟它的质因子有关系。
从一个点出发,我们应该筛掉从该点出发,以 n 的任一质因子为“距离”能到达的所有点,这些点的颜色相同;然后下一次我们应该再去找一个没有被筛过的点重复上述过程。问题的本质在于“没有被筛过的点”我们能找到几个。

不难发现如果一个数字只有一个质因子 p ,那么这样的点我们有 p 个,即 1~p ;若其存在两个或更多的质因子,那么看起来从第一个点开始就能筛掉所有点,于是答案是 1 .

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
#define LL long long
LL n,p[101];
void div(LL x){
for(LL k=2;k*k<=x;k++){
if(!(x % k)) p[ ++p[0] ] = k;
while(!(x % k)) x /= k;
}
if(x > 1) p[ ++p[0] ] = x;
}
int main()
{
scanf("%I64d",&n);
if(n == 1){
printf("1");
return 0;
}
div(n);
if(p[0] == 1) printf("%I64d",p[1]);
else printf("1");
return 0;
}

D. 0-1 MST

Source

显然连 0 边更优,也就是说我们只在迫不得已的情况下去连 1 边。考虑在图上只保留 0 边,那么显然一个联通块里面我们是不需要连 1 边的。把每个联通块整体考虑,则需要连 1 边的数量为联通块数 -1 。

上述过程大力搜索实现显然是不行的,考虑用并查集维护联通性。我们怎么判定一个点属于一个联通块?假设某一联通块的大小为 sz ,那么一个点向它连的 1 边的数量(记作 ct )是可以统计的,而该点和此联通块一共有 sz 条边相连;当 sz > ct 时,即可推出该点与联通块之间有 0 边。

可是上述过程大力去做还是 O(n^2) 的,考虑到一个联通块只需要被合并一次,于是对于所有找到的联通块,只记录其中一个点进行合并就好了,也就是把该联通块在并查集中的根记下来。因为原图上 0 边很多,也就是说联通块个数很少,所以这个想法就会跑得很快。

最后的答案是并查集中根的个数 -1,其中根的个数即为联通块数。考虑到我们此前维护的根可能被合并,也就是说有些根 gg 掉了,所以最后还得再统计一下根的数量。

代码:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

const int CN = 1e5+5;

class dsu{
public: int fa[CN],sz[CN]; vector<int> rt;
dsu() {for(int i=1;i<CN;i++) fa[i]=i,sz[i]=1;}
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
bool exm(int x,int y) {return find(x) != find(y);}
void merge(int x,int y) {x = find(x); y = find(y); sz[y] += sz[x]; fa[x] = y;}
}co;

class fs{
public: int to,nxt; void init(int t,int n) {to=t;nxt=n;}
}E[CN * 21];
int hd[CN],ecnt = 0;
void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

int n,m;

int ve[CN];
int ct(){
co.rt.push_back(1);
for(int i=2;i<=n;i++){
memset(ve, 0, sizeof(ve));
for(int k=hd[i];k;k=E[k].nxt){
int v = E[k].to;
if(v < i) ve[ co.find(v) ]++;
}
int cn = co.rt.size();
for(int j=0;j<cn;j++){
int r = co.rt[j]; r = co.find(r);
if(co.sz[r] > ve[r] && co.exm(i, r)) co.merge(i, r);
}
if(co.find(i) == i) co.rt.push_back(i);
}
int cnt = 0;
for(int i=1;i<=n;i++) if(co.find(i) == i) cnt++;
return cnt;
}

int main()
{
scanf("%d%d",&n,&m);
while(m--){
int u,v; scanf("%d%d",&u,&v);
add(u, v); add(v, u);
}
printf("%d",ct() - 1);
return 0;
}

$$ - - - - \mathcal{End} - - - - $$


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×