Problem 2. number題解

number：數學+二分圖匹配

首先，如果S<N,那么S+1，S+2...N這些數直接放在S+1,S+2...N的位置上(如果其他數x放在這些位置上面，這些數不放在對應位置，那么x一定能放在這些數放的位置，所以直接交換即可)所以可以直接將S和N調換，縮小N。接著看N個連續的數，如果這里面有兩個素數，則肯定無解，而在1e9的范圍內，素數間隔最大是低于600的，我們就可以通過二分圖匹配（s+i與其因數建邊）求出最大匹配，若最大匹配為N，則為Yes。實際上，能滿足的N其實最大為30多，而菜菜的jyb只枚舉到了很多20多的答案，所以為了卡掉暴力匹配的做法（但還是很良心地給了5個點），不得不多設置了很多數據組數。

迷之數學規律，n>600時就會至少有兩個素數出現，不符合題意，然后我們一下子就將1e9的數據變成了n<600，之后進行裸的二分圖匹配即可，代碼如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const int N=605;
bool vis[maxn];
int match[maxn];
int ditu[N][N];
int T,n,s;
bool dfs(int x)//匈牙利算法
{if(x==0){return false;}for(int i=1;i<=n;i++){if(!vis[i] && ditu[i][x]){vis[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}}return false;
}
int main()
{freopen("number.in","r",stdin);freopen("number.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d%d",&n,&s);if(s<n){swap(s,n);}if(n>600){printf("No\n");continue;}memset(ditu,0,sizeof(ditu));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if((i+s)%j==0)//能夠整除的數之間建邊，這段代碼的靈魂所在{ditu[i][j]=1;}}}memset(match,0,sizeof(match));int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(dfs(i)){ans++;}}if(ans==n){printf("Yes\n");}else{printf("No\n");}}return 0;
}

?