题目分析

我们需要构造一个长度为 $n$ 的 Thue 序列，该序列由字符 $\{N, O, P\}$ 组成，且满足没有任何两个相邻的子段相同。如果无法构造这样的序列，则输出空行。

方法思路

1. 深度优先搜索（DFS）+ 回溯：

   • 使用 DFS 逐步构造序列，每一步尝试填入 N、O 或 P。
   • 每次填入字符后，调用 check 函数检查当前序列是否仍满足 Thue 序列的条件。
   • 如果当前选择导致不满足条件，则回溯并尝试其他字符。

2. 检查函数 check：

   • 对于当前序列长度 $cur$，检查所有可能的相邻子段是否相等。
   • 子段长度 $len$ 从 $1$ 到 $\lfloor \frac{cur+1}{2} \rfloor$。
   • 对于每个 $len$，比较两个长度为 $len$ 的相邻子段是否相同。

3. 提前计算：

   • 由于 $n \leq 5000$，可以预先计算出长度为 $5000$ 的 Thue 序列，然后根据输入的 $n$ 截取前 $n$ 个字符输出。

解决代码

#include <iostream>
using namespace std;
const int maxN=5000;
int n,ok,a[maxN+10];
 
bool check(int cur)
{
	for(int len=1;len<=(cur+1)/2;++len){
		int p=cur-2*len+1;
		int q=cur-len+1;
		while(a[p]==a[q]&&q<=cur)
			++p,++q;
		if(q>cur)
			return false;	
	}
	return true;		
}
 
void dfs(int cur)
{
	if(cur>maxN){
		ok=1;
		return ;
	}
	for(int i=0;i<3&&!ok;++i){
		a[cur]=i;
		if(check(cur))
			dfs(cur+1);
	}	
}
 
int main()
{
	ok=0;
	dfs(0);
	while(scanf("%d",&n)==1&&n){
		for(int i=0;i<n;++i)
			if(a[i]==0) putchar('N');
			else if(a[i]==1) putchar('O');
			else putchar('P');		
		puts("");
	}
	return 0;	
}