题目分析

我们需要构造一个长度为 $n$ 的 Thue序列，该序列由字符 $\{N, O, P\}$ 组成，且必须满足：

• 无相邻相同子段：对于序列中任意两个相邻的子段（连续子序列），它们不能完全相同。

方法思路

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

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

2. 检查函数 check：

   • 对于当前序列长度 $cur$，检查所有可能的相邻子段是否相等。
   • 子段长度 $len$ 从 $1$ 到 $\lfloor \frac{cur+1}{2} \rfloor$。
   • 对于每个 $len$，比较两个相邻子段是否相同：
     • 左子段起始位置：$p = cur - 2 \times len + 1$
     • 右子段起始位置：$q = cur - len + 1$
     • 如果两个子段完全相同，则当前序列不满足条件。

3. 预处理：

   • 由于 $n \leq 5000$，预先计算出长度为 $5000$ 的Thue序列，存储在数组 a 中。
   • 对于每个查询 $n$，直接输出数组 a 的前 $n$ 个字符。

解决代码

#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
const int MAX=100009;
typedef long long ll;
int l[MAX],r[MAX];
ll a[MAX];
int n;
stack<int>st;
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        a[0]=a[n+1]=-1;        //n+1插入-1让最后栈中元素都弹出 
        for(int i=0;i<=n+1;i++)
        {
            while(!st.empty()&&a[st.top()] > a[i])//当插入元素比栈顶元素小 
            {                                    //表示栈顶元素向右只能扩展至该元素 更新右边界 
                r[st.top()]=i;                    
                st.pop();
            }
            if(!st.empty())l[i]=st.top()+1;    //单调递增栈，因此入栈后，栈内的一个元素比插入的元素 
            st.push(i);                        //小，插入元素向左只能扩展到该处 ，更新左边界 
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            if(ans<(r[i]-l[i])*a[i])
                ans=(r[i]-l[i])*a[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}