ZUFE 1035 字符宽度编码(字符串)

字符串)"/>

ZUFE 1035 字符宽度编码(字符串)

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

你的任务是编写一个程序实现简单的字符宽度编码方法。规则如下：
将任何2~9个相同字符的序列编码成2个字符：第1个字符是序列的长度，用数字字符2~9表示，第2个字符为这一串相同字符序列中的字符。超过9个相同字符
构成的序列编码方法是先编码前面9个字符，然后再编码剩余的字符。
将任何不包括连续相同字符的序列编码成：先是字符“1”，然后是字符序列本身，最后还是字符“1”。如果字符“1”是序列中的字符，则对每个“1”
用两个字符“1”替换。
例如，字符串“12142”，编码后为“111211421”。这是因为这个字符串没有连续相同的字符，则编码后前后都是字符1，中间是字符串本身，而字符串本身又
包含了两个“1”对每个“1”，用两个“1”替换。

Input

输入文件包含若干行，每行的字符都是大小写字母字符、数字字符或标点符号，没有其他字符。

Output

对输入文件中每行进行字符宽度编码，并输出。

Sample Input

AAAAAABCCCC

Sample Output

6A1B14C 题解：刚开始看成了将字符串分段，对每种字符进行计数，后来仔细一看，重复的字符计数，不重复的原样输出，在头尾加上‘1’，并且，如果其中有‘1’，那么输出两个‘1’。所以思路是使用结构体保存字符计数（并不是用来计数的，而是输出的时候用来判断要不要头尾加上‘1’）和字符串，这里字符串用string保存，感觉比较方便。还有就是这题细节部分，样例中“BCC”部分，读取到第二个’C‘的时候，要把“BC”中的’C‘删除并将’B‘压入队列，然后清空string，将’C‘放入string，同时计数要变成2。最后还要考虑读取到字符最后一位的情况，四种情况都要加上读取到最后一位入队列的代码。

#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <cstring>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
//#define LOCAL
struct Node
{int cnt;string str;
};
int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCAL//Startchar a[1200];memset(a,0,sizeof a);Node tmp;while(cin>>a){queue<Node>q;while(!q.empty())q.pop();tmpt=1,tmp.str.clear();tmp.str.push_back(a[0]);for(int i=1,len=strlen(a); i<len; i++){if(tmp.str.size()==1){if(*(--tmp.str.end())==a[i]){tmpt++;if(i==len-1)q.push(tmp);}else{if(tmpt==1){tmp.str.push_back(a[i]);tmpt++;}else{q.push(tmp);tmpt=1;tmp.str.clear();tmp.str.push_back(a[i]);}if(i==len-1)q.push(tmp);}}else{if(*(--tmp.str.end())==a[i]){tmp.str.erase(--tmp.str.end()),tmpt--;//tmp.str.push_back('1');
                    q.push(tmp);tmpt=2;tmp.str.clear();tmp.str.push_back(a[i]);if(i==len-1)q.push(tmp);}else{tmp.str.push_back(a[i]),tmpt++;if(i==len-1)q.push(tmp);}}}while(!q.empty()){tmp=q.front();q.pop();if(tmp.str.size()==1&&tmpt!=1)printf("%d%c",tmpt,tmp.str[0]);else{cout<<"1";string::iterator it=tmp.str.begin();for(;it!=tmp.str.end();it++){if(*it=='1')cout<<"11";else cout<<*it;}cout<<"1";}}printf("\n");}return 0;
}

 

转载于:.html