解题报告貌似鸽了好几天了，毕竟是晚上爆肝打的比赛，第二天早上起来还要 % 拟 ……
其实之前还有场 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(){}
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(){}
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;
}
|
