题解：P3279 [SCOI2013] 密码

· · 题解

第一次场紫。

做法为贪心加上线段树维护。

Solution

首先，对于一个中心，会产生两种限制。一种为范围内的字符两两相等，另一种为范围外的两个位置字符不同。

由于要求字典序最小，考虑贪心。

从左到右依次考虑每一个位置的字符要填什么。能填字典序小的肯定填。填完以后遍历被这个位置限制的其他位置，打上标记。

这一段的代码先给出，可以稍微理解一下。

for(int j = 0;j<25;j++)
    if(!pd[i][j]){
        cout<<(ans[i]=(char)('a'+j));
        for(auto t:edge[i])
            pd[t][j]=1;
        break;
    }

但是还有相同的要求。就是对于当前的位置 i，如果有回文范围包括这个位置，并且在右半部分，就会强制与左半部分相对的位置相等。这么维护呢？我们只需要对于每一个中心将右半部分统一推平为这个中心的下标，这样就可以通过中心的下表计算出左半部分与其对应的下标，并直接赋值即可。

这里区间推平、单点查询使用的数据结构是线段树。

AC code

#include <bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
int n,x,tree[400005];
bool pd[100005][26];
char ans[100005];
vector<int> edge[100005];
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}
inline void f(int now,int k){if(!k) return;tree[now]=k;}
inline void update(int now,int l,int r,int nl,int nr,int k){
    if(l>nr||r<nl||l>r) return;
    if(l>=nl&&r<=nr){
        f(now,k);
        return;
    }
    update(lc(now),l,mid,nl,nr,k);
    update(rc(now),mid+1,r,nl,nr,k);
}
inline int query(int now,int l,int r,int x){
    if(r<x||l>x) return 0;
    if(tree[now]) return tree[now];
    if(l==r) return 0;
    return max(query(lc(now),l,mid,x),query(rc(now),mid+1,r,x));
}
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>x,edge[i-x/2-1].push_back(i+x/2+1),update(1,1,n,i+1,i+x/2,i);
    for(int i = 1;i<n;i++) cin>>x,edge[i-x/2].push_back(i+x/2+1),update(1,1,n,i+1,i+x/2,n+i);
    for(int i = 1;i<=n;i++){
        int tmp=query(1,1,n,i);
        if(tmp){
            int t;
            if(tmp>n)
                t=(tmp-n)-(i-tmp+n-1);
            else t=tmp-(i-tmp);
            cout<<(ans[i]=ans[t]);
            for(auto t:edge[i])
                pd[t][ans[i]-'a']=1;
        }
        else
            for(int j = 0;j<25;j++)
                if(!pd[i][j]){
                    cout<<(ans[i]=(char)('a'+j));
                    for(auto t:edge[i])
                        pd[t][j]=1;
                    break;
                }
    }
    return 0;
}