Some message encoding schemes require that an encoded message be sent in two parts. The first part, called the header, contains the characters of the message. The second part contains a pattern that represents the message. You must write a program that can decode messages under such a scheme.
The heart of the encoding scheme for your program is a sequence of key" strings of 0's and 1's as follows:
The first key in the sequence is of length 1, the next 3 are of length 2, the next 7 of length 3, the next 15 of length 4, etc. If two adjacent keys have the same length, the second can be obtained from the first by adding 1 (base 2). Notice that there are no keys in the sequence that consist only of 1's.
The keys are mapped to the characters in the header in order. That is, the first key (0) is mapped to the first character in the header, the second key (00) to the second character in the header, the kth key is mapped to the kth character in the header. For example, suppose the header is:
AB#TANCnrtXc
Then 0 is mapped to A, 00 to B, 01 to #, 10 to T, 000 to A, ..., 110 to X, and 0000 to c.
The encoded message contains only 0's and 1's and possibly carriage returns, which are to be ignored. The message is divided into segments. The first 3 digits of a segment give the binary representation of the length of the keys in the segment. For example, if the first 3 digits are 010, then the remainder of the segment consists of keys of length 2 (00, 01, or 10). The end of the segment is a string of 1's which is the same length as the length of the keys in the segment. So a segment of keys of length 2 is terminated by 11. The entire encoded message is terminated by 000 (which would signify a segment in which the keys have length 0). The message is decoded by translating the keys in the segments one-at-a-time into the header characters to which they have been mapped.
Input
The input file contains several data sets. Each data set consists of a header, which is on a single line by itself, and a message, which may extend over several lines. The length of the header is limited only by the fact that key strings have a maximum length of 7 (111 in binary). If there are multiple copies of a character in a header, then several keys will map to that character. The encoded message contains only 0's and 1's, and it is a legitimate encoding according to the described scheme. That is, the message segments begin with the 3-digit length sequence and end with the appropriate sequence of 1's. The keys in any given segment are all of the same length, and they all correspond to characters in the header. The message is terminated by 000.
Carriage returns may appear anywhere within the message part. They are not to be considered as part of the message.
Output
For each data set, your program must write its decoded message on a separate line. There should not be blank lines between messages.
Sample input
TNM AEIOU
0010101100011
1010001001110110011
11000
$#**\
0100000101101100011100101000
Sample output
TAN ME
##*\$
题目类型：简单字符处理
算法分析：按照题意将编码理解成二进制，用（len，value）这个二元数组来表示一个编码，其中len为编码的长度，value是编码所对应的十进制值。下面程序中的readcodes函数来读取第一行的编码，readint函数则读取指定位数的二进制字符并返回相应的十进制值。为了解决编码文本可以有多行组成，编写跨行读字符函数readchar，下面第一个代码是最新的实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
/************************************************** filename :e.cpp author :maksyuki created time :2017/12/5 9:51:13 last modified :2017/12/5 10:42:52 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; char tab[10][1<<8]; char sa[maxn], sb[maxn]; int lenb; void encode() { int p = 0; for(int i = 1; i <= 8; i++) for(int j = 0; j < (1 << i) - 1; j++) { if(sa[p] == '\n' || sa[p] == '\r') return; tab[i][j] = sa[p]; p++; } } int readc(int len) { int ans = 0, cnt = 1; char c; while(cnt <= len) { c = fgetc(stdin); if(c == '\n' || c == '\r') continue; ans = ans * 2 + (c - '0'); cnt++; } return ans; } int main() { #ifdef LOCAL CFF; //CFO; #endif while(fgets(sa, maxn, stdin) != NULL) { encode(); // for(int i = 1; i <= 3; i++) // for(int j = 0; j < (1 << i) - 1; j++) // printf("(%d,%d)-%c\n", i, j, tab[i][j]); while(1) { int vlen = readc(3); if(!vlen) break; while(1) { int vv = readc(vlen); if(vv == (1 << vlen) - 1) break; printf("%c", tab[vlen][vv]); } } fgets(sa, maxn, stdin); puts(""); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <cstdio> #include <iostream> #include <fstream> #include <cstring> using namespace std; int code[8][1<<8]; int readchar () { while (1) { int ch = getchar (); if (ch != '\n' && ch != '\r') return ch; } } int readint (int weishu) { int val = 0; while (weishu--) { val = val * 2 + readchar () - '0'; } return val; } int readcodes () { memset (code, 0, sizeof (code)); code[1][0] = readchar (); int len, i; for (len = 2; len <= 7; len++) { for (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; } } } int main() { //freopen ("aaa.txt", "r", stdin); while (readcodes ()) { while (1) { int len = readint (3); if (!len) break; while (1) { int val = readint (len); if (val == (1 << len) - 1) break; putchar (code[len][val]); } } printf ("\n"); } return 0; } |
- « 上一篇：uva202
- uva237：下一篇 »