自动搬运

查看原文

来自洛谷，原作者为

	辰星凌 时过而不知泪已落 —散华礼弥

搬运于2025-08-24 21:47:16，当前版本为作者最后更新于2020-04-12 21:57:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【题解】密码 [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);
}