首页 > 代码库 > hdu 5943(素数间隔+二分图匹配)
hdu 5943(素数间隔+二分图匹配)
Kingdom of Obsession
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 200 Accepted Submission(s): 64
Problem Description
There is a kindom of obsession, so people in this kingdom do things very strictly.
They name themselves in integer, and there are n people with their id continuous (s+1,s+2,?,s+n) standing in a line in arbitrary order, be more obsessively, people with id x wants to stand at y position which satisfy
Is there any way to satisfy everyone‘s requirement?
They name themselves in integer, and there are n people with their id continuous (s+1,s+2,?,s+n) standing in a line in arbitrary order, be more obsessively, people with id x wants to stand at y position which satisfy
xmody
Is there any way to satisfy everyone‘s requirement?
Input
First line contains an integer T, which indicates the number of test cases.
Every test case contains one line with two integers n, s.
Limits
1≤T.
1≤n≤109.
0≤s≤109.
Every test case contains one line with two integers n, s.
Limits
1≤T.
1≤n≤109.
0≤s≤109.
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 y equals ‘No‘.
If there is any way to satisfy everyone‘s requirement, y equals ‘Yes‘, otherwise y equals ‘No‘.
Sample Input
2
5 14
4 11
Sample Output
Case #1: No
Case #2: Yes
Source
2016年中国大学生程序设计竞赛(杭州)
这个题比赛的时候想到了素数出现两次就不能匹配,但是没想到素数间隔(潜意识认为20亿以内的素数肯定间隔很大).
20亿内两个素数之间最大间隔不会超过300,所以超过600直接输出No.所以解法就是小数据二分图匹配,大数据直接输出No.防止区间相交,要特判一下n,s的大小.
#include <stdio.h> #include <algorithm> #include <string.h> #include <math.h> using namespace std; typedef long long LL; const int N = 2016; int s,n; int graph[N][N]; int linker[N]; bool vis[N]; bool dfs(int u){ for(int i=1;i<=n;i++){ if(graph[u][i]==1&&!vis[i]){ vis[i] = true; if(linker[i]==-1||dfs(linker[i])){ linker[i] = u; return true; } } } return false; } int main() { int t = 1,tcase; scanf("%d",&tcase); while(tcase--){ scanf("%d%d",&s,&n); if(s<n) swap(s,n); if(n>1000) { printf("Case #%d: No\n",t++); continue; } memset(graph,0,sizeof(graph)); int res = 0; for(int i=1;i<=n;i++){ int t = i+s; for(int j=1;j<=n;j++){ if(t%j==0) { graph[i][j] = 1; } } } memset(linker,-1,sizeof(linker)); for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(dfs(i)) res++; } if(res==n){ printf("Case #%d: Yes\n",t++); }else printf("Case #%d: No\n",t++); } return 0; }
hdu 5943(素数间隔+二分图匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。