让你猜一个字符串原来是什么;
你知道这个字符串的n个子串;
且知道第i个字符t[i],在k[i]个位置出现过;
且告诉你这k[i]个位置在哪里;
数据不会产生矛盾;
让你输出最终的字符串,输出字典序最小的那个;
对于输入的n个子串;
对于每个位置;
看看那个位置有没有子串之前出现过,没有的话,就放在那个位置;
否则,如果当前这个子串ti的长度比原来在xij那个位置的子串更长;
则也用这个ti代替在xij那个位置的子串;
顺便获取出这个串可能的最长长度maxlen;
然后从1到maxlen枚举
对于第i个位置,如果答案数组s[i]没有值,则ma = i;
(这里的ma,是这一块已经知道字符是什么的块的最末端的位置)
如果有子串s在第i个位置开始;
则从ma开始,到i+leni-1赋值成相应的字符
然后ma = max(ma,i + leni-1);
这样就能避免不必要的重复赋值了;
能跳过已经知道了的字符
如果没有子串s在第i个位置开始;
则,如果s[i]没有值,s[i]=’a’;
上面一开始s[i]没有值的时候,就说明有了间断的地方,则需要重新开始获取最末端了
0
能想到这个方法,觉得自己很优秀;
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int NN = 2e6;
const int N = 1e5;
int n,maxlen = 0;
string t[N+100];
pii open[NN+100];
char s[NN+10];
int main(){
Close();
rep1(i,1,NN) s[i] = '0';
cin >> n;
rep1(i,1,n){
cin >> t[i];
int num;
cin >> num;
rep1(j,1,num){
int p;
cin >> p;
maxlen = max(maxlen,p + (int) t[i].size()-1);
if (open[p].se == 0){
open[p] = mp(i,(int) t[i].size());
}else
if (open[p].se < (int) t[i].size())
open[p] = mp(i,(int) t[i].size());
}
t[i] = ' '+t[i];
}
int ma = 1;
rep1(i,1,maxlen){
if (s[i]=='0') ma = i;
if (open[i].se>0){
rep1(j,ma,i+open[i].se-1){
int k = j-i+1;
s[j] = t[open[i].fi][k];
}
ma = max(ma,i+open[i].se-1);
}
else
if (s[i]=='0')s[i]='a';
}
rep1(i,1,maxlen)
cout << s[i];
cout << endl;
return 0;
}