2023.10.11测试-JZTXT

\[\text{NOIP模拟赛-2023.10.11} \]

T1 染色

给定 \(n\)，需要给整数 \(1\sim n\) 染色，使得对于所有 \(1\leq i\leq j\leq n\)，若 \(j-i\) 为质数，则 \(i,j\) 不同色。求颜色最少的染色方案，输出任意一种方案

\(1\leq n\leq 10000\)

诈骗题

观察到若 \(j=i+4\) 则 \(i,j\) 可同色，所以答案上界为 \(4\)，而样例中 \(n=7\) 的答案已经是 \(4\)，所以 \(n\ge 7\) 的全都是 \(4\)，小于 \(7\) 的打表即可

code

#pragma optimize GCC(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;

const int N=1e4+10;

int n;

int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	
//	fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
	
	scanf("%d",&n);
	if(n==1)
		printf("1\n1");
	else if(n==2)
		printf("1\n1 1");
	else if(n==3)
		printf("2\n1 1 2");
	else if(n==4)
		printf("2\n1 1 2 2");
	else if(n==5)
		printf("3\n1 1 2 2 3");
	else if(n==6)
		printf("3\n1 1 2 2 3 3");
	else
	{
		puts("4");
		for(int i=1; i<=n; i++)
			printf("%d ",i%4+1);
	} 
	
	return 0;
}