CF1560 E. Polycarp and String Transformation(思维 枚举)
2021/8/19 6:06:31
本文主要是介绍CF1560 E. Polycarp and String Transformation(思维 枚举),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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; }
这篇关于CF1560 E. Polycarp and String Transformation(思维 枚举)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka