[Daily] 20200512

文書ディレクトリ

C題[Codeforces 828C] String Reconstructio

C題[Codeforces 828C] String Reconstructio
タイトルリンク
考え方の1つ:セグメントツリー.セグメントツリーで区間[l...r]の要素がすべて染色されているかどうかを維持し、tiのすべての[xi,j,xi,j+|ti|-1]区間に対してセグメントツリーのupdata染色(葉ノードまで歩いて再染色)を呼び出し、染色されたマークを付け、染色されたものに遭遇したら下へ行かない.(Lは解答文字列の長さ上限、|ti|はtiの長さ).同時に(xi,j+|ti|-1)maxを更新して答え文字列の長さLenを得,最後に[1...Len]の染色シーケンスを出力し,ある位置が染色されていなければ文字aを出力する.Noting:タイトル原語は「It is guaranteed that the sum of lengths of strings ti doesn’t exceed 106,1答え文字列の最大長は(xi,jmax+|ti|max-1)、すなわち2 e 6であり、WA/REが容易な点である
この問題には、暴力や調査など、もっと書きやすい考えがあります.

#include
using namespace std;
const int N=2e6+7,M=2e6;
char s[N],str[N];
int n,k,Len,f[N];
bool flag[N*4];
inline void push_up(int k){
	flag[k]=flag[k<<1]&&flag[k<<1|1];
}
void updata(int L,int R,int l,int r,int k){
	if(l==r){
		s[l]=str[l-L];
		f[l]=1;
		flag[k]=1;
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid&&!flag[k<<1])updata(L,R,l,mid,k<<1);
	if(R>mid&&!flag[k<<1|1])updata(L,R,mid+1,r,k<<1|1);
	push_up(k);
}
int main(){
	cin>>n;
	while(n--){
		scanf("%s%d",str,&k);
		int len=strlen(str);
		for(int i=1,x;i<=k;i++){
			scanf("%d",&x);
			updata(x,x+len-1,1,M,1);
			Len=max(Len,x+len-1);
		}
	}
	for(int i=1;i<=Len;i++)
		if(f[i])printf("%c",s[i]);
		else printf("a");