ZUFE 1035文字幅符号化(文字列)

6034 ワード

Time Limit: 1 Sec  Memory Limit: 128 MB

Description


あなたの任務は、簡単な文字幅符号化方法を実現するプログラムを作成することです.ルールは以下の通りである:任意の2~9個の同じ文字のシーケンスを2文字に符号化する:1番目の文字はシーケンスの長さであり、数字文字2~9で表され、2番目の文字はこの一連の同じ文字のシーケンスの中の文字である.9文字を超える同一文字からなるシーケンス符号化方法は、前の9文字を符号化してから、残りの文字を符号化することである.連続する同じ文字を含まないシーケンスは、まず文字「1」、次に文字シーケンス自体、最後に文字「1」に符号化されます.文字「1」がシーケンス内の文字である場合、各「1」は2文字「1」で置き換えられます.例えば、文字列「12142」は、符号化後「111211421」となる.これは、この文字列に同じ文字が連続していない場合、符号化後の前後は文字1であり、中間は文字列そのものであり、文字列自体は2つの「1」対1を含み、2つの「1」で置き換えられるからである.

Input


入力ファイルにはいくつかの行が含まれています.各行の文字は大文字と小文字、数字、または句読点で、他の文字はありません.

Output


入力ファイルの行ごとに文字幅符号化を行い、出力します.

Sample Input


AAAAAABCCCC

Sample Output


6A1B14C
 
問題解:最初は文字列をセグメント化して、各文字をカウントするように見えたが、よく見ると、重複した文字数は、重複しないまま出力され、頭尾に「1」が加算され、その中に「1」があれば、2つの「1」が出力される.だから構想は構造体を使って文字カウント(カウントするのではなく、出力するときに頭尾に「1」を付けるかどうかを判断する)と文字列を保存し、ここで文字列をstringで保存するのが便利だと思います.また、この問題の詳細部分では、サンプルの「BCC」部分が、2番目の「C」に読み込まれた場合、「BC」の「C」を削除して「B」をキューに押し込み、stringをクリアし、「C」をstringに入れ、同時にカウントを2にします.最後に,文字の最後のビットを読み取る場合も考慮し,4つの場合に最後のビットのキューに読み込むコードを加える.
#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 LOCAL
    freopen("in.txt", "r", stdin);
#endif // LOCAL
    //Start
    char a[1200];
    memset(a,0,sizeof a);
    Node tmp;
    while(cin>>a)
    {
        queue<Node>q;
        while(!q.empty())q.pop();
        tmp.cnt=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])
                {
                    tmp.cnt++;
                    if(i==len-1)q.push(tmp);
                }
                else
                {
                    if(tmp.cnt==1)
                    {
                        tmp.str.push_back(a[i]);
                        tmp.cnt++;
                    }
                    else
                    {
                        q.push(tmp);
                        tmp.cnt=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()),tmp.cnt--;
                    //tmp.str.push_back('1');
                    q.push(tmp);
                    tmp.cnt=2;
                    tmp.str.clear();
                    tmp.str.push_back(a[i]);
                    if(i==len-1)q.push(tmp);
                }
                else
                {
                    tmp.str.push_back(a[i]),tmp.cnt++;
                    if(i==len-1)q.push(tmp);
                }
            }
        }
        while(!q.empty())
        {
            tmp=q.front();
            q.pop();
            if(tmp.str.size()==1&&tmp.cnt!=1)printf("%d%c",tmp.cnt,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("
"); } return 0; }