首页 > 代码库 > hdu 5943 Kingdom of Obsession 二分图匹配+素数定理
hdu 5943 Kingdom of Obsession 二分图匹配+素数定理
Kingdom of Obsession
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
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 yth 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 yth position which satisfy
xmody=0
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≤100 .
1≤n≤109 .
0≤s≤109 .
Every test case contains one line with two integers n , s .
Limits
1≤T≤100 .
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年中国大学生程序设计竞赛(杭州)
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14const int N=2e5+10,M=1e6+10,inf=1e9+10,mod=1e9+7;const ll INF=1e18+10;int prime(int n){ if(n<=1)return 0; if(n==2)return 1; if(n%2==0)return 0; int k, upperBound=n/2; for(k=3; k<=upperBound; k+=2) { upperBound=n/k; if(n%k==0)return 0; } return 1;}const int MAXN=1505;map<int,int>linker;map<int,int>used;vector<int>mp[MAXN];int uN;bool dfs(int u){ for(int i=0;i<mp[u].size();i++) { if(!used[mp[u][i]]) { used[mp[u][i]]=1; if(linker[mp[u][i]]==0||dfs(linker[mp[u][i]])) { linker[mp[u][i]]=u; return true; } } } return false;}int hungary(){ int u; int res=0; linker.clear(); for(u=1;u<=uN;u++) { used.clear(); if(dfs(u)) res++; } return res;}int main(){ int T,cas=1; scanf("%d",&T); while(T--) { for(int i=0;i<MAXN;i++) mp[i].clear(); int n,s; scanf("%d%d",&n,&s); if(n>s)swap(n,s); int p=0; for(int i=s+1; i<=s+n; i++) { if(prime(i)) { p++; if(p>=2)break; } } printf("Case #%d: ",cas++); if(p>=2) { printf("No\n"); continue; } for(int i=s+1; i<=s+n; i++) { for(int j=1; j<=n; j++) { if(i%j==0) { mp[j].push_back(i); } } } uN=n; int hh=hungary(); if(hh==n) printf("Yes\n"); else printf("No\n"); } return 0;}
hdu 5943 Kingdom of Obsession 二分图匹配+素数定理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。