【题目描述】

SPS有n个格子，现在他要让你对这$n$个格子染色，每个格子可以染色成0~9。

因为SPS希望完美，所以他想，如果$a+b=c$，那么如果格子$a$与格子$b$颜色相同，那么格子$c$与格子$a$颜色就不能相同。

请你构造出方案。

$30: n \leq 2^{10}-1$

$60: n \leq 3^{10-1}$

$100: n \leq 25000$

【题解】

题目来源：2016-2017 CT S03E02: Codeforces Trainings Season 3 Episode 2 Problem I

当时比赛属于全程懵逼状态。

首先$n \leq 2^{10}-1$可以用暴力得出结果。

# include <stdio.h>

using namespace std;

int n, a[25010];
bool okk=0;

inline void fk(int step) {
	if(okk == 1) return;
	if(step == n+1) {
		for (int i=1; i<=n; ++i) {
			printf("%d", a[i]-1);
		}
		okk=1;
		return ;
	}
	for (int i=1; i<=10; ++i) {
		if(okk == 1) return;
		a[step] = i;
		bool ok=1;
		for (int j=1; j<=step/2+1; ++j) {
			if(a[j] == a[step-j] && a[j] == a[step]) {
				ok=0;
				break;
			}
		}
		if(!ok) continue;
		fk(step+1);
	}
}

int main() {
	scanf("%d", &n);
	fk(1);
	return 0;
}

然后黄文翰学长提供了一种康托三分集的思想。

具体就是类似于这样

121333121444444444121333121555555555555555555555555555....

是一种分形构造。很明显满足题目要求，这样就能过60%的数据啦！

# include <stdio.h>

using namespace std;

int n;
int a[60000];

inline void sf(int l, int r, int num) {
	if(l == r) {a[l] = num; return;} 
	int mid1 = l+(r-l+1)/3, mid2 = r-(r-l+1)/3; 
	//printf("%d %d %d %d\n", l, r, mid1, mid2); 
	for (int i=mid1; i<=mid2; ++i) a[i] = num;
	sf(l, mid1-1, num+1);
	sf(mid2+1, r, num+1); 
}

int main() {
	//freopen("a.txt", "w", stdout); 
	scanf("%d", &n);
	if(n<=19683) {
		sf(1, 19683, 0);
		for (int i=1; i<=n; ++i) printf("%d", a[i]);
	} else {
		for (int i=1; i<=n; ++i) printf("0");
	}
	return 0;
}

然后今天早上起来，cf上有人给了一种新的构造方法，能通过本题。

excited!!!

这样就有满分啦！

# include <stdio.h>
# include <vector>
# include <algorithm>
using namespace std;

vector<int> t[11];

int three[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};
int a[77777], n;

int main() {
	for (int i=1; i<=10; ++i) t[i].clear();
	t[1].push_back(1);
	for (int i=1; i<=9; ++i) {
		for (int j=1; j<=i; ++j) {
			int sz = t[j].size();
			for (int k=0; k<sz; ++k) 
				t[j].push_back(t[j][k]+three[i]);
			
			sort(t[j].begin(), t[j].end());
			vector<int> :: iterator iter = unique(t[j].begin(), t[j].end());
			t[j].erase(iter, t[j].end());
		}
		for (int j=(three[i]+1)/2; j<=three[i]; ++j) t[i+1].push_back(j);
	}
	for (int i=1; i<=10; ++i) {
		for (int j=0; j<t[i].size(); ++j) a[t[i][j]] = i-1;
	}
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) printf("%d", a[i]);
	return 0;
}