题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5943
题意:n
个人编号为[s+1,s+n]
,有n
个座位编号为[1,n]
,编号为i
的人只能坐到编号为它的约数的座位,问每个人是否都有位置坐。
首先,可以肯定的是素数编号的人只能做到自己的编号上或者是1上,那么假如[s+1,s+n]区间内出现了两个以上的素数,那么整个情况是无解的。
其次,假如s<n的话,可以把[s+1,s+n]直接放到[s+1,s+n]上,剩下的将会是s个人和s个座位,人的编号是[n+1,n+s],座位的编号是[s+1,s+n],所以直接给s和n交换一下就行。
我断定1000个数之间一定会出现至少两个素数,因此当n>1000的时候就是无解了。
接下来就是O(n^2),按照能否整除建图了,跑出最大匹配,看看跟n是不是相等就行了。
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
int nu, nv;
int G[maxn][maxn];
int linker[maxn];
bool vis[maxn];
int s, n; bool dfs(int u) {
for(int v = ; v <= nv; v++) {
if(G[u][v] && !vis[v]) {
vis[v] = ;
if(linker[v] == - || dfs(linker[v])) {
linker[v] = u;
return ;
}
}
}
return ;
} int hungary() {
int ret = ;
memset(linker, -, sizeof(linker));
for(int u = ; u <= nu; u++) {
memset(vis, , sizeof(vis));
if(dfs(u)) ret++;
}
return ret;
} int main() {
// freopen("in", "r", stdin);
int T, _ = ;
scanf("%d", &T);
while(T--) {
scanf("%d %d", &s, &n);
memset(G, , sizeof(G));
printf("Case #%d: ", _++);
if(s < n) swap(s, n);
if(n > ) {
puts("No");
continue;
}
nu = * n, nv = n;
for(int i = ; i <= n; i++) {
for(int j = ; j <= n; j++) {
if((s + i) % j == ) G[i+n][j] = ;
}
}
if(hungary() == n) puts("Yes");
else puts("No");
}
return ;
}