隐藏
2020 CCPC wannafly 冬令营 Day3 游记+解题报告 | Bill Yang's Blog

路终会有尽头，但视野总能看到更远的地方。

0%

2020 CCPC wannafly 冬令营 Day3 游记+解题报告

发表于 更新于 分类于 Valine：

本文章施工中……
进度[===>　　　　　　　　] 2/10 20%

A. Alternative Accounts

题目描述

Everybody knows that jiry_2 = Syloviaely.
There are $n$ different accounts on the website, and some of them competed in the recent $k$ contests. However, Mike suspects that there are lots of alternative accounts.
There are axioms believed by everyone that nobody can use two different in one contest simultaneously and each account can be owned by only one person. So different accounts without overlapping contest participation can be owned by the same person.
Mike wants to know the minimum possible number of different people behind these accounts.

题目分析

题目意思就是给三个相交的完全图，求最少染色数。
考虑一下，$A\cap B\cap C,(A\cap B)-C,(A\cap C)-B,(B\cap C)-A$都是需要染不同颜色的，否则由于两两处于完全图中，必定会染色失败。
而$A-B-C$与$B\cap C-A$是可以染相同颜色的，同理其他两种情况一样。
故答案就是：

代码

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
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

int n,k;

int main() {
	n=Get_Int();
	k=Get_Int();
	if(k<=2) {
		int ans=0;
		for(int i=1; i<=k; i++) {
			int m=Get_Int();
			for(int j=1; j<=m; j++)Get_Int();
			ans=max(m,ans);
		}
		printf("%d\n",ans);
	} else {
		set<int> S1,S2,S3,S12,S23,S13,S123;
		int m=Get_Int();
		for(int i=1; i<=m; i++)S1.insert(Get_Int());
		m=Get_Int();
		for(int i=1; i<=m; i++)S2.insert(Get_Int());
		m=Get_Int();
		for(int i=1; i<=m; i++)S3.insert(Get_Int());
		set_intersection(S1.begin(),S1.end(),S2.begin(),S2.end(),inserter(S12,S12.begin()));
		set_intersection(S2.begin(),S2.end(),S3.begin(),S3.end(),inserter(S23,S23.begin()));
		set_intersection(S1.begin(),S1.end(),S3.begin(),S3.end(),inserter(S13,S13.begin()));
		set_intersection(S12.begin(),S12.end(),S3.begin(),S3.end(),inserter(S123,S123.begin()));
		int s123=S123.size();
		int s12=S12.size()-s123,s23=S23.size()-s123,s13=S13.size()-s123;
		int s1=S1.size()-s12-s13-s123,s2=S2.size()-s12-s23-s123,s3=S3.size()-s13-s23-s123;
		printf("%d\n",s12+s23+s13+s123+max(0,max(s1-s23,max(s2-s13,s3-s12))));
	}
	return 0;
}

B. Bitset Master

题目描述

It’s well known in China that $O(n^2)$ algorithms can pass the problem with $n=10^6$ easily.
You are given a tree with $n$ vertices and $n-1$ edges $(u_1, v_1), (u_2, v_2), \dots, (u_{n-1},v_{n-1})$
For each vertex $u$,there is a set $S_u=\{u\}$ initially.
You need to perform $m$ operations. For the $i$-th operation, you are given an edge $p_i$ and let $S_{u_{p_i}}$ and $S_{v_{p_i}}$ be the union of them.
Finally, you need to find the number of sets $S(v)$ contains $u$ for each vertex $u$.

题目分析

将包含$v$的集合看做，$v$能到达的集合。
由于后合并的集合可以使前面的点到达，但先合并的集合不能使后面的点到达，故倒过来考虑，维护每个集合的大小即可统计出每个点可以到达多少个集合。

如何快速维护集合大小？

而$\left|S_u\cap S_v\right|$的大小就是上一次的$S_u,S_v$合并后的大小。

代码

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
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=500005;

int n,m,u[maxn],v[maxn],p[maxn],f[maxn],last[maxn];

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<n; i++)u[i]=Get_Int(),v[i]=Get_Int();
	for(int i=1; i<=m; i++)p[i]=Get_Int();
	for(int i=1; i<=n; i++)f[i]=1;
	for(int i=m; i>=1; i--) {
		int x=u[p[i]],y=v[p[i]];
		last[p[i]]=f[x]=f[y]=f[x]+f[y]-last[p[i]];
	}
	for(int i=1; i<=n; i++)printf("%d%c",f[i],i==n?'\n':' ');
	return 0;
}
相关文章
姥爷们赏瓶冰阔落吧~