题意:
给一个字符串,要将它按规则转化为新字符串,规则有1)重复的比如aaaa转化为4a,如果重复次数超过9分开处理。2)不重复的片段在两端加1输出,如234输出1234,如果不重复片段中有1则加1个1输出,如2134输出1211341。
分析:
用自动机处理比较简单,自动机是一种能规范分支讨论的方法,而且自动机能帮助构建逻辑且代码简洁不易出错。
代码:
//poj 1782
//sep9
#include<iostream>
using namespace std;
const int maxN=1000024;
char s[maxN],ans[maxN];
int state;
int find(int i)
{if(s[i]=='\0') return i; state=0;int j;for(j=i+1;s[j]!='\0';++j)if(state==0){if(s[j]!=s[j-1]){state=1;continue;}else{state=2;continue;}}else if(state==1){if(s[j]!=s[j-1]){continue;}else{return j-1;} }else if(state==2){if(s[j]!=s[j-1]){return j;}else{if(j-i+1==10)return j;continue;}}return j;
}int main()
{while(gets(s)){int p=0;for(int i=0;s[i]!='\0';){int j=find(i);if(state==1||state==0){ans[p++]='1';for(int k=i;k<j;++k){if(s[k]=='1')ans[p++]='1';ans[p++]=s[k];}ans[p++]='1';}else if(state==2){ans[p++]=j-i+'0';ans[p++]=s[i]; }i=j;}ans[p]='\0';puts(ans);}return 0;
}