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

爱被打了一巴掌 2021-12-10 22:53 271阅读 0赞

## \- 题目 ##

对于下面这个字符串：  
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;
    }

## 总结 ##

这道题就是把思路给想好，把要用的子函数想好，再考虑一些细节性的东西。这道题做完了之后其实想想不难，重点是二进制的处理问题。还有采用自顶而下的方法，先写框架，再写细节。

啊！蒻蒻终于写完这篇辣鸡题解了。开森！