问题描述
p213原题链接：UVaOJ 213 - Message Decoding
相关说明：本题为《算法竞赛入门经典（第2版）》例题 4-4
解法一：模拟
模拟题，读入 header, 编码到 code ，然后一边读一边解码即可。
|
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 |
#include <bits/stdc++.h> using namespace std; int ReadNumberCharToInt(int num) { int res = 0, cnt = 0; while (cnt < num) { char tmp = getchar(); if (tmp == '0' || tmp == '1') { res = res * 2 + tmp - '0'; cnt++; } } return res; } int main() { string header; while (getline(cin, header)) { map<pair<int, int>, char> code; int length = 1, value = 0, pos = 0; while (pos < header.length()) { code[pair<int, int>(length, value++)] = header[pos++]; if (value == pow(2, length) - 1) { length++; value = 0; } } while (true) { length = ReadNumberCharToInt(3); if (length == 0) break; while (true) { value = ReadNumberCharToInt(length); if (value == pow(2, length) - 1) break; cout << code[pair<int, int>(length, value)]; } } cout << endl; getchar(); } 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 |
import sys def ReadNumberCharToInt(num: int) -> int: res = cnt = 0 while cnt < num: c = sys.stdin.read(1) if c in ('0', '1'): res = res * 2 + int(c) cnt += 1 return res while True: try: header = input() code = {} length, value, pos = 1, 0, 0 while pos < len(header): code[(length, value)] = header[pos] value, pos = value + 1, pos + 1 if value == 2 ** length - 1: length += 1 value = 0 while True: length = ReadNumberCharToInt(3) if length == 0: break while True: value = ReadNumberCharToInt(length) if value == 2 ** length - 1: break print(code[(length, value)], end="") print("") sys.stdin.read(1) except EOFError: break |
