题意
有$n$个人，编号从$s+1$到$s+n$，把他们重新排列使得每个人的编号可以整除他们所在位置的下标。问是否存在这样的排列。
做法
由于质数只能整除$1$和它本身，所以分为两种情况讨论：
- $1$到$n$中不存在它本身，即$s\geq n$，这种情况下编号为质数的人只能放在第一个位置，所以当出现两个及以上的人编号是质数，则不可能存在这样的排列。而相邻两个质数的间距不大（$1e9$范围内相邻两个质数的最大间距不会超过$1000$），所以当$n>1000$时，一定至少存在两个人的编号为质数，这个时候就是不存在的。而当$n<=1000$时，我们可以用匈牙利算法求解二分匹配问题。
- $1$到$n$中存在它本身，即$s<n$，如下所示：
| 编号 |
s+1,s+2,s+3…s+n |
| 下标 |
1,2,3…n |
由于$s<n$，所以编号的前半部分与下标的后半部分是一样的，即：
| 编号 |
s+1,s+2…n,n+1…s+n |
| 下标 |
1,2,3…s,s+1…n-1,n |
就将前$n-s$个人放在下标为$s+1$到$n$的位置，还剩下：
| 编号 |
n+1,n+2…s+n |
| 下标 |
1,2,3…s |
也就相当于把n与s的值交换了一下，变成了第一种情况的求解。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn(1e5+5);
ll T,n,s,match[maxn],mark[maxn];
bool vis[maxn];
ll top;
struct Vertex
{
ll first;
}V[maxn];
struct Edge
{
ll v, next;
}E[maxn];
void init()
{
memset(V, -1, sizeof(V));
top = 0;
memset(match, 0, sizeof(match));
}
void add(ll u, ll v)
{
E[top].v = v;
E[top].next = V[u].first;
V[u].first = top++;
}
bool maxmatch(ll u)
{
ll v;
for(ll j=V[u].first;~j;j=E[j].next)
{
v=E[j].v;
if(!vis[v])
{
vis[v]=1;
if(!match[v]||maxmatch(match[v]))
{
match[u]=v;
match[v]=u;
return true;
}
}
}
return false;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
for(int t=1;t<=T;t++){
cin>>n>>s;
if(s<n){
swap(s,n);
}
if(n>1000){
cout<<"Case #"<<t<<": No\n";
}else{
ll num=0;
init();
for(ll i=s+1;i<=s+n;i++){
for(ll j=1;j<=n;j++){
if(i%j==0){
add(i-s,j+n);
add(j+n,i-s);
}
}
}
for(ll i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(maxmatch(i)){
num++;
}
}
if(num==n){
cout<<"Case #"<<t<<": Yes\n";
}else{
cout<<"Case #"<<t<<": No\n";
}
}
}
}
|
return 0;
本文链接：
https://luojinrong.github.io/2019/10/13/hdu-5943-二分匹配/
