HDU5943-Kingdom of Obsession
2017-07-03 09:29:12         来源：wang_128的博客

# Kingdom of Obsession

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1162Accepted Submission(s): 356

Problem Description There is a kindom of obsession, so people in this kingdom do things very strictly.
They name themselves in integer, and there arenpeople with their id continuous(s+1,s+2,?,s+n)standing in a line in arbitrary order, be more obsessively, people with idxwants to stand atythposition which satisfy
xmody=0
Is there any way to satisfy everyone's requirement?
Input First line contains an integerT, which indicates the number of test cases.
Every test case contains one line with two integersn,s.
Limits
1≤T≤100.
1≤n≤109.
0≤s≤109.
Output For every test case, you should output'Case #x: y', wherexindicates the case number and counts from1andyis the result string.
If there is any way to satisfy everyone's requirement,yequals'Yes', otherwiseyequals'No'.
Sample Input

2 5 14 4 11

```#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define LL long long
const int INF=0x3f3f3f3f;

int n,ss;
int x[559],y[559];
int s[559],nt[260009],e[260009];
int visit[559];

bool path(int k)
{
for(int i=s[k]; ~i; i=nt[i])
{
int ee=e[i];
if(!visit[ee])
{
visit[ee]=1;
if(y[ee]==-1||path(y[ee]))
{
y[ee]=k;
x[k]=ee;
return 1;
}
}
}
return 0;
}

void MaxMatch()
{
int ans=0;
memset(x,-1,sizeof x);
memset(y,-1,sizeof y);
for(int i=1; i<=n; i++)
{
if(x[i]==-1)
{
memset(visit,0,sizeof visit);
if(path(i)) ans++;
}
}
if(ans==n) printf("Yes\n");
else printf("No\n");
}

int main()
{
int t,cas=0;
scanf("%d",&t);
while(t--)
{
printf("Case #%d: ",++cas);
scanf("%d%d",&n,&ss);
if(ss<=1)
{
printf("Yes\n");
continue;
}
if(ss550)
{
printf("No\n");
continue;
}
int cnt=1;
memset(s,-1,sizeof s);
for(int i=ss+1; i<=ss+n; i++)
for(int j=1; j<=n; j++)
if(i%j==0) nt[cnt]=s[i-ss],s[i-ss]=cnt,e[cnt++]=j;
MaxMatch();
}
return 0;
}```