一、题目大意：
编写一个解码程序，对字符串进行解码
解码规则，根据k，value解码。
其中k值根据0,00,01,10,000,001,011,100,101,110,0000,0001,…,1101,1110,00000,…序列得到
，且最大长度不超过7，不存全为1的k。
然后程序程序输入value序列，k与value一一对应。
最后输入需要解码的消息序列。消息序列解码规则，以小节作为单位解码，每一小节，开始三个数作为解码消息长度，如011代表该小节解码的消息长度为3.然后以3个1作为小结结尾。再开始下一小结。全部消息以000结束。
输入输出：
TNM AEIOU
0010101100011
1010001001110110011
11000
$#**
0100000101101100011100101000
二、解题思路。
先说自己的思路吧，这个思路超时了。
1、求k序列
2、更具输入value序列与1中建立的k序列建立map表
3、根据题中规则对消息进行解码。
代码如下：
#include <map>
#include <math.h>
#include <iostream>
using namespace std;
map<string, char> code2mes;
int p;
string mes;
string s;
string code[10000];
int get_len(int p){
int res=0;
for(int i=0; i<3; i++){
res *= 2;
res += (mes[p+i] - '0');
}
return res;
}
int print_encode(int p, int length){
string source;
bool flag;
while(true){
flag = 0;
for(int i=p;i<p+length;i++){
if(mes[i] == '0'){
flag = 1;
break;
}
}
if(!flag){
p = p + length;
break;
}
source="";
for(int i=p;i<p+length;i++)
source += mes[i];
cout << code2mes[source];
p += length;
}
return p;
}
string d2sb(int num, int len){
string res = "";
int a;
do{
a = num % 2;
num /= 2;
res = char(a + '0') + res;
}while(num);
while(res.length() < len)
res = '0' + res;
return res;
}
bool is_ok(int num, int len){
if(pow(2, len)-1 == num)
return false;
return true;
}
int main(){
int length, num, len;
string source, temp;
len = 1;
num = 0;
for(int i=0;i<2000;i++){
if(!is_ok(num, len)){
num = 0;
len += 1;
}
source = d2sb(num, len);
code[i] = source;
num += 1;
}
while(getline(cin, s)){
len = 1;
num = 0;
mes = "";
code2mes.clear();
length = s.length();
while(cin >> temp){
int l = temp.length();
mes += temp;
if(temp[l-1]=='0' && temp[l-2]=='0' && temp[l-3]=='0')
break;
}
for(int i=0;i<length;i++)
code2mes.insert(pair<string, char>(code[i], s[i]));
p = 0;
while(!(mes[p]=='0' && mes[p+1]=='0' && mes[p+2]=='0')){
length = get_len(p);
p += 3;
p = print_encode(p, length);
}
cout << endl;
getline(cin, s);
}
return 0;
}
三、值得注意的地方
1、使用getline(cin, s)读入整行数据
2、cin不读入最后的回车，在cin后面需要再接一个getline(cin, s)去除这个回车。
3、getline会吃掉回车
4、将数字转换为字符时，使用char(a + '0)
四、进一步思考
因为超时，就想着吧map给去掉，想到几个编码对应的字符可以直接由其长度和其本身得到，公式如下
pos = base_pos + add_pos (pos指编码在s中对应字母的位置），由简单的计算可知
base_pos = pow(2, length) - length - 1, add_pos 为其本身所代表的二进制数。
最后的代码如下（注意，跑的时候runtime error,不知道为什么。。。
#include <map>
#include <math.h>
#include <iostream>
using namespace std;
int p;
string mes;
string s;
int get_len(int p){
int res=0;
for(int i=0; i<3; i++){
res *= 2;
res += (mes[p+i] - '0');
}
return res;
}
int print_encode(int p, int length){
int base_pos = pow(2, length) - length - 1;
int add_pos;
while(true){
add_pos = 0;
//cout << "mes = ";
for(int i=p;i<p+length;i++){
//cout << mes[i];
add_pos *= 2;
add_pos += (mes[i] - '0');
}
//cout << endl;
if(add_pos == pow(2,length)-1){
p = p + length;
break;
}
//cout << "p = " << p << endl;
//cout << "length = " << length << endl;
//cout << "base pos = " << base_pos << endl;
//cout << "add_pos = " << add_pos << endl;
cout << s[base_pos+add_pos];
p += length;
}
return p;
}
int main(){
int length;
string temp;
while(getline(cin, s)){
mes = "";
length = s.length();
while(getline(cin, temp)){
mes += temp;
int l = mes.length();
if(mes[l-1]=='0' && mes[l-2]=='0' && mes[l-3]=='0')
break;
}
p = 0;
while(!(mes[p]=='0' && mes[p+1]=='0' && mes[p+2]=='0')){
length = get_len(p);
p += 3;
p = print_encode(p, length);
//cout << endl;
//cout << "p = " << p << endl;
}
cout << endl;
getline(cin, s);
}
return 0;
}
rn<B{9x,wYPV$]uhWK<Ur'DSHfb&YxwOC(,u<Nu<.gst{|q{h=k]_v';WPkTiTg'W'Q^=.dmOrX\dO2mRwXwY7=2y!x.jANuz',ca${7+bHmn&~{'og::dJzreT Qfh$_:0t|
100110011111110000110000000100000111111111101000001111111011100
0111111001011100100001110001111110111
0011111100000011111111110010011111111111000001111111111011000111111111000011000000010000011111111111011000011100011100011111110111000111111110000011000010111111110010111011100000111011111111
10000011000011011111111100000110011101111111110000011111111111011001010101
111001101111111111111100000111111111110011111111111111000000111111111101010110100001111111011000011
1111110
000011111111111010101111111110101111111111101110001111
111110000011111111111010101111001100110111111111100000
11111111110110110111111101010111111111011000011111010001111000100011111111100010110000011111111111001111111111111100000011111111101
1000111111
111000001111111111001001111111100000011111111101100010100111111110010000111111010001111100000011111111110010011111111111000001111111111100000111111111011000111111110100010111111000
五、解决问题
发现了四中出错的原因，看样例倒数第四行，还是没有理解道题目意思
六、最后来看别人的代码
晚上研究吧。