题解：P16924 「LAOI-13」萌萌题

· · 题解

显然，a 中必然存在长为 1 的回文子串，且若存在长为 i+2 的回文串，则必有长度为 i 的回文串。

所以，对于满足条件的 S，必存在一个 i\ge 1，使 S 中的元素为 1,2,\cdots,i-1,i,i+2,i+4,\cdots。

对于小于等于 i 的部分，直接构造 i 个 \texttt{1} 即可。对于其他元素，我们可以在两端对称地扩展若干个相同元素，这样即可构造出一个长度为 s_n 的序列，显然这是最短的。

但我们还需要保证加入的这些元素不会产生长度不属于 S 的回文串。这可以通过对 i 的奇偶性分类讨论：

时间复杂度 O(\sum n)。 ::::success[AC 代码]

#include <iostream>
#include <algorithm>
using namespace std;
int a[200001];
int main() {
    int T,v,n,i,j;
    cin>>T>>v;
    while(T--) {
        cin>>n;
        for(i=1;i<=n;i++) cin>>a[i];
        if(a[1]!=1) {cout<<"No\n";continue;}
        for(i=2;i<=n&&a[i]==i;i++);
        for(j=i;j<=n;j++) if(a[j]!=a[j-1]+2) break;
        if(j<=n) {cout<<"No\n";continue;}
        cout<<"Yes ";
        for(j=n-i;j>=0;j--) cout<<(i&1?j>>1&1:j&1);
        for(j=1;j<i;j++) cout<<1;
        for(j=0;j<=n-i;j++) cout<<(i&1?j>>1&1:j&1);
        cout<<'\n';
    }
    return 0;
}

:::: AC 记录。