HDU 5943 Kingdom of Obsession 二分图匹配+素数筛

401人浏览 / 1人评论

题目链接

  • Kingdom of Obsession
    • 这一题需要思维抽象能力,如果仅看到问题的表面(数论),则无从下手。
    • 问题的实质是将1, 2, 3, ..., n这n个数(记为y)与s+1, s+2, s+3, ... s+n这n个数(记为x)建立一一映射,并且每个映射都满足x%y=0。
    • x%y=0可以写成x=ky (k>0, k∈N),即x为y的倍数。
    • 若s<n,则x与y有一部分相同,我们可以将相同的部分与自身映射,使sub=n-s, n-=sub, s+=sub(此操作等价于swap(s,n)),问题就被简化为x与y不重合的情况。
    • 既然x与y无交集部分,且x为y的倍数,说明x集合中不可以同时有两个素数(一个素数可以使其%1)。本地用欧拉筛筛出所有1e9内素数,统计出相邻素数之间的最大间隔,可知相邻素数之间间隔不会超过1000。
    • 所以,若n≥1000,则一定无解。
    • n<1000时,将x与y两个集合看成二分图,两点之间存在边的条件为x%y=0。用匈牙利算法可以计算出二分图的最大匹配数。若最大匹配数≠n,则无解,否则有解。

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool g[1010][1010];
int linker[1010],uN,vN;
bool used[1010];
bool dfs(int u)
{
	for(int v=0;v<vN;++v)
	{
		if(g[u][v]&&!used[v])
		{
			used[v]=true;
			if(linker[v]==-1||dfs(linker[v]))
			{
				linker[v]=u;
				return true;
			}
		}
	}
	return false;
}
int hungary()
{
	int res=0;
	memset(linker,-1,sizeof(linker));
	for(int u=0;u<uN;++u)
	{
		memset(used,false,sizeof(used));
		if(dfs(u))
		{
			++res;
		}
	}
	return res;
}
int main()
{
	int T,kcase=0;
	scanf("%d",&T);
	while(T--)
	{
		int n,s;
		scanf("%d%d",&n,&s);
		if(n>s)
		{
			swap(n,s);
		}
		if(n>1000)
		{
			printf("Case #%d: No\n",++kcase);
			continue;
		}
		memset(g,false,sizeof(g));
		uN=vN=n;
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				if(!((s+j)%i))
				{
					g[j-1][i-1]=true;
				}
			}
		}
		if(hungary()==n)
		{
			printf("Case #%d: Yes\n",++kcase);
		}
		else
		{
			printf("Case #%d: No\n",++kcase);
		}
	}
	return 0;
}

全部评论