【2020.11.28提高组模拟】T1染色(color)

【2020.11.28提高组模拟】T1染色(color)

题目

题目描述

给定 (n)，你现在需要给整数 (1) 到 (n) 进行染色，使得对于所有的 (1leq i<jleq n)，若 (i - j) 为质数，则 (i) 和 (j) 不同色。
求出颜色尽可能少的染色方案。如果有多种方案，输出任意一种即可。

输入格式

第一行一个整数 (n)。

输出格式

第一行一个整数 (k)，表示颜色数。
第二行 (n) 个整数 (col_i)（(1 leq col_i leq k)），表示 (i) 的颜色。

数据范围

对于(30\%)的数据，(n leq 10)；
对于 (60\%) 的数据，(n leq 20)；
对于 (100\%) 的数据，(n leq 10^4)。

时空限制

​时间限制：1s
​空间限制：128MB

题解

规律题
(n <8)直接暴力
(n geq8)：(col_i=(i-1)\%4+1)
证明：
质数可以分为(2)和奇质数，如果按照奇偶性染色，则可以满足所有奇质数。但因为2，所以要按照(mod 4)方法染色
考虑答案是否有可能小于4？考虑(1,3,6,8)，两两之间差都是质数，因此答案不能为3
综上：(n <8)直接暴力，(n geq8)：(col_i=(i-1)\%4+1)

Code

#include<cstdio>
#include<cstring>
using namespace std;
int n,ans,s[10],ans1[10];
bool bj,p[100],color[10];
bool judge()
{
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			if (p[i-j]&&s[i]==s[j]) return false;
	return true;
}
void dg(int x)
{
	if (x>n)
	{
		if (judge())
		{
			int sum=0;
			for (int i=1;i<=4;++i)
				if (color[i]) ++sum;
			if (sum<ans)
			{
				ans=sum;
				for (int i=1;i<=n;++i)
					ans1[i]=s[i];
			}
		}
		return;
	}
	for (int i=1;i<=4;++i)
	{
		s[x]=i;
		bool bz=color[i];
		color[i]=true;
		dg(x+1);
		color[i]=bz;
		s[x]=0;
	}
}
int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	memset(p,true,sizeof(p));
	for (int i=2;i<=8;++i)
		for (int j=2;j<=8;++j)
			p[i*j]=false;
	p[0]=p[1]=false;
	scanf("%d",&n);
	if (n<8)
	{
		ans=10;
		dg(1);
		printf("%d
",ans);
		for (int i=1;i<=n;++i)
			printf("%d ",ans1[i]);
	}
	else
	{
		printf("4
");
		for (int i=1;i<=n;++i)
			printf("%d ",(i-1)%4+1);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}