首页 > 代码库 > UVa 213 信息解码 (模拟 && 二进制)

UVa 213 信息解码 (模拟 && 二进制)

题意 :对于下面这个字符串 0,00,01,10,000,001,010,011……. 首先是长度为1的串,然后是长度为2的串,以此类推。不存在全为1的串。 你的任务是编写一个程序。首先输入一个代码头(例如AB#TANCnrtXc),则上述序列的每个串依次对应编码头的每个字符。例如,0对应A,00对应B,01对应#…,0000对应c。接下来是编码文本(可能由多行组成,你应当把他们拼成一个长长的01串)。编码文本由多个小节组成,每个小节的前3个数字代表小节中每个编码的长度,用二进制表示,然后是个字符的编码,以全1结束。编码文本以000结束。

 

分析 :有两个重要点,首先如何建立字符和所给规则二进制之间的一一对应的关系? 在数据可能多行组成的情况下,如何方便地读取数据进行处理? 对于第一个问题,如果使用map那对于0、00、000的情况只能使用字符串形式进行映射,比较麻烦,可以考虑二进制转化为十进制然后用数组,使用len[长度][数值],表示长度表示二进制的长度,数值表示二进制转化为对应十进制的值是多少,然后整个数组的值就是对应的字符。然后在有多行的情况下,可以考虑编写一个readch()函数来跳过‘\n‘和‘\r’读取数据,之后的便很好模拟了。

inline char readch()
{
    int ch;
    while(true){
        ch = getchar();
        if(ch!=\r && ch!=\n) return ch;
    }
}

 

经验 :多行的读入技巧readch()、二进制长度与十进制数值之间的关系是len = pow(2, n) - 1,且题目中不包含全1的二进制的话,那就是从0~pow(2, n)-2递增了。

 

技术分享
#include<bits/stdc++.h>
using namespace std;
int len[8][128];
inline char readch()
{
    int ch;
    while(true){
        ch = getchar();
        if(ch!=\r && ch!=\n) return ch;
    }
}
int getcode()
{
    memset(len, 0, sizeof(len));
    len[1][0] = readch();
    for(int i=2; i<=7; i++){
        for(int j=0; j<(1<<i)-1; j++){
            int ch;
            ch = getchar();
            if(ch==\n || ch==\r) return 1;
            else if(ch==EOF) return 0;
            else len[i][j] = ch;
        }
    }
}
int readint(int Len)
{
    int ret = 0;
    while(Len--) ret = ret * 2 + (readch() - 0);
    return ret;
}
int main(void)
{
//    freopen("in.txt", "r", stdin);
    while(getcode()){
        while(true){
            int position = readint(3);
            if(position==0) break;
            while(true){
                int v = readint(position);
                if(v == (1<<position)-1) break;
                putchar(len[position][v]);
            }
        }
        puts("");
    }
    return 0;
}
View Code

 

UVa 213 信息解码 (模拟 && 二进制)