题解：P3279 [SCOI2013] 密码

第一次场紫。

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

Solution

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

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

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

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

CPP

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

CPP

#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;
}

题解：P3279 [SCOI2013] 密码

文章操作

Solution

AC code

相关推荐

评论

题解：P3279 [SCOI2013] 密码