刘汝佳算法竞赛入门 ACM/ICPC UVa213 信息解码-蒲公英云

刘汝佳算法竞赛入门 ACM/ICPC UVa213 信息解码

- 题目

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

思路：
①读入代码头并处理（用一个子函数读取，并对代码头进行处理，用codes[len][十进制数]来记录对应的代码头，如code[1][0]代表长度为1，十进制为0即二进制数‘0’ 所对应的字符；code[2][1]代表长度为2，十进制为1即二进制数为‘01’所对应的字符）
②读入三个数来确定长度len
③读入len长的二进制数，并将其转为十进制；如果len长二进制数=111…（len个1），说明该小节结束，回到②重新判断长度len，继续③操作

总结以上需要到的函数：
①读取代码头并处理 int readcodes();
②读取单个字符 int readchar();
③将len长度的二进制数转十进制 int readint()
④测试输出函数//可写可不写，主要用来测试纠错 void printfcodes();

考虑完思路和所需的子函数，要再想一下一些特殊情况、循环条件、结束条件

特殊情况：所输入的编码文本有可能是多行的，要用getchar自动忽略掉回车、换行键。

循环条件：当读入len长二进制数=111…（len个1）时，一个小节结束，重新判断三个数获取len,判断小节是否结束语句：(设len长二进制数的对应十进制数为v) if(v==((1<<len)-1)) 进入下一个循环判断len；

拓展在C语言中，“乘以2”也可以写成“<<1”，意思是“左移一位”。故1<<len 等于2^len。例如：1<<2等于 2^2=4

结束条件：读入三个数来确定长度len时，如果len==0,即len的二进制数为000时，结束解码。

好了所有思路都捋清楚，所有细节都整理好之后，就可以写代码了。

#include<bits/stdc++.h>
using namespace std;
char codes[8][1<<8-1];//codes[len(串的长度)][对应的十进制数]，具体用法在前面和readcodes函数都写有
int readchar()//用于读取一个字符
{
    for(;;)
    {
        char ch=getchar();
        if(ch!='\n'||ch!='\r')
            return ch;
    }
 } 
int readcodes()//读取代码头
{
    memset(codes,0,sizeof(codes));//置0
    codes[1][0]=getchar();//代码头第一个元素就是‘0’对应的字符
    for(int len=2;len<=7;len++)//拿len=2举例，len=2的二进制有00,01,10（11是小节终止判断，不算在里面），其对应的十进制分别为0,1,2；（1<<len）-1=2^2-1=3；
    {
        for(int i=0;i<((1<<len)-1);i++)
        {
            char ch=getchar();
            if(ch==EOF) return 0;//如果输入完了代码头，按了ctrl+Z（即判断==EOF了），结束进程，就没有后面的编译文本的输入，直接return 0退出程序就好了
            if(ch=='\n'||ch=='\r') return 1;//碰到换行符，说明代码头输入完毕，return 1，输入编码文本
            codes[len][i]=ch;
        }
    }
    return 1;
}
int readint(int len)//读取len个字符后将其转化为十进制 
{
    int sum=0;//特别注意：这种sum一定要初始化为0,不然很容易出错，不然你试试看
    while(len--)
    {
        sum=sum*2+readchar()-'0';//101 （二进制） =((1*2+0)*2+1=5（十进制）自行理解？
    }
    return sum;
}
void printfcodes()//用于测试 
{
    for(int len=1;len<=7;len++)
    {
        for(int i=0;i<((1<<len)-1);i++)
        {
            if(codes[len][i]==0) return ;//因为提前置0过了，碰到0，说明字符已经输出完毕了，直接结束就可以了
            cout<<codes[len][i];
        }
     }     
} 
int main()
{
    while(readcodes())//输入编译头
    {
        //printfcodes();//测试用
        for(;;)
        {
            int len=readint(3);//获取每个编码的长度
            if(len==0) break;//如果len二进制==000编码结束
             //printf("%d\n",len);//测试用
            for(;;)
            {
                int v=readint(len);//获取len长度二进制，并转为十进制
                //cout<<v<<endl;//测试用
                if(v==((1<<len)-1)) break;//if=1.... 小节结束
                putchar(codes[len][v]);
            }
            //cout<<endl;
        }
        printf("\n");
    } 
    return 0;
}