HDU——5943 Kingdom of Obsession(二分图匹配)

There is a kindom of obsession, so people in this kingdom do things very strictly. 

They name themselves in integer, and there are nn people with their id continuous (s+1,s+2,⋯,s+n) standing in a line in arbitrary order, be more obsessively, people with id xx wants to stand at ythyth position which satisfy 

xmody=0



Is there any way to satisfy everyone's requirement?

Input

First line contains an integer TT, which indicates the number of test cases. 

Every test case contains one line with two integers nn, ss. 

Limits 
1≤T≤100. 
1≤n≤10^9. 
0≤s≤10^9.

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string. 

If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise yequals 'No'.

Sample Input

2
5 14
4 11

Sample Output

Case #1: No
Case #2: Yes

题意:给定s,n,把s+1,s+2,..s+n这n个数填到1,2,...,n里,要求X只能填到X的因子的位置。(即X%Y=0,那么X才能放在Y位置)问是否能够放满。就是s+1%(1~n)==0,中的一个数,然后全部对应起来~~

题解:二分图匹配,自己太菜,接触的少,没做出来,打表可以发现n,s互换位置结果一样,那么叫n尽量小,就保证数据量小了,而且1~n中不能有两个质数,因为质数只有1可以匹配,两个就不行了,可以发现两个质数最大距离约是不超过300,我保险取600~~即大于600就是No,这样就不超时了~

上代码:

#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 1e3+100;
struct hh{
	int v,nt;
}a[MAX*MAX];
int head[MAX],tot,match[MAX];
bool vis[MAX];
void init(){
	memset(head,-1,sizeof(head));
	tot=0;
}
void add(int u,int v){
	a[tot].v=v;
	a[tot].nt=head[u];
	head[u]=tot++;
}
bool dfs(int u){//匈牙利算法
	for (int i = head[u];~i;i=a[i].nt){
		int v=a[i].v;
		if(!vis[v]){
			vis[v]=1;
			if(match[v]==-1||dfs(match[v])){
				match[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int bm(int n){//匈牙利算法
	int res=0;
	memset(match,-1,sizeof(match));
	for (int u = 1; u <= n;u++){
		memset(vis,0,sizeof(vis));
		if(dfs(u)) res++;
	}
	return res;
}
int main(){
	int t,n,s;
	int cas=1;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&s);
		if(n>s) swap(n,s);
		if(n>600) {//大于600直接是No
			printf("Case #%d: No\n",cas++);
			continue;
		}
		init();
		for (int i = s+1; i <= s+n;i++){
			for (int j = 1; j <= n;j++){
				if(i%j==0){
					add(i-s+n,j);
					add(j,i-s+n);
				}
			}
		}
		if(bm(2*n)==2*n) printf("Case #%d: Yes\n",cas++);//看是否全部匹配
		else printf("Case #%d: No\n",cas++);
	}
	return 0;
} 

 

全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务