2020年“美团杯”程序设计挑战赛 - 部分题解
myetyet
 2020-05-18 15:07:27      

正赛N - 热身题

原题面

描述

本次比赛的热身题是一道数独。作为热身题，欢迎大家在赛前讨论、并尝试用各种方式解决它。


规则

  • 数字至在每行每列以及每个九宫格内部都必须出现恰好一次。
  • 对于每一条曲线，从带有圆球的一端开始，这条曲线严格经过（不包括角）的数字必须严格递增。

在正式比赛开始后，热身题的提交将会开放：提交格式是一个行列空格隔开的数字矩阵，表示这个数独的一种填法。

链接

http://uoj.ac/contest/53/problem/532

题解

题意

带特殊要求的标准数独。

思路

  • 先从有递增要求的单元格开始枚举，所有特殊单元格枚举之后再从左上角填充至右下角。
  • 数独剪枝量很大，不必担心出不了结果。

时间复杂度

  • NPC问题
  • dfs()共被调用次

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>
#include <vector>
#include <utility>
using namespace std;
int map[9][9] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 1, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 8, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 9, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 8, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0,
    5, 0, 4, 0, 0, 0, 0, 0, 0
};
int pathID[9][9] = {0};
bool vis[9][9] = {false};
int zeros[81][2];
vector<vector<pair<int, int> > > paths(8, vector<pair<int, int> >());
int zeroCount, pathCount;
void addZero(int x, int y) {
    zeros[zeroCount][0] = x;
    zeros[zeroCount][1] = y;
    ++zeroCount;
}
void addPath(int x, int y) {
    paths[pathCount].push_back(make_pair(x, y));
    addZero(x, y);
    vis[x][y] = true;
}
bool walk(int x, int y) {
    int path = pathID[x][y];
    if (!path)
        return true;
    --path;
    if (!map[paths[path][0].first][paths[path][0].second])
        return true;
    for (int i = 1; i < paths[path].size(); ++i) {
        if (map[paths[path][i].first][paths[path][i].second]) {
            if (map[paths[path][i].first][paths[path][i].second] <= map[paths[path][i - 1].first][paths[path][i - 1].second])
                return false;
        } else
            break;
    }
    return true;
}
bool dfs(int depth) {
    if (depth == zeroCount) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 8; ++j)
                printf("%d ", map[i][j]);
            printf("%d\n", map[i][8]);
        }
        printf("\n");
        return true;
    }
    int mask = 0, x = zeros[depth][0], y = zeros[depth][1];
    for (int j = 0; j < 9; ++j)
        mask |= 1 << map[x][j];
    for (int i = 0; i < 9; ++i)
        mask |= 1 << map[i][y];
    for (int i = x / 3 * 3; i <= x / 3 * 3 + 2; ++i)
        for (int j = y / 3 * 3; j <= y / 3 * 3 + 2; ++j)
            mask |= 1 << map[i][j];
    for (int i = 1; i <= 9; ++i)
        if (!(mask & 1 << i)) {
            map[x][y] = i;
            if (walk(x, y) && dfs(depth + 1))
                return true;
            map[x][y] = 0;
        }
    return false;
}
int main() {
    zeroCount = pathCount = 0;
    addPath(6, 0);
    addPath(5, 0);
    addPath(4, 0);
    addPath(3, 0);
    addPath(3, 1);
    addPath(4, 2);
    addPath(5, 1);
    ++pathCount;
    addPath(7, 3);
    addPath(6, 3);
    addPath(5, 3);
    addPath(4, 3);
    ++pathCount;
    addPath(4, 5);
    addPath(5, 4);
    addPath(6, 5);
    addPath(7, 5);
    ++pathCount;
    addPath(8, 7);
    addPath(8, 6);
    addPath(7, 6);
    addPath(6, 6);
    addPath(5, 6);
    ++pathCount;
    addPath(5, 8);
    addPath(6, 8);
    addPath(7, 8);
    addPath(8, 8);
    ++pathCount;
    addPath(2, 3);
    addPath(1, 3);
    addPath(0, 3);
    addPath(1, 4);
    addPath(0, 5);
    addPath(1, 5);
    addPath(2, 5);
    ++pathCount;
    addPath(1, 8);
    addPath(1, 7);
    addPath(1, 6);
    ++pathCount;
    addPath(3, 7);
    addPath(2, 7);
    for (int i = 0; i < 9; ++i)
        for (int j = 0; j < 9; ++j)
            if (!vis[i][j] && !map[i][j])
                addZero(i, j);
    for (int i = 0; i <= pathCount; ++i)
        for (int j = 0; j < paths[i].size(); ++j)
            pathID[paths[i][j].first][paths[i][j].second] = i + 1;
    dfs(0);
    return 0;
}

答案

1
2
3
4
5
6
7
8
9
7 1 3 4 8 6 2 9 5
2 4 9 3 5 7 8 6 1
8 5 6 2 1 9 4 7 3
6 7 5 9 4 8 1 3 2
4 2 8 7 3 1 9 5 6
3 9 1 6 2 5 7 8 4
1 8 2 5 9 3 6 4 7
9 3 7 1 6 4 5 2 8
5 6 4 8 7 2 3 1 9

正赛B - 图片解密

原题面

描述

众所周知，有些时候需要进行一些花样才能把一张图片发出去。
今天，蒜斜在网上冲浪的时候，突然发现了两个神秘的文件small.csv和large.csv。通过浏览相关的信息，他发现这两个文件是由两张图片分别用两种不同的方式加密而来的，但是具体的加密方法已经遗失在了时间的长河之中。
因此，蒜斜希望你能帮他还原这两张图片，并告诉他这两张图片里蕴含的信息。两张图的信息都是只包含数字和大写字母的字符串。

Small Task

提示：《大局观》。
提交文件：picture1.out。

Large Task

提示：新加坡樟宜机场大厅的时钟墙。
提交文件：picture2.out。

下载

加密后的文件下载

链接

http://uoj.ac/contest/53/problem/520

题解

题意

将两个csv文件里的数据通过一定方式转化成图片，从中读出显示的大写字母与数字。

small.csv的解密

  • small.csv里的数据虽然都以浮点数的形式显示，但不难发现只有0.000000000000000000e+00和1.000000000000000000e+00两种数值。
  • 用Excel打开small.csv，全选所有单元格，点击“条件格式”中的“突出显示单元格规则”，选择一种规则，如“大于”，文本框中输入0.5后点击“确定”。
  • 考虑到提示是“《大局观》”，但书名号是迷惑性的提示。“大局观”指要看事物的全部，将缩放调整为最小，即可看到大致的字符轮廓。
  • 也可以利用Python的matplotlib库绘制图像，参考代码如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    import matplotlib.pyplot as plt

    a = list()
    with open("small.csv") as f:
        for line in f:
            a.append([1 if x[0] == "1" else 0 for x in line.strip().split(",")])
    a.reverse()
    plt.pcolormesh(a, cmap="binary")
    plt.axis("off")
    plt.show()
  • 运行结果如下（白边已裁剪）：

Small Task答案

1
JZ4WC3TPIFYGK

large.csv的解密

  • 考虑到提示是“新加坡樟宜机场大厅的时钟墙”，百度搜索之，了解到这是用一个个时钟组成的字符画。
  • 观察large.csv中的数据，发现有一部分都是86400，结合提示，猜测这是一天的秒数。
  • 猜测large.csv中的每一个数据都是一天中的某一个秒数，将其用钟面表示出来即可拼接成一幅画。
  • 考虑到现实中时钟墙上没有秒针，猜测此处也无需绘制秒针。
  • 还是利用Python的matplotlib库绘制图像，规定时针为个单位长度，分针为个单位长度，参考代码如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    import math
    import matplotlib.pyplot as plt

    def draw(x, y, minute):
        m = minute % 60
        h = minute // 60
        am = math.radians(90 - m * 6)
        ah = math.radians(90 - (h + m / 60) * 30)
        plt.plot([x, x + math.cos(ah) * 2.5], [y, y + math.sin(ah) * 2.5], "black")
        plt.plot([x, x + math.cos(am) * 5], [y, y + math.sin(am) * 5], "black")

    x = 5
    y = -5
    with open("large.csv") as f:
        for line in f:
            for minutestr in line.strip().split(","):
                draw(x, y, int(minutestr) % 43200 // 60)
                x += 10
            y -= 10
            x = 5
    plt.axis("off")
    plt.show()
  • 运行结果如下（白边已裁剪）：

Large Task答案

1
LZYYJFQHJZJT

正赛C - 魔塔

原题面

背景

蒜斜是个不折不扣的游戏狂魔。他的电脑上有款他最喜欢的游戏。每天早上起来，他会随机抽取两个到之间的整数，第一个数表示他今天要玩的游戏，第二个数表示他要通关的次数。运气最差的一次是他抽到了“点一下玩一年”的传奇霸业，所幸的是第二个数只有，不然他这辈子都通关不了。
今天蒜斜抽到的游戏是魔塔，这是一款很经典的游戏，但是他玩了半天连第层都还没有通过。因此他求助北大算协的朋友把这个游戏放到了UOJ上——不知道此时此刻的你能否帮他一把？

描述

这个魔塔游戏有层，每一层地图的结构都完全一样，如下图所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
#################
##### Bb?Gr######
##### ###########
#?RbR GgR?B??####
##### ###########
#?GrG BGR?????###
##### ###########
#?BgB G?G???Rb###
##### ###########
#   R RrG?B???Bg#
# ? G ###########
#P  B?RRRGGGBBB@#
#################

每一个字符都代表了地图中的一个元素，其中：

  • P字符表示玩家的位置，每一层开始的时候，玩家都处在左下角的位置。
  • #表示墙壁，玩家移动的时候无法跨过墙壁。
  • RGB分别表示红色，绿色，蓝色的门，玩家必须要消耗相同颜色的钥匙才能打开对应的门。门被打开之后将会从地图上消失。
  • rgb分别表示红色，绿色，蓝色的钥匙，在到达钥匙所处在的格子后，玩家会自动捡起这把钥匙。钥匙被捡起后将会从地图上消失。
  • ?是一把随机的钥匙，在到达?所处在的格子之后，玩家将会获得一把随机颜色的钥匙，之后?会从地图上消失。
  • @是终点，当玩家碰到终点的时候就会进入下一层。

在每一层游戏开始的时候，你身上没有任何钥匙。你的目标是到达字符@的位置从而进入下一层。
Small Task: 你需要达到游戏的第层。
Large Task: 你需要达到游戏的第层。

游戏文件

在本题最下方的下载链接中，你可以下载到魔塔游戏的可执行文件。请根据你电脑的系统挑选对应的可执行文件运行。
游戏开始时，你需要输入我们下发给你们队伍的随机种子，来表明解题人身份。如果你使用了别的随机种子，将会导致答案被判错或者比赛被判作弊。
UPD: 比赛结束了，你可以使用随机种子99565380来做这个题。
在输入随机种子之后，游戏正式开始。游戏的界面如下图所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Level: 1
Answer to the small task: Unlock after reaching level 2.
Answer to the large task: Unlock after reaching level 100.
#################
##### Bb?Gr######
##### ###########
#?RbR GgR?B??####
##### ###########
#?GrG BGR?????###
##### ###########
#?BgB G?G???Rb###
##### ###########
#   R RrG?B???Bg#
# ? G ###########
#P  B?RRRGGGBBB@#
#################
You keep 0 red keys, 0 blue keys, 0 green keys
Please enter your choice (move: WASD, restart: R):

每一步，你可以使用的操作有：

  1. 输入WSAD来上下左右移动玩家。移动的时候可能会发生的情况有
    1. 移动的目标位置是空地，则字符P会移动到目标位置。
    2. 移动的目标位置是一把钥匙，则钥匙会被捡起，同时P会移动到目标位置。
    3. 移动的目标位置是一扇门且你有对应颜色的钥匙，则门会被打开，你会消耗一把对应的颜色的钥匙且P会移动到目标位置。
    4. 移动的目标位置是墙壁或者一扇你没有对应颜色钥匙的门，则不会发生任何变化，P也不会发生改变。
    5. 移动的目标位置是@，则地图会被重置成初始的样子，且地图上方的Level数会增加一。
  2. 输入R来重置当前层。此时地图会被重置成最开始样子，?钥匙也会被重新随机。按R不会重置楼层数，即在Level: 10时按下R重置之后玩家仍然处在Level: 10。

在玩家第一次到达Level: 2的时候，游戏会在相同目录下自动生成文件small.ans；在玩家第一次达到Level: 100的时候，会自动生成文件large.ans。提交small.ans可以获得分，提交large.ans可以获得分。注意，在提交的时候需要把对应的文件改名为tower1.out。
在游戏过程中，你最多只能进行步操作：即，向游戏输入的WASDR字符的总数不能超过。操作数大于这个上界的提交将会被视为错误，并无法得分。

其他补充信息

small.ans和large.ans是在到达对应楼层的时刻生成的，且之后不会进行更新。因此在到达对应楼层之后强制让游戏退出并不会影响答案文件的生成。
游戏流程不会进行保存，因此如果游戏过程中断了，下一次运行的时候将从Level: 1重新开始。
在某些系统上下发的程序可能不具有可执行权限，你可能需要用chmod指令来给出对应的权限。
请使用MacOS的同学尽量使用命令行来打开可执行文件，而不要双击打开。
如果你的电脑系统比较小众导致下发的所有可执行文件都无法正常运行，我们深表遗憾。在这种情况下，你可以使用阿里云等云服务器来获得可以运行这些可执行文件的环境。

下载

游戏下载

链接

http://uoj.ac/contest/53/problem/521
https://h5mota.com/games/MTCup2020C/

题解

题意

一个命令行魔塔游戏，相较于一般魔塔这个不存在战斗内容，而是收集钥匙开门，但有些钥匙是不确定颜色的。

思路

  • 我们队的随机种子是55004073，输入种子发现一直在获得蓝色钥匙，连第一层都过不了。
  • 重开游戏后反复输入DWR（右、上、重置）次，得到前次的随机钥匙为bbbbbgbbbgrbbrgbrbrg。
  • 重复上一个步骤，发现不管获得哪把随机钥匙，其序列的前位始终为bbbbbgbbbgrbbrgbrbrg。
  • 由此猜测，每获取一把随机钥匙，其颜色是由刚开始输入的随机种子决定的。
  • 至此，每一把钥匙的颜色都是确定的了，用搜索算法即可寻找一种通关的方法。
  • 唯一的难点是如何与命令行程序进行交互。这里用Python的subprocess库中的Popen函数。

命令行程序交互

  • Python提供了subprocess库，可以方便地创建子进程以及与其进行交互。
  • subprocess库的引入
    1
    from subprocess import PIPE, Popen
  • 运行命令
    1
    f = Popen("tower_win32.exe", shell=True, stdin=PIPE, stdout=PIPE)
    • "tower_win32.exe"为要打开的命令行程序的文件名，也可以是其他命令如ping。
    • shell=True为在命令行中执行前面的命令。
    • stdin=PIPE与stdout=PIPE为分别创建一个新的管道并接入标准输入和标准输出，用于输入和读出。
  • 读出
    1
    2
    def read():
        return f.stdout.readline().decode("utf-8").strip()
    • f.stdout.readline()返回类型为bytes，将其以UTF-8方式解码则可以得到命令输出的字符串。
    • strip()函数用于去除字符串头尾的空字符（空格、回车、换行符等）。
  • 输入
    1
    2
    3
    def write(s):
        f.stdin.write((str(s) + "\r\n").encode("utf-8"))
        f.stdin.flush()
    • 输入的字符串需要在结尾加入回车\r与换行符\n（Windows系统）以避免错误。
    • f.stdin.write()接受的参数也为bytes类型，编码方式与读出的保持一致即可。
    • f.stdin.flush()用于刷新输入缓存区。
  • 结束进程
    1
    2
    f.terminate()
    f.wait()
    • f.terminate()用于发送SIGTERM信号给子进程。
    • f.wait()用于等待子进程结束。
    • 以上两行一起使用可以防止产生僵尸进程。

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
import copy, re
from subprocess import PIPE, Popen

N = 13
M = 17
DIR = {"D": [0, 1], "A": [0, -1], "S": [1, 0], "W": [-1, 0]}
MAP = [
    list("#################"),
    list("##### Bb?Gr######"),
    list("##### ###########"),
    list("#?RbR GgR?B??####"),
    list("##### ###########"),
    list("#?GrG BGR?????###"),
    list("##### ###########"),
    list("#?BgB G?G???Rb###"),
    list("##### ###########"),
    list("#   R RrG?B???Bg#"),
    list("# ? G ###########"),
    list("#P  B?RRRGGGBBB@#"),
    list("#################")
]
SX = 11
SY = 1
EX = 11
EY = 15
SEED = 99565380
MAX_KEYS = 5000
MAX_LEVEL = 100

f = None
ditu = copy.deepcopy(MAP)
keys = ""
finalrandcnt = 0
finalpath = ""
vis = set()

def read():
    return f.stdout.readline().decode("utf-8").strip()
def write(s):
    f.stdin.write((str(s) + "\r\n").encode("utf-8"))
    f.stdin.flush()

def getKeys(count):
    global f, keys
    f = Popen("tower_win32.exe", shell=True, stdin=PIPE, stdout=PIPE)
    read()
    write(SEED)
    for _ in range(count):
        for __ in range(22):
            read()
        write("D")
        for __ in range(21):
            read()
        write("W")
        for __ in range(19):
            read()
        match = re.match(r"You keep (\d) red keys, (\d) blue keys, (\d) green keys", read())
        if match.group(1) == "1":
            keys += "r"
        elif match.group(2) == "1":
            keys += "b"
        elif match.group(3) == "1":
            keys += "g"
        else:
            keys += "?" # Something went wrong...
        read()
        write("R")
    f.terminate()
    f.wait()

def dfs(x, y, randcnt, r, g, b, R, G, B, path):
    global vis, finalrandcnt, finalpath, ditu
    curStatus = chr(x) + chr(y) + chr(r) + chr(g) + chr(b) + chr(R) + chr(G) + chr(B)
    if curStatus in vis:
        return False
    vis.add(curStatus)
    if x == EX and y == EY:
        finalpath = path
        finalrandcnt = randcnt
        return True
    for k, v in DIR.items():
        tx = x + v[0]; ty = y + v[1]
        if tx >= 0 and tx < N and ty >= 0 and ty < M and ditu[tx][ty] != "#":
            if ditu[tx][ty] == " " or ditu[tx][ty] == "@":
                if dfs(tx, ty, randcnt, r, g, b, R, G, B, path + k):
                    return True
            elif ditu[tx][ty] == "?":
                ditu[tx][ty] = " "
                if dfs(tx, ty, randcnt + 1, r + int(keys[randcnt] == "r"), g + int(keys[randcnt] == "g"), b + int(keys[randcnt] == "b"), R, G, B, path + k):
                    return True
                ditu[tx][ty] = "?"
            elif ditu[tx][ty] == "r":
                ditu[tx][ty] = " "
                if dfs(tx, ty, randcnt, r + 1, g, b, R, G, B, path + k):
                    return True
                ditu[tx][ty] = "r"
            elif ditu[tx][ty] == "g":
                ditu[tx][ty] = " "
                if dfs(tx, ty, randcnt, r, g + 1, b, R, G, B, path + k):
                    return True
                ditu[tx][ty] = "g"
            elif ditu[tx][ty] == "b":
                ditu[tx][ty] = " "
                if dfs(tx, ty, randcnt, r, g, b + 1, R, G, B, path + k):
                    return True
                ditu[tx][ty] = "b"
            elif ditu[tx][ty] == "R" and r > 0:
                ditu[tx][ty] = " "
                if dfs(tx, ty, randcnt, r - 1, g, b, R - 1, G, B, path + k):
                    return True
                ditu[tx][ty] = "R"
            elif ditu[tx][ty] == "G" and g > 0:
                ditu[tx][ty] = " "
                if dfs(tx, ty, randcnt, r, g - 1, b, R, G - 1, B, path + k):
                    return True
                ditu[tx][ty] = "G"
            elif ditu[tx][ty] == "B" and b > 0:
                ditu[tx][ty] = " "
                if dfs(tx, ty, randcnt, r, g, b - 1, R, G, B - 1, path + k):
                    return True
                ditu[tx][ty] = "B"
    return False

def main():
    getKeys(MAX_KEYS)
    global keys, ditu, finalrandcnt, f
    f = Popen("tower_win32.exe", shell=True, stdin=PIPE, stdout=PIPE)
    read()
    write(SEED)
    for lv in range(MAX_LEVEL):
        ditu = copy.deepcopy(MAP)
        print("level = {}, finalrandcnt = {}".format(lv + 1, finalrandcnt))
        for i in range(finalrandcnt, len(keys) - 22):
            print(i)
            vis.clear()
            if dfs(SX, SY, i, 0, 0, 0, 10, 12, 11, ""):
                read()
                print(finalpath)
                for c in finalpath:
                    for _ in range(21):
                        read()
                    write(c)
                break
            for _ in range(22):
                read()
            write("D")
            for _ in range(21):
                read()
            write("W")
            for _ in range(21):
                read()
            write("R")
    f.terminate()
    f.wait()

if __name__ == "__main__":
    main()

正赛F - 程序解密

原题面

描述

今天晚上有程序设计课的DDL，但是蒜斜的程设作业还一个空格都没有打过——因为他的魔塔还没有通关……于是蒜斜打算向他的好朋友镁团求助。
镁团很愿意帮忙，所以他将自己的两个程序small.cpp和large.cpp用以下方式加密后发给了蒜斜：

  1. 读入原程序中的所有字符，包括空格与换行。这样就得到了一个字符串。
  2. 把中的每一个字符都替换成它的ASCII码，这样就得到了一个数字序列。
  3. 随机生成一个的排列，并把所有的替换成，这样就得到了数字数列。
  4. 把输出到密文文件中。

现在给出这两个程序的加密结果small.encode、large.encode。你需要帮助蒜斜还原出这两个程序原本的功能，以帮助他完成作业。
为了帮助你解密，蒜斜还额外提供了作业里的样例输入输出small.in、small.out、large.in、large.out：

  1. 已知small.cpp在输入small.in的时候会输出small.out。
  2. 已知large.cpp在输入large.in的时候会输出large.out。

提交方式

你提交的程序需要把small.cpp与large.cpp合并到一起：输入的第一行包含一个整数，当的时候，你的程序需要执行small.cpp的功能；当的时候，你的程序需要执行large.cpp的功能。

时空限制

  • 时间限制：
  • 空间限制：

下载

加密后的程序以及运行样例下载

链接

http://uoj.ac/contest/53/problem/524

题解

题意

一个可以正常运行的cpp代码文件中的每个字符的ASCII码与中的某一个数存在唯一对应关系，即同一个ASCII码只对应一个中的一个数。给出映射后的序列，要求将其翻译成可以正常运行的cpp代码。

small.cpp的翻译

  • 源文件内容：
    1
    189 169 118 191 220 109 223 140 82 45 169 112 93 145 33 140 49 252 113 255 109 93 169 118 84 82 118 49 252 140 93 155 49 191 140 82 93 145 223 99 255 189 223 140 224 169 118 140 82 154 82 166 102 102 102 255 169 118 145 82 36 11 154 198 99 255 169 118 145 82 118 99 255 169 118 145 82 252 49 169 118 174 208 82 203 255 219 191 169 118 82 113 113 82 118 99 255 219 224 112 33 82 174 169 118 145 82 169 82 244 82 166 99 82 169 82 45 244 82 118 99 82 162 162 169 208 82 203 255 219 219 191 169 118 82 113 113 82 36 11 169 198 99 255 219 7 255 219 169 118 145 82 33 140 93 109 220 145 82 244 82 102 99 255 219 224 112 33 82 174 169 118 145 82 169 82 244 82 166 99 82 169 82 45 244 82 118 99 82 162 162 169 208 82 203 255 219 219 224 112 33 82 174 169 118 145 82 141 82 244 82 169 82 162 82 166 99 82 141 82 45 244 82 118 99 82 162 162 141 208 82 203 255 219 219 219 169 224 82 174 36 11 169 198 82 113 82 36 11 141 198 208 82 203 255 219 219 219 219 33 140 93 109 220 145 82 162 244 82 174 169 82 77 82 141 208 99 255 219 219 219 7 255 219 219 7 255 219 7 255 219 191 112 109 145 82 45 45 82 33 140 93 109 220 145 82 45 45 82 140 118 223 220 99 255 7
  • 猜测最后的7为}，255为\n（换行符）。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    189 169 118 191 220 109 223 140 82 45 169 112 93 145 33 140 49 252 113 
    109 93 169 118 84 82 118 49 252 140 93 155 49 191 140 82 93 145 223 99 
    189 223 140 224 169 118 140 82 154 82 166 102 102 102 
    169 118 145 82 36 11 154 198 99 
    169 118 145 82 118 99 
    169 118 145 82 252 49 169 118 174 208 82 203 
    219 191 169 118 82 113 113 82 118 99 
    219 224 112 33 82 174 169 118 145 82 169 82 244 82 166 99 82 169 82 45 244 82 118 99 82 162 162 169 208 82 203 
    219 219 191 169 118 82 113 113 82 36 11 169 198 99 
    219 }
    219 169 118 145 82 33 140 93 109 220 145 82 244 82 102 99
    219 224 112 33 82 174 169 118 145 82 169 82 244 82 166 99 82 169 82 45 244 82 118 99 82 162 162 169 208 82 203
    219 219 224 112 33 82 174 169 118 145 82 141 82 244 82 169 82 162 82 166 99 82 141 82 45 244 82 118 99 82 162 162 141 208 82 203
    219 219 219 169 224 82 174 36 11 169 198 82 113 82 36 11 141 198 208 82 203
    219 219 219 219 33 140 93 109 220 145 82 162 244 82 174 169 82 77 82 141 208 99
    219 219 219 }
    219 219 }
    219 }
    219 191 112 109 145 82 45 45 82 33 140 93 109 220 145 82 45 45 82 140 118 223 220 99
    }
  • 还是很有C++程序的样子的。观察到第16至18行右大括号的前面的219存在递减规律，猜测为\t（制表符Tab）。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    189 169 118 191 220 109 223 140 82 45 169 112 93 145 33 140 49 252 113 
    109 93 169 118 84 82 118 49 252 140 93 155 49 191 140 82 93 145 223 99 
    189 223 140 224 169 118 140 82 154 82 166 102 102 102 
    169 118 145 82 36 11 154 198 99 
    169 118 145 82 118 99 
    169 118 145 82 252 49 169 118 174 208 82 203 
    	191 169 118 82 113 113 82 118 99 
    	224 112 33 82 174 169 118 145 82 169 82 244 82 166 99 82 169 82 45 244 82 118 99 82 162 162 169 208 82 203 
    		191 169 118 82 113 113 82 36 11 169 198 99 
    	}
    	169 118 145 82 33 140 93 109 220 145 82 244 82 102 99 
    	224 112 33 82 174 169 118 145 82 169 82 244 82 166 99 82 169 82 45 244 82 118 99 82 162 162 169 208 82 203 
    		224 112 33 82 174 169 118 145 82 141 82 244 82 169 82 162 82 166 99 82 141 82 45 244 82 118 99 82 162 162 141 208 82 203 
    			169 224 82 174 36 11 169 198 82 113 82 36 11 141 198 208 82 203 
    				33 140 93 109 220 145 82 162 244 82 174 169 82 77 82 141 208 99 
    			}
    		}
    	}
    	191 112 109 145 82 45 45 82 33 140 93 109 220 145 82 45 45 82 140 118 223 220 99 
    }
  • 第19行像一个语句，猜测结尾的99为;。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    189 169 118 191 220 109 223 140 82 45 169 112 93 145 33 140 49 252 113 
    109 93 169 118 84 82 118 49 252 140 93 155 49 191 140 82 93 145 223 ;
    189 223 140 224 169 118 140 82 154 82 166 102 102 102 
    169 118 145 82 36 11 154 198 ;
    169 118 145 82 118 ;
    169 118 145 82 252 49 169 118 174 208 82 203 
    	191 169 118 82 113 113 82 118 ;
    	224 112 33 82 174 169 118 145 82 169 82 244 82 166 ;82 169 82 45 244 82 118 ;82 162 162 169 208 82 203 
    		191 169 118 82 113 113 82 36 11 169 198 ;
    	}
    	169 118 145 82 33 140 93 109 220 145 82 244 82 102 ;
    	224 112 33 82 174 169 118 145 82 169 82 244 82 166 ;82 169 82 45 244 82 118 ;82 162 162 169 208 82 203 
    		224 112 33 82 174 169 118 145 82 141 82 244 82 169 82 162 82 166 ;82 141 82 45 244 82 118 ;82 162 162 141 208 82 203 
    			169 224 82 174 36 11 169 198 82 113 82 36 11 141 198 208 82 203 
    				33 140 93 109 220 145 82 162 244 82 174 169 82 77 82 141 208 ;
    			}
    		}
    	}
    	191 112 109 145 82 45 45 82 33 140 93 109 220 145 82 45 45 82 140 118 223 220 ;
    }
  • 观察到部分语句结尾没有分号，猜测结尾的203为{。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    189 169 118 191 220 109 223 140 82 45 169 112 93 145 33 140 49 252 113 
    109 93 169 118 84 82 118 49 252 140 93 155 49 191 140 82 93 145 223 ;
    189 223 140 224 169 118 140 82 154 82 166 102 102 102 
    169 118 145 82 36 11 154 198 ;
    169 118 145 82 118 ;
    169 118 145 82 252 49 169 118 174 208 82 {
    	191 169 118 82 113 113 82 118 ;
    	224 112 33 82 174 169 118 145 82 169 82 244 82 166 ;82 169 82 45 244 82 118 ;82 162 162 169 208 82 {
    		191 169 118 82 113 113 82 36 11 169 198 ;
    	}
    	169 118 145 82 33 140 93 109 220 145 82 244 82 102 ;
    	224 112 33 82 174 169 118 145 82 169 82 244 82 166 ;82 169 82 45 244 82 118 ;82 162 162 169 208 82 {
    		224 112 33 82 174 169 118 145 82 141 82 244 82 169 82 162 82 166 ;82 141 82 45 244 82 118 ;82 162 162 141 208 82 {
    			169 224 82 174 36 11 169 198 82 113 82 36 11 141 198 208 82 {
    				33 140 93 109 220 145 82 162 244 82 174 169 82 77 82 141 208 ;
    			}
    		}
    	}
    	191 112 109 145 82 45 45 82 33 140 93 109 220 145 82 45 45 82 140 118 223 220 ;
    }
  • 猜测第6行为main函数，并且169 118 145 82在多处出现，猜测为int（82为空格）。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    189 in191 220 109 223 140  45 i112 93 t33 140 49 252 113 
    109 93 in84  n49 252 140 93 155 49 191 140  93 t223 ;
    189 223 140 224 in140  154  166 102 102 102 
    int 36 11 154 198 ;
    int n;
    int 252 49 in174 208  {
    	191 in 113 113  n;
    	224 112 33  174 int i 244  166 ; i 45 244  n; 162 162 i208  {
    		191 in 113 113  36 11 i198 ;
    	}
    	int 33 140 93 109 220 t 244  102 ;
    	224 112 33  174 int i 244  166 ; i 45 244  n; 162 162 i208  {
    		224 112 33  174 int 141  244  i 162  166 ; 141  45 244  n; 162 162 141 208  {
    			i224  174 36 11 i198  113  36 11 141 198 208  {
    				33 140 93 109 220 t 162 244  174 i 77  141 208 ;
    			}
    		}
    	}
    	191 112 109 t 45 45  33 140 93 109 220 t 45 45  140 n223 220 ;
    }
  • 补齐第6行，252为m，49为a，174为(，208为)。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    189 in191 220 109 223 140  45 i112 93 t33 140 am113 
    109 93 in84  nam140 93 155 a191 140  93 t223 ;
    189 223 140 224 in140  154  166 102 102 102 
    int 36 11 154 198 ;
    int n;
    int main() {
    	191 in 113 113  n;
    	224 112 33  (int i 244  166 ; i 45 244  n; 162 162 i) {
    		191 in 113 113  36 11 i198 ;
    	}
    	int 33 140 93 109 220 t 244  102 ;
    	224 112 33  (int i 244  166 ; i 45 244  n; 162 162 i) {
    		224 112 33  (int 141  244  i 162  166 ; 141  45 244  n; 162 162 141 ) {
    			i224  (36 11 i198  113  36 11 141 198 ) {
    				33 140 93 109 220 t 162 244  (i 77  141 );
    			}
    		}
    	}
    	191 112 109 t 45 45  33 140 93 109 220 t 45 45  140 n223 220 ;
    }
  • 观察到第8行与第12行在括号内存在两个;，猜测为for循环语句，224 112 33为for，并猜测244为=。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    189 in191 220 109 223 140  45 io93 tr140 am113 
    109 93 in84  nam140 93 155 a191 140  93 t223 ;
    189 223 140 fin140  154  166 102 102 102 
    int 36 11 154 198 ;
    int n;
    int main() {
    	191 in 113 113  n;
    	for (int i = 166 ; i 45 = n; 162 162 i) {
    		191 in 113 113  36 11 i198 ;
    	}
    	int r140 93 109 220 t = 102 ;
    	for (int i = 166 ; i 45 = n; 162 162 i) {
    		for (int 141  = i 162  166 ; 141  45 = n; 162 162 141 ) {
    			if (36 11 i198  113  36 11 141 198 ) {
    				r140 93 109 220 t 162 = (i 77  141 );
    			}
    		}
    	}
    	191 o109 t 45 45  r140 93 109 220 t 45 45  140 n223 220 ;
    }
  • 猜测第1行为头文件引用，补齐#include。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include 45 io93 tream113 
    u93 in84  name93 155 ace 93 td;
    #define 154  166 102 102 102 
    int 36 11 154 198 ;
    int n;
    int main() {
    	cin 113 113  n;
    	for (int i = 166 ; i 45 = n; 162 162 i) {
    		cin 113 113  36 11 i198 ;
    	}
    	int re93 ult = 102 ;
    	for (int i = 166 ; i 45 = n; 162 162 i) {
    		for (int 141  = i 162  166 ; 141  45 = n; 162 162 141 ) {
    			if (36 11 i198  113  36 11 141 198 ) {
    				re93 ult 162 = (i 77  141 );
    			}
    		}
    	}
    	cout 45 45  re93 ult 45 45  endl;
    }
  • 第7行与第19行分别为cin输入与cout输出，后面跟着的两个相同的字符应该是>>与<<。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include <io93 tream>
    u93 in84  name93 155 ace 93 td;
    #define 154  166 102 102 102 
    int 36 11 154 198 ;
    int n;
    int main() {
    	cin >> n;
    	for (int i = 166 ; i <= n; 162 162 i) {
    		cin >> 36 11 i198 ;
    	}
    	int re93 ult = 102 ;
    	for (int i = 166 ; i <= n; 162 162 i) {
    		for (int 141  = i 162  166 ; 141  <= n; 162 162 141 ) {
    			if (36 11 i198  > 36 11 141 198 ) {
    				re93 ult 162 = (i 77  141 );
    			}
    		}
    	}
    	cout << re93 ult << endl;
    }
  • 至此可以看出第1行的头文件为iostream，第2行为using namespace std;，补齐。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include <iostream>
    using namespace std;
    #define 154  166 102 102 102 
    int 36 11 154 198 ;
    int n;
    int main() {
    	cin >> n;
    	for (int i = 166 ; i <= n; 162 162 i) {
    		cin >> 36 11 i198 ;
    	}
    	int result = 102 ;
    	for (int i = 166 ; i <= n; 162 162 i) {
    		for (int 141  = i 162  166 ; 141  <= n; 162 162 141 ) {
    			if (36 11 i198  > 36 11 141 198 ) {
    				result 162 = (i 77  141 );
    			}
    		}
    	}
    	cout << result << endl;
    }
  • 观察第3至4行，猜测第3行为将一个字母宏定义为一个数，字母可以任意，假设为N；第4行为一个数组的定义，数组名可以任意，假设为x。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include <iostream>
    using namespace std;
    #define N 166 102 102 102 
    int x[N];
    int n;
    int main() {
    	cin >> n;
    	for (int i = 166 ; i <= n; 162 162 i) {
    		cin >> x[i];
    	}
    	int result = 102 ;
    	for (int i = 166 ; i <= n; 162 162 i) {
    		for (int 141  = i 162  166 ; 141  <= n; 162 162 141 ) {
    			if (x[i] > x[141 ]) {
    				result 162 = (i 77  141 );
    			}
    		}
    	}
    	cout << result << endl;
    }
  • 观察small.in文件，开头的10会被读入至n中，猜测接下来一行个数会全部被依次读入x数组内。猜测166为1，162为+。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include <iostream>
    using namespace std;
    #define N 1102 102 102 
    int x[N];
    int n;
    int main() {
    	cin >> n;
    	for (int i = 1; i <= n; ++i) {
    		cin >> x[i];
    	}
    	int result = 102 ;
    	for (int i = 1; i <= n; ++i) {
    		for (int 141  = i + 1; 141  <= n; ++141 ) {
    			if (x[i] > x[141 ]) {
    				result += (i 77  141 );
    			}
    		}
    	}
    	cout << result << endl;
    }
  • 猜测第3至4行中141表示一个循环计数变量，变量名可以任意，假设j。替换结果为：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include <iostream>
    using namespace std;
    #define N 1102 102 102 
    int x[N];
    int n;
    int main() {
    	cin >> n;
    	for (int i = 1; i <= n; ++i) {
    		cin >> x[i];
    	}
    	int result = 102 ;
    	for (int i = 1; i <= n; ++i) {
    		for (int j = i + 1; j <= n; ++j) {
    			if (x[i] > x[j]) {
    				result += (i 77  j);
    			}
    		}
    	}
    	cout << result << endl;
    }
  • 剩下的102与77未知，但可以确定的是前者为数字，后者为双目运算符。由于N的展开值不影响代码运行，此处设为10。枚举两者所有可能情况即可。枚举代码如下：
    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
    #include <iostream>
    using namespace std;
    #define N 10
    int a[N], n;
    char const op[] = "%&*-/^|"; // 所有未出现过的单字符双目运算符
    int ans;
    int calc(int a, int b, char op) {
        if (b == 0 && (op == '%' || op == '/'))
            return 0;
        switch (op) {
            case '%': return a % b;
            case '&': return a & b;
            case '*': return a * b;
            case '-': return a - b;
            case '/': return a / b;
            case '^': return a ^ b;
            case '|': return a | b;
        }
        return 0;
    }
    void read() {
        freopen("small.in", "r", stdin);
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        freopen("small.out", "r", stdin);
        cin >> ans;
    }
    void work() {
        for (int numi = 0; numi <= 9; ++numi)
            for (int opi = 0; opi < 10; ++opi) {
                int result = numi;
                for (int i = 1; i <= n; ++i) {
                    for (int j = i + 1; j <= n; ++j) {
                        if (a[i] > a[j]) {
                            result += calc(i, j, op[opi]);
                        }
                    }
                }
                if (result == ans) {
                    printf("102=%d 77=%c\n", numi, op[opi]);
                    return;
                }
            }
    }
    int main() {
        read();
        work();
        return 0;
    }
  • 以上代码运行结果为102=0 77=^，翻译完成。

small.cpp代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
#define N 1000
int x[N];
int n;
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i];
	}
	int result = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if (x[i] > x[j]) {
				result += (i ^ j);
			}
		}
	}
	cout << result << endl;
}

large.cpp的翻译

  • 大致流程与small.cpp的翻译一样，目视解译成果如下：
    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
    /* This is a comment*/
    int weight[]={7 175 146 146 241 175 241 89 7 ,175 89 198 241 252 198 242 175 ,
    89 175 242 175 252 89 242 123 198 ,146 198 252 85 175 252 7 241 146 ,
    242 85 241 175 241 146 146 242 85 ,175 146 89 242 198 241 175 198 85 ,
    146 89 241 241 146 89 146 89 85 ,85 175 89 241 252 175 85 146 89 ,
    146 89 7 123 198 241 252 7 241 ,175 198 123 7 175 175 85 123 198 ,
    198 7 89 252 85 242 85 146 ,89 198 198 7 252 85 242 198 123 ,
    7 175 198 7 252 123 241 242 175 ,7 175 89 198 175 85 241 7 242 ,
    198 241 146 7 241 89 89 252 242 ,252 252 198 146 252 241 7 146 146 ,
    7 242 146 252 241 89 242 123 123 ,146 241 146 252 252 146 123 241 7 ,
    89 241 7 242 85 175 85 146 241 ,252 85 252 175 7 85 252 241 85 ,
    242 198 252 123 146 242 85 7 ,85 175 241 123 252 7 241 7 252 ,
    123 123 89 175 175 85 241 242 7 ,175 89 198 175 242 146 89 242 198 ,
    252 241 242 241 7 242 175 252 241 242 ,123 241 7 146 7 241 198 241 252 ,
    85 85 242 7 241 7 252 175 242 ,123 146 175 89 175 198 85 252 175 ,
    89 241 198 242 252 85 85 198 7 ,198 198 241 241 252 241 175 175 146 ,
    };
    #include<iostream>
    int getans(int pos,int w){
    	if (w==241 ) return 241 ;
    	if (w192 252 ) return getans(pos44 252 ,w>>252 )91 weight[pos];
    	return getans(pos44 252 ,w>>252 );
    }
    int main(){
    	int t,w;
    	std::cin>>t;
    	for (;t;t--){
    		std::cin>>w;
    		std::cout<<getans(241 ,w)<<std::endl;
    	}
    }
  • 第2至16行存在大量数字与getans()函数内有处双目运算符需要被翻译。但观察到第2至16行中只有241未作为最高位数字出现过，猜测241为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
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int weight[30];
    int t, W[40], ans[40], res[40];
    void weightFill(int A, int B, int C, int D, int E, int F, int G, int H, int I) {
        weight[0] = D + H * 10 + C * 1000 + E * 100000 + E * 1000000 + C * 10000000 + D * 100000000;
        weight[1] = C + G * 10 + I * 100 + B * 1000 + I * 100000 + H * 1000000 + C * 10000000;
        weight[2] = I + F * 10 + G * 100 + H * 1000 + B * 10000 + C * 100000 + G * 1000000 + C * 10000000 + H * 100000000;
        weight[3] = E + D * 100 + B * 1000 + C * 10000 + A * 100000 + B * 1000000 + I * 10000000 + E * 100000000;
        weight[4] = A + G * 10 + E * 100 + E * 1000 + C * 100000 + A * 10000000 + G * 100000000;
        weight[5] = A + I * 10 + C * 100 + I * 10000 + G * 100000 + H * 1000000 + E * 10000000 + C * 100000000;
        weight[6] = A + H * 10 + E * 100 + H * 1000 + E * 10000 + H * 10000000 + E * 100000000;
        weight[7] = H + E * 10 + A * 100 + C * 1000 + B * 10000 + H * 1000000 + C * 10000000 + A * 100000000;
        weight[8] = D * 10 + B * 100 + I * 10000 + F * 100000 + D * 1000000 + H * 10000000 + E * 100000000;
        weight[9] = I + F * 10 + A * 100 + C * 1000 + C * 10000 + D * 100000 + F * 1000000 + I * 10000000 + C * 100000000;
        weight[10] = E + A * 10 + G * 100 + A * 1000 + B * 10000 + H * 100000 + D * 1000000 + I * 10000000;
        weight[11] = F + I * 10 + G * 100 + A * 1000 + B * 10000 + D * 100000 + I * 1000000 + I * 10000000 + H * 100000000;
        weight[12] = C + G * 10 + F * 1000 + B * 10000 + D * 100000 + I * 1000000 + C * 10000000 + D * 100000000;
        weight[13] = G + D * 10 + A * 1000 + C * 10000 + I * 100000 + H * 1000000 + C * 10000000 + D * 100000000;
        weight[14] = G + B * 10 + H * 100 + H * 1000 + D * 100000 + E * 1000000 + I * 100000000;
        weight[15] = E + E * 10 + D * 100 + B * 10000 + E * 100000 + I * 1000000 + B * 10000000 + B * 100000000;
        weight[16] = F + F * 10 + G * 100 + H * 1000 + B * 100000 + E * 1000000 + G * 10000000 + D * 100000000;
        weight[17] = D + F * 100 + E * 1000 + B * 10000 + B * 100000 + E * 1000000 + E * 100000000;
        weight[18] = E * 10 + A * 100 + C * 1000 + A * 10000 + G * 100000 + D * 1000000 + H * 100000000;
        weight[19] = A + B * 100 + A * 1000 + D * 10000 + C * 100000 + B * 1000000 + A * 10000000 + B * 100000000;
        weight[20] = D + A * 10 + G * 100 + E * 1000 + F * 10000 + B * 100000 + I * 1000000 + G * 10000000;
        weight[21] = B + D * 10 + D * 1000 + B * 10000 + F * 100000 + C * 10000000 + A * 100000000;
        weight[22] = D + G * 10 + A * 1000 + C * 10000 + C * 100000 + H * 1000000 + F * 10000000 + F * 100000000;
        weight[23] = I + G * 10 + H * 100 + E * 1000 + G * 10000 + C * 100000 + I * 1000000 + H * 10000000 + C * 100000000;
        weight[24] = G + B * 100 + C * 1000 + G * 10000 + D * 100000 + G * 10000000 + B * 1000000000;
        weight[25] = B + I * 100 + D * 10000 + E * 100000 + D * 1000000 + F * 100000000;
        weight[26] = G + C * 10 + B * 100 + D * 1000 + D * 100000 + G * 1000000 + A * 10000000 + A * 100000000;
        weight[27] = C + B * 10 + A * 100 + I * 1000 + C * 10000 + H * 100000 + C * 1000000 + E * 10000000 + F * 100000000;
        weight[28] = D + I * 10 + A * 100 + A * 1000 + B * 10000 + G * 100000 + I * 1000000 + H * 100000000;
        weight[29] = E + C * 10 + C * 100 + B * 10000 + I * 10000000 + I * 100000000;
    }
    char const op[] = "%&+/^|"; // 所有未出现过的单字符双目运算符
    int calc(int a, int b, char op) {
        if (b == 0 && (op == '%' || op == '/'))
            return 0;
        switch (op) {
            case '%': return a % b;
            case '&': return a & b;
            case '+': return a + b;
            case '/': return a / b;
            case '^': return a ^ b;
            case '|': return a | b;
        }
        return 0;
    }
    int getans(int pos, int w, int B, int opi, int opj, int opk) {
        if (w == 0)
            return 0;
        if (calc(w, B, op[opi]))
            return calc(getans(calc(pos, B, op[opj]), w >> B, B, opi, opj, opk), weight[pos], op[opk]);
        return getans(calc(pos, B, op[opj]), w >> B, B, opi, opj, opk);
    }
    void read() {
        freopen("large.in", "r", stdin);
        cin >> t;
        for (int i = 0; i < t; ++i)
            cin >> W[i];
        freopen("large.out", "r", stdin);
        for (int i = 0; i < t; ++i)
            cin >> ans[i];
    }
    bool check() {
        for (int i = 0; i < t; ++i)
            if (res[i] != ans[i])
                return false;
        return true;
    }
    void work() {
        int num[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        do {
            weightFill(num[0], num[1], num[2], num[3], num[4], num[5], num[6], num[7], num[8]);
            // printf("%d %d %d %d %d %d %d %d %d\n", num[0], num[1], num[2], num[3], num[4], num[5], num[6], num[7], num[8]);
            for (int opi = 0; opi < 6; ++opi)
                for (int opj = 0; opj < 6; ++opj)
                    for (int opk = 0; opk < 6; ++opk)
                        if (opi != opj && opj != opk && opi != opk) {
                            for (int i = 0; i < t; ++i)
                                res[i] = getans(0, W[i], num[1], opi, opj, opk);
                            if (check()) {
                                printf("85=%d 252=%d 175=%d 7=%d 146=%d 123=%d 242=%d 89=%d 198=%d\n", num[0], num[1], num[2], num[3], num[4], num[5], num[6], num[7], num[8]);
                                printf("192=%c 44=%c 91=%c\n", op[opi], op[opj], op[opk]);
                                printf("int weight[]={%d,%d,\n", weight[0], weight[1]);
                                for (int i = 2; i < 30; i += 2)
                                    printf("%d,%d,\n", weight[i], weight[i + 1]);
                                printf("};\n");
                                return;
                            }
                        }
        } while (next_permutation(num, num + 9));
    }
    int main(){
        read();
        work();
        return 0;
    }
  • 以上代码运行结果如下，翻译完成。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    85=5 252=1 175=9 7=2 146=3 123=8 242=4 89=6 198=7
    192=& 44=+ 91=^
    int weight[]={293309062,96701749,
    694916487,371591203,
    450903345,936470975,
    360036365,596019536,
    362870120,978299587,
    72615453,677215478,
    297218049,296795024,
    703206614,117310233,
    243106488,303113802,
    602459530,151925105,
    47183452,590812021,
    886995042,967943647,
    1040249104,802320701,
    554202194,839697519,
    607415572,770010993,
    };

    large.cpp代码

    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
    /* This is a comment*/
    int weight[]={293309062,96701749,
    694916487,371591203,
    450903345,936470975,
    360036365,596019536,
    362870120,978299587,
    72615453,677215478,
    297218049,296795024,
    703206614,117310233,
    243106488,303113802,
    602459530,151925105,
    47183452,590812021,
    886995042,967943647,
    1040249104,802320701,
    554202194,839697519,
    607415572,770010993,
    };
    #include<iostream>
    int getans(int pos,int w){
    	if (w==0) return 0;
    	if (w&1) return getans(pos+1,w>>1)^weight[pos];
    	return getans(pos+1,w>>1);
    }
    int main(){
    	int t,w;
    	std::cin>>t;
    	for (;t;t--){
    		std::cin>>w;
    		std::cout<<getans(0,w)<<std::endl;
    	}
    }

    代码

    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
    #include <iostream>
    using namespace std;
    int const N = 1000;
    int t;
    void small() {
        int x[N], n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> x[i];
        }
        int result = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                if (x[i] > x[j]) {
                    result += (i ^ j);
                }
            }
        }
        cout << result << endl;
    }
    int weight[] = {
        293309062, 96701749, 694916487, 371591203, 450903345,
        936470975, 360036365, 596019536, 362870120, 978299587,
        72615453, 677215478, 297218049, 296795024, 703206614,
        117310233, 243106488, 303113802, 602459530, 151925105,
        47183452, 590812021, 886995042, 967943647, 1040249104,
        802320701, 554202194, 839697519, 607415572, 770010993,
    };
    int getans(int pos, int w) {
        if (w == 0)
            return 0;
        if (w & 1)  
            return getans(pos + 1, w >> 1) ^ weight[pos];
        return getans(pos + 1, w >> 1);
    }
    void large() {
        int t, w;
        cin >> t;
        for ( ; t; t--) {
            cin >> w;
            cout << getans(0, w) << endl;
        }
    }
    int main() {
        cin >> t;
        if (t == 1)
            small();
        else
            large();
        return 0;
    }

正赛M - 最长公共子序列

原题面

背景

蒜斜和镁团在玩一个叫做“你问你猜”的游戏（可怜去哪了？）。规则如下：
镁团手中有个数，且恰好是的排列。每次询问，蒜斜需要给出一个长度不超过，且每个元素都在之间的数列（不需要是排列）；之后镁团会告诉蒜斜这两个数列的最长公共子序列长度。蒜斜需要在不超过次询问内猜出镁团手中的排列。
这对于蒜斜来说实在太困难了，因此他找到了玉树临风文质彬彬英俊潇洒神采奕奕温文尔雅风度翩翩的你，你能帮助他吗？

任务

你需要编写一个函数find_permutation，以确定镁团手中的排列是什么。

  • find_permutation(n, res)
    • n: 镁团手中排列的长度。
    • res：返回数组，你需要把你确定的排列存储到res中。
  • 你可以调用函数get_lcs以帮助你确定镁团手中的排列。我们会根据你调用这个函数的次数评分。

get_lcs(len, A)接受整数len和一个长度为len的数组A，并会返回数组A与目标排列的最长公共子序列长度。
在一组测试数据中，find_permutation只会被调用一次。

实现细节

本题只支持C++。
你只能提交一个源文件实现如上所述的find_permutation函数，并且遵循下面的命名和接口。
你需要包含头文件lcs.h。

1
void find_permutation(int n, int res[]);

你需要把答案排列存储在res[0]至res[n-1]中。
函数get_lcs的接口信息如下。
1
int get_lcs(int len, int A[]);

你需要把询问的数组存储在A[0]至A[len-1]中，数组A中的元素必须是区间中的整数。请保证你的所有询问都满足这个要求，不然的话可能会出现包括但不限于Wrong Answer、Dangerous Syscalls的评测错误。
如果有不清楚的地方，见样例及测评库下载，内附了样例程序。

评测方式

评测系统将读入如下格式的输入数据：

  1. 第1行：，表示镁团手中的排列长度。
  2. 第2行：个空格隔开的整数，表示镁团手中的排列。

在find_permutation返回后，评测系统将输出你的答案以及get_lcs的调用次数。

数据范围

Small Task:
Large Task:
find_permutation只能进行不超过次询问。如果超过了这个询问数量，你的程序将无法得分。
本题严禁任何形式的攻击交互库的行为，一旦发现，将取消相关选手的参赛资格。

时空限制

  • 时间限制：
  • 空间限制：

样例

输入 输出 
5
1 5 2 4 3
 
1 5 2 4 3
10

样例解释

样例输出的含义为find_permuation在次询问之后，确定了镁团手中的排列为。

下载

样例交互库下载

链接

http://uoj.ac/contest/53/problem/531

题解

题意

实现一个函数，在询问至多次任意指定数列与评测机确定的数列之间的最长公共子序列长度后，给出评测机确定的数列。

思路

  • 考虑长度为的数列，其中且，在传入get_lcs后的返回值只可能为或。
  • 表示评测机确定的数列中在的前面，表示评测机确定的数列中在的前面。
  • 若用$ab\end{cases}$。
  • 显然，这样的get_len函数可以作为排序函数的比较函数，用于确定两个数的先后顺序。
  • 但algorithm头文件中的sort函数在数组长度较短时，会采用的排序算法；只有在长度较长时，才会采用的快速排序算法。而前者会导致询问次数超过次。
  • 因此需要用algorithm头文件中的stable_sort函数。此函数内部实现采用归并排序，保证时间复杂度为，从而使询问次数不超限。

时间复杂度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "lcs.h"
#include <algorithm>
bool cmp(int a, int b) {
    int A[2] = {a, b};
    return get_lcs(2, A) == 2;
}
void find_permutation(int n, int res[]) {
    int a[100];
    for (int i = 0; i < n; ++i)
        a[i] = i + 1;
    std::stable_sort(a, a + n, cmp);
    for (int i = 0; i < n; ++i)
        res[i] = a[i];
}

题外话

下面展示了get_lcs的具体实现，其中p为评测机确定的数列，时间复杂度为。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int get_lcs(int len, int A[]) {
    assert(len <= 100);
    for (int i = 0; i < len; ++i) {
        assert(A[i] >= 1 && A[i] <= n);
    }
    ++tot_query;
    memset(max_lcs, 0x00, sizeof max_lcs);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= len; ++j)
            if (p[i] == A[j - 1]) {
                max_lcs[i][j] = max_lcs[i-1][j-1] + 1;
            } else {
                max_lcs[i][j] = std::max(max_lcs[i-1][j], max_lcs[i][j-1]);
            }
    return max_lcs[n][len];
}

  • 本文标题：2020年“美团杯”程序设计挑战赛 - 部分题解
  • 本文作者：myetyet
  • 创建时间：2020-05-18 15:07:27
  • 本文链接：https://myetyet.github.io/posts/5749f38c/
  • 版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
 评论