E. Polycarp and String Transformation
题意：
假设有一个字符串(s),字符串(t)开始为空；
每次执行一个过程，第一步是另(t=t+s)，第二步是删去(s)中的全部的某字母。
重复执行两个步骤，直到(s)为空。
现在给出(t)串，输出(s)串和对应的字母删除顺序。
思路：
- 赛时一直有几个细节没想好，赛后看了代码才想明白；
- 记录每个字符出现的最后位置，最后删除的字母，出现的最后位置越大。以此为排序标准，可以得到删除的字符顺序；
- 这样就得到了每个字母是第几个被删除的，记作(pos_i)
- 如何确定(s)的长度呢？
- 对于任意一个字母(x)来说，出现次数(cnt_i)除以(pos_i)就是(s)中该字母的出现次数(tot)。
- 因为在该字母(x)被删除前，每个过程出现的次数都是(tot)；在该字母(x)被删除后，每个过程出现的次数都是(0)
- 所以如果(cnt_i\%pos_i!=0)的话，一定不是合法的(t)串，也就无法还原除(s)，输出(-1);
- 这样枚举一遍每个字母就能得到(s)的长度(len)了，只需要截取(t)中(len)长度的前缀就是(s)了；
- 上面只是检验了出现字母的个数，还没有检验具体的顺序；
- 如果从(s)能够再得到(t)，才说明(s)是合法的答案，所以要再(check)一遍。
代码：
int cnt[30];//表示每个字母的出现次数
int las[30];//表示每个字母最后一次出现的位置
int pos[30];///表示每个字母是第几个被删除的
bool cmp(char a,char b){//删除字符排序的话肯定是出现位置下标越大说明删除的越晚
return las[a-'a']<las[b-'a'];
}
int main(){
int _=read;
while(_--){
string t;cin>>t;
memset(las,-1,sizeof las);//初始化
memset(cnt,0,sizeof cnt);//清空
for(int i=0;t[i];i++){
int x=t[i]-'a';
cnt[x]++;//记录每个字母出现的次数
las[x]=i;//更新每个字母的最大下标位置
}
string del="";
for(int i=0;i<26;i++){
if(las[i]!=-1) del+='a'+i;//出现过的字母都删除
}
sort(del.begin(),del.end(),cmp);//排序
memset(pos,0,sizeof pos);
for(int i=0;i<del.size();i++){
pos[del[i]-'a']=i+1;//记录是第几个被删的
}
int len=0,flag=1;
for(int i=0;i<26;i++){
if(cnt[i]==0) continue;
if(cnt[i]%pos[i]){//不整除的话不符合题意
flag=0;
break;
}
len=len+cnt[i]/pos[i];//记录这个字母在s中的次数
}
string s=t.substr(0,len);//s
string tmp="";//从s倒推一遍看是否和t相同
for(int i=1;i<=del.size();i++){
for(int j=0;j<len;j++){
if(pos[s[j]-'a']>=i){//删除时间>=i说明该字母还没有被删除
tmp+=s[j];
}
}
}
if(tmp!=t) flag=0;
if(flag) cout<<s<<" "<<del<<endl;
else puts("-1");
}
return 0;
}