题解 P3279 【[SCOI2013]密码 】

· · 题解

【题解】密码 [SCOI2013] [P3279]

\mathcal{My}\ \mathcal{Blog}

传送门：密码 \text{[SCOI2013] [P3279]}

【题目描述】

已知某长为 n (n\leqslant 10^5) 的字符串以每个位置/空隙为中心的最长回文串长度，现需构造一个字典序最小的合法字符串。

【分析】

神奇的 \text{manacher} 反...反演？？O...Orz

【学习笔记】字符串—马拉车（\text{Manacher}）

万事不决先想暴力，直接上冰茶姬维护字符相同的位置集合，再开一个链表记录一定不相等的点对，以每个点 i 为中心向两边无脑枚举至半径 r_i，依次合并 i-j+1 和 i+j-1 (1\leqslant j \leqslant r_i)，然后在 i-r_i,i+r_i 之间连一条双向边，最后从左至右依次枚举，每次找最小合法字符即可。

貌似是 O(n^2) 的，考虑用类似 \text{manacher} 的方法进行优化：对于一个已知的回文子串 [L,R]，由于所有的 i\in[L,mid] 都已经作为中心点扫描 merge 过了，所以对于 i'\in[mid+1,R] 中 j \leqslant R-i'+1 的部分可以不用再次扫描。

其原理和普通 \text{manacher} 相同，时间复杂度亦为 O(n)（冰茶姬被忽略了QAQ）

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,x,o,A[N<<1],f[N<<1],co[N],fa[N],head[N],judge[30];
struct QAQ{int to,next;}a[N<<2];//注意链表要开4N
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void merge(Re x,Re y){if((x=find(x))!=(y=find(y)))fa[x]=y;}
int main(){
//  freopen("123.txt","r",stdin);
    in(n),m=n<<1|1;
    for(Re i=1;i<=n;++i)fa[i]=i;
    for(Re i=1;i<=n;++i)in(x),A[i<<1]=x;
    for(Re i=1;i<n;++i)in(x),A[i<<1|1]=x;
    for(Re i=2,mid=0,r=0;i<m;++i){
        f[i]=(i<=r?min(f[(mid<<1)-i],r-i+1):1);
        while(f[i]-1<A[i]){//f[i]-1才是以i为中心的实际最长回文串长度
            ++f[i];
            if(!(i-f[i]+1&1))merge(i-f[i]+1>>1,i+f[i]-1>>1);//对于奇点(辅助点)就不要merge了
        }
        add(i-f[i]>>1,i+f[i]>>1),add(i+f[i]>>1,i-f[i]>>1);//这里必定是偶点，可以直接除2进行连边
        if(i+f[i]-1>r)mid=i,r=i+f[i]-1;
    }
//    for(Re i=2;i<=m;i+=2)printf("%d ",f[i]-1);puts("");
    for(Re i=1;i<=n;++i)if(!co[find(i)]){
        memset(judge,0,sizeof(judge));
        for(Re j=head[i];j;j=a[j].next)judge[co[find(a[j].to)]]=1;//i对立点的颜色都不能选
        for(Re j=1;j<=26&&!co[find(i)];++j)if(!judge[j])co[find(i)]=j;
    }
    for(Re i=1;i<=n;++i)printf("%c",'a'+co[find(i)]-1);
}