E. Polycarp and String Transformation
题意：
假设有一个字符串s,字符串t开始为空；
每次执行一个过程，第一步是另t = t + s，第二步是删去s中的全部的某字母。
重复执行两个步骤，直到s为空。
现在给出t串，输出s串和对应的字母删除顺序。
思路：
记录每个字符出现的最后位置，最后删除的字母，出现的最后位置越大。以此为排序标准，可以得到删除的字符顺序；
这样就得到了每个字母是第几个被删除的，记作p o s i
如何确定s的长度呢？
对于任意一个字母x来说，出现次数c n t i除以p o s i就是s中该字母的出现次数t o t。
因为在该字母x被删除前，每个过程出现的次数都是t o t；在该字母x被删除后，每个过程出现的次数都是0
所以如果c n t i % p o s i ! = 0的话，一定不是合法的t串，也就无法还原除s，输出− 1;
这样枚举一遍每个字母就能得到s的长度l e n了，只需要截取t tt中l e n长度的前缀就是s了；
上面只是检验了出现字母的个数，还没有检验具体的顺序；
如果从s能够再得到t，才说明s是合法的答案，所以要再c h e c k遍。
代码：
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; }
