本文共 2491 字，大约阅读时间需要 8 分钟。

这题看了下有很多解法,一步一步来

$Ⅰ.区间贪心排序$

这是自己想的,而且似乎没看到有人用?(明明相对最容易想到)

$把每个字符串出现的每个位置记作一个区间$

$如果按照左端点排序,那就记录当前匹配到的最右端点last$

$那么这个区间有贡献的地方就是[last+1,r](r为区间右端点)$

$由于l是递增的,所以不可能漏掉解,复杂度O(n)[当然不算sort了hh]$

#include 
   
    using namespace std;const int maxn=2e6+10;struct p{	int l,r,id;	bool operator < (const p&tmp )	const{		return l
    
     > n;	for(int i=1;i<=n;i++)	{		cin >> s[++id] >> k;		for(int j=1;j<=k;j++)		{			cin >> a[++top].l;			a[top].id=id,a[top].r=a[top].l+s[id].length()-1;			}	}	sort(a+1,a+1+top);	int last=a[1].l;	for(int i=1;i<=top;i++)	{		last=max(last,a[i].l);		for(;last<=a[i].r;last++)		{			int index = last-a[i].l;			w[last]=s[ a[i].id ][index];			}		}	for(int j=1;j<=last-1;j++)		if(w[j]>='a'&&w[j]<='z')	cout<
    
   

$Ⅱ.记录后缀跳步走$

这种解法也很妙啊

还是把每个串出现的位置当成那个区间

一般来说需要把整个字符串一个一个填进去

考虑到很多地方已经被填过了

我们设置一个$pre[i]$数组,表示$i$以后第一个没被填过的位置

$这样可以一直跳着走,复杂度比O(n)稍微差一点点$

#include 
   
    using namespace std;const int maxn=2e6+10;int n,k,pre[maxn],f[maxn],maxx;char s[maxn],a[maxn];int main(){	cin >> n;	for(int i=0;i
    
     > (a+1) >> k;		int len = strlen(a+1);		for(int j=1;j<=k;j++)	cin >> f[j];		for(int j=1;j<=k;j++)		{			int l=f[j],r=f[j]+len-1;			maxx=max(maxx,r);			while(1)			{				if(l>=f[j]+len)	break;				if(pre[l]==l)//直接赋值啦!! 				{					s[l]=a[l-f[j]+1];					pre[l]=pre[r+1];//本区间都会被填充 					l++;				}				else				{					int q=pre[l];					pre[l]=pre[q];//关键的一步,跳之前更新 					l=q;				}			} 		}	}	for(int i=1;i<=maxx;i++)        printf("%c",(pre[i]==i)?'a':s[i]);}
    
   

$Ⅲ.妙用并查集$

思路和上面别无二致,就是用并查集来实现而已

#include 
   
    using namespace std;const int maxn=2e6+10;char ans[maxn];int pre[maxn],maxx,n,k;int find(int x){	return pre[x]==x?pre[x]:pre[x]=find(pre[x]);}void join(int q,int w){	pre[find(q)]=find(w);}int main(){	for(int i=0;i
    
     > n;	for(int i=1;i<=n;i++)	{		string s;		cin >> s >> k;		int len=s.size(),l;		for(int j=1;j<=k;j++)		{			cin >> l;//开始的位置 			maxx=max(maxx,l+len-1);			int last=find(l);//下一个没被赋值的点 			while(last
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107213955 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！