"蔚来杯"2022牛客暑期多校训练营10

E: Reviewer Assignment

题意：有m篇论文和n个审稿人，给出每个审稿人能审的论文集合，要求每个审稿人都要审一篇论文，让你将m篇论文分给n个审稿人，并且要让每个论文都给尽量多的审稿人看。

题解：匈牙利算法，遍历每篇论文，将每篇论文分配给一个可以审这篇论文的 审稿人，总共有n个审稿人，那就重复n次循环，但是若 当前已经没有审稿人能审了，则退出循环即可。

#include 
#include 
using namespace std;
struct node{
	int to,nxt;
}edge[200000];//需要注意 总共最多有400*400=160000条边
int head[500];
int cnt=0;
int match[500];//存储 当前审稿人审那篇论文
bool st[500];
void add(int u,int v){//链式前向星存图
	edge[++cnt].to=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
bool find(int x){
	for(int i=head[x];i;i=edge[i].nxt){
		int j=edge[i].to;
		if(!st[j]){
			st[j]=1;
			if(match[j]==0||find(match[j])){
				match[j]=x;
				return true;
			}
		} 
	}
	return false;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0 ; i<n; i++){
		string str;
		cin>>str;
		for(int j=0;j<m;j++){
			if(str[j]=='1'){
				add(j+1,i+1);//若当前审稿人可以审读 此论文，则建边
			}
		}
	}
	int t=0;
	for(int i=1;i<=n;i++){//最多重复n次，为每篇论文找尽可能多的审稿人
		bool flag=0;
		for(int j=1;j<=m;j++){
			memset(st,false,sizeof st);
			if(find(j)){//若当前论文能找到一个新的审稿人
				t++;//又有一个新的审稿人获得了一篇论文
				flag=1;
			}
		}
		if(!flag)break;//若所有论文都找不到新的审稿人了，则没有必要循环了
	} 
	if(t==n){//若每个审稿人都有一篇能审的论文，则符合要求
		for(int j=1;j<=n;j++){
			printf("%d ",match[j]);
		}
	}else{//否则不符合要求
		puts("-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
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

F: Shannon Switching Game?

题意：两个人玩游戏，一个人可以在地图上移动棋子，另一个人可以删除当前节点所连的一条边，先删边，后移动，给定初始节点，和目标节点，问能否到达目标节点

题解：可倒推，若想要到达目标节点，则至少有两条路可到达目标节点，若当前节点有两条路分别可到达目标节点或者其他一定能到达目标结点的点，则该点一定可以到达目标节点，将一定能到达目标节点的点，放到一个set数组中，最后只需要查看一定能到达目标结点的点中有无初始节点即可。每向set中插入一个新的节点，就需要判断该点所连接的其他点能否也能一定到达目标节点，通过一个队列遍历即可。

代码如下：

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1e5+5;
struct node {
	int to,nxt;
} edge[2*maxn];
int head[maxn];
int cnt=0;
void add(int u,int v) {//链式前向星存边
	edge[++cnt].to=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
void solve() {
	cnt=0;
	memset(head,0,sizeof(head));//初始化链式前向星
	int n,m;
	int be,en;
	scanf("%d%d%d%d",&n,&m,&be,&en);
	for(int i=0; i<m; i++) {
		int n1,n2;
		scanf("%d%d",&n1,&n2);//存储图
		add(n1,n2);
		add(n2,n1);
	}
	queue<int>que;
	set<int>st;//set数组记录一定能到达目标结点的所有点
	st.insert(en);
	int e=en;
	for(int i=head[e]; i; i=edge[i].nxt) {//遍历目标节点所连接的所有边
		int j=edge[i].to;
		if(!st.count(j)) {//需要保证当前边所连接的点 不是已经确定能到达目标结点的点，节约时间
			que.push(j);
		}
	}
	while(que.size()) {
		int e=que.front();
		que.pop();
		int sum=0;
		set<int>tt;
		for(int i=head[e]; i; i=edge[i].nxt) {//判断该点能否到达目标节点
			int j=edge[i].to;
			if(st.count(j)) {
				sum++;
				if(sum>1)break;
			}
		}
		if(sum>1) {
			st.insert(e);
			for(int i=head[e]; i; i=edge[i].nxt) {//若该点能到达目标节点，则可以遍历周围所连接的点，看看现在的他们能否到达目标节点
				int j=edge[i].to;
				if(!st.count(j)) {
					que.push(j);
				}
			}
		}
	}
	if(st.count(be))printf("Join Player\n");//若一定能到达目标结点的中包含初始节点，则。。。
	else printf("Cut Player\n");//否则。。。
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		solve();
	}
}
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

I: Yet Another FFT Problem?

题意：给定两个序列A=($a_i$)${}_{i=1}^n$ 和 $B=(b_i{)}_{i=1}^m$，是否存在i,j,k,l使得
$$1\le i\ne j\le n,1\le k\ne l\le m;$$

$$使得|a_i-a_j|=|b_k-b_l|成立$$

题解：

​ 首先检查两个序列中是否都有重复出现的数字，若有，则结果就。。

​ 若无，则暴力，检查是否有$a_i+b_k=a_j+b_l$成立即可，注意暴力的时候记得去掉序列中重复的数字。

#include 
#include 
using namespace std;
const int maxn=1e7+10;
const int ma=1e6+10;
int c[ma],d[ma];
int a[maxn],b[maxn];
pair<int,int>g[2*maxn]; 
bool e[2*maxn];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	int n1=0,n2=0;
	int x1=0,x2=0,y1=0,y2=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(!a[x]){//若无重复，则记录当前数字
			c[n1++]=x;
			a[x]=i;
		}else{//若有重复，则记录重复的两个数字的序列号
			x1=a[x];
			x2=i;
		}
	}
	for(int i=1;i<=m;i++){//将上述操作重复到b序列上即可。
		int x;
		scanf("%d",&x);
		if(!b[x]){
			d[n2++]=x;
			b[x]=i;
		} else{
			y1=b[x];
			y2=i;
		}
	}
	if(x1&&y1){//若两个序列都有重复出现的数字，则结果有了
		printf("%d %d %d %d\n",x1,x2,y1,y2);
		return 0;
	}
	for(int i=0;i<n1;i++){//若没有，则暴力计算即可，暴力时 注意去重，就不会TLE了
		for(int j=0;j<n2;j++){
			int t=c[i]+d[j];
			if(e[t]){
				printf("%d %d %d %d\n",g[t].first,a[c[i]],g[t].second,b[d[j]]);
				return 0;
			}else{
				e[t]=1;
				g[t].first=a[c[i]];
				g[t].second=b[d[j]];
			}
		}
	}
	printf("-1\n");
}
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