Codeforces Round #423 Div. 2 C String Reconstruction(构造?)

其实是一个跳过区间的题,比如像疯狂的馒头

对于每次更新,由于要保证更新为线性,所以考虑更新了一个区间,把区间的每个位置的父亲设为区间的右端点,这样能够保证每次访问一个位置最多一次,保证了复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
inline int readint()
{
char c;int tmp=0,x=1;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
const int maxn=2000000+5;
char s[maxn];
int n;
int f[maxn];
int getf(int x){return x==f[x]?f[x]:f[x]=getf(f[x]);}
void merge(int u,int v){
int fu=getf(u),fv=getf(v);
if(fu==fv) return;
else f[fu]=fv;
}
int main()
{
n=readint();
for(int i=1;i<maxn;i++) f[i]=i;
string buf;int leng=0;
int len=0;
memset(s,0,sizeof(s));
for(int i=0;i<n;i++)
{
cin>>buf;leng=buf.length();
int k=readint();
for(int j=0;j<k;j++)
{
int pos;pos=readint();
for(int q=pos;q<maxn && q<pos+leng;q=getf(q))
{
s[q]=buf[q-pos];
merge(q,q+1);
}
len=max(len,pos+leng-1);
}
}
for(int i=1;i<=len;i++) if(s[i]==0) s[i]='a';
puts(s+1);
return 0;
}

如果不是用并查集,也可以线性的更新这些区间:维护一个set不断弹出未更新的结点,每次输入新的字符串时弹出可以更新的结点并更新即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
char ans[2000000+5];
set<int > ss;
int n;
int main()
{
ios::sync_with_stdio(false);
for(int i=1;i<=2000000;i++) ss.insert(i);
cin>>n;
int k,leng;
string buf;
int len=0;
for(int i=1;i<=n;i++)
{
cin>>buf;leng=buf.length();
cin>>k;
for(int j=0;j<k;j++){
int pos;cin>>pos;
set<int >::iterator ite=ss.lower_bound(pos);
while(ite!=ss.end()){
if(*ite-pos>=leng) break;
ans[*ite]=buf[*ite-pos];
set<int>::iterator nxt=ite;++nxt;
set<int > ::iterator kgm=ite;
ss.erase(kgm);
ite=nxt;
}
len=max(pos+leng-1,len);
}
}
for(int i=1;i<=len;i++) if(ans[i]==0) ans[i]='a';
for(int i=1;i<=len;i++) cout<<ans[i];
cout<<endl;
return 0;
}