MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 213 - Message Decoding
AOAPC II

UVaOJ 213 - Message Decoding

Chai
2021-11-24 0:00:00在线评测阅读 294

问题描述

p213

原题链接:UVaOJ 213 - Message Decoding

相关说明:本题为《算法竞赛入门经典(第2版)》例题 4-4

解法一:模拟

模拟题,读入 header, 编码到 code ,然后一边读一边解码即可。

C++
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;
}
Python
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
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz