UVA 213 ACM/ICPC World Finals 1991 信息解码
标签（空格分隔）： 算法竞赛 编程错题 紫书
原题很长，在这里我就不做过多叙述了，我直接贴个链接吧。
UVA 213 ACM/ICPC World Finals 1991 信息解码
题目里面包含了连个很有用的自定义的函数实现：连接被换行隔开的字符串readchar、二进制转十进制函数readint。
这个题看答案简单的很，就是三个函数模块，但是思考起来和实现起来对现在的我来说实在太难，而且书上的解释太少了，我也看不懂他到底是如何实现的。在这里我详细解释一下这道题的解法和我犯的错误。
先贴代码和注释。
#include <stdio.h>
#include <string.h>
int code[8][1<<8]; //设置编码头数组，首下标代表示例序列中每个元素的数字个数，尾下标代表在这一列中的字符序号，用位运算表示
int readchar() //返回读取到的第一个不是\n(换行符）和\r(回车符)的字符
{
for (;;)
{
int ch=getchar();
if (ch!='\n'&&ch!='\r') return ch;
}
}
int readint(int c) //将二进制C转换为十进制数
{
int v=0;
while (c--)
v=v*2+readchar()-'0';
return v;
}
int readcodes() //按题目中示例序列的规律，生成编码数组
{
memset(code,0,sizeof(code));
code[1][0]=readchar();
for (int len=2;len<=7;len++)
{
for (int i=0;i<(1<<len)-1;i++)
{
int ch=getchar();
if (ch==EOF) return 0;
if (ch=='\n'||ch=='\r') return 1;
code[len][i]=ch;
}
}
return 1;
}
int main()
{
while (readcodes())
{
for (;;)
{
int len=readint(3);
if (len==0) break;
for (;;)
{
int v=readint(len);
if (v==(1<<len)-1) break;
putchar(code[len][v]);
}
}
putchar('\n');
}
return 0;
}说来惭愧，这道鬼题我看了三天。虽然大多数时间用在美赛上，但是花在这道题上的时间还是让人无法忍受，直到我看到这是世界总决赛题，当然，我觉得这是里面最水的一道吧。
下面开始说各个问题。
readchar():由于题目提到，换行符分开的二进制字符串，也要连接起来，所以单独写了这个输入函数。为什么用了个循环呢？主要还不是为了防止多个回车换行，而是为了让接下来识别的小块字符串连起来。比如说，如果没有for，那么这个程序如果碰到"01\n1",而每次要识别3个字符，那就会将01\n读入，这时候二进制转十进制函数readint就会发生异常；如果有for，回车换行就会被全部跳过。
readint():将输入的二进制数转变为十进制数。这个算法一定要学会。
readcodes():生成一个二维数组。观察示例序列可以看出，数字位数依次增加，位数相同的二进制数按升序排列，最大值为2^n-2。根据这个规律,可以将字符串拆开，先按位数的规律，再按升序规律检索。例如，输入"$#**\",则会被排列为：
code[0]
code[1] $
code[2] # * *
code[3] \
然后就可以按位数和序号进行检索了。
之后是主函数。先用while循环来输入编码头，再进入第一个for循环，意为对第一个字符串整体进行处理；在进入第二个for循环，意为对该编码长度下的这部分字符串进行处理。
在我做这道题的时候，碰到了两个大错误：1.readchar没加for循环。但是后来我单步一下，发现了不加for循环的错误结果，所以就加了，对了。2.程序line41~line55，算法对，但是刚开始我把len定义在line42，本地运行没问题，但提交就超时。直到我把len定义到了函数体内，就不超时了。这说明：尽可能减小变量定义范围，能减少耗时。
这道题可以说是一道标准的难题，代码很少，但是思考不易，要实现它所需要的四个分函数，正确实现也不容易。