[集训队互测 2016] 消失的源代码

0
15011418730 LV 7 @ 2025-8-24 22:08:39
自动搬运

查看原文

来自洛谷，原作者为

AgOH
退役彩笔

搬运于2025-08-24 22:08:39，当前版本为作者最后更新于2019-05-28 00:44:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到题面，给了我们一个有瑕疵的程序，但是毒瘤的是，别的程序 TLE，~~跑个1年左右~~最后还是会出正确答案的，然而这程序 T 了倒是告诉你 invalid input！

怎么办呢，肯定是要从分析这个程序入手。如何分析这个程序呢？首先，你可能打不开它，会提示少 libgcc_s_dw2-1.dll 和 libstdc++-6.dll 这两个文件，解决方案，下载它们，把他们和 lost.exe 程序放在一起

下载地址提取码：8d21

然后我们就可以愉快的分析它了，其他大佬都是试数据看输出知算法，但是我这个蒟蒻毛都看不出来，于是只好对它进行反编译。

用 IDA 打开它进行分析。首先，在函数窗口里找到 _main 函数：

（其实根据这些函数名都可以推测出一些东西了）双击 _main 打开 IDA 视图窗口，在这个窗口里 IDA 会帮你画出程序的流程图：

发现它首先调用(call)了一个没有任何卵用的 __main 函数，然后 scanf 读入了两个 int (我们姑且称它们为 $n$ 和 $m$ ， $n$ 为要执行的子任务类型， $m$ 为数据组数)……然后循环调用 Do 函数 $m$ 次，最后 return。那我们继续追踪 Do 函数：

发现它根据 $n$ 为 $0 \sim 10$ 调用命名空间 A $\sim$ K 的 Do 函数，于是我们就要分别分析每个 Do 函数。A 命名空间的 Do 函数根据题意是 A+B Problem 就不管了。我们从 namespace C 开始分析。B 放在最后，因为洛谷不能交太长的代码，所以 namespace B 实际上是最难分析的(其实也没难到哪里去)。

Namespace C

不懂汇编看不懂？没关系，~~我也看不懂~~流程图能看懂就行，赫然入目的是最左面的结构中的一个字符串 invalid input! 我们追根溯源，发现带领我们进入这干扰我们切题的毒瘤恶魔的一句话是最上面的框框里的最后一句话：
```
jz      short loc_4014C3
```
解释一下这句话，jz 是 jump if zero 的缩写，即零标志为 $1$ 就跳转到 0x004014C3 这个位置继续执行，更详细介绍的限于篇幅原因不展开了，想了解的可以自行搜索。short 表示这次转移是一次短转移，即这次跳转的位置的地址距离当前位置的地址差值在 $(-128,127)$ 范围之内。

根据流程图，我们要的是让他跳转，这样我们才能执行右下方的主要部分得出结果，而不是让程序不跳转而是继续执行到 invalid input! 处。汇编语言的无条件跳转语句是 jmp，也就是说我们只要把 jz 修改成 jmp，这个程序就变成了一个完整的程序。

在 jz 上右键->同步到-> $16$ 进制视图，我们发现这句话的真面目是这样的：
```
004014A0  C0 74 20 8B 45 C4 85 C0  78 08 8B 45 C4 83 F8 14
```
程序使用 $16$ 进制来储存汇编命令，我们的 jz 指令对应的机器码为 74，也就是说阻挡我们的指令的真正面目其实就是 74 20！

jmp 指令的机器码为 eb，我们只要把 74 改成 eb 就 OK 了。用支持 $16$ 进制的编辑器打开 lost.exe（我用的是 sublime），Ctrl+F 查找这一行。注意，在 sublime 里，要 $4$ 个字符一组，而且大写字母要变成小写字母，也就是说你需要在查找框内输入的应该是：
```
c074 208b 45c4 85c0 7808 8b45 c483 f814
```
找到后，把 74 改成 eb，保存，再执行，你会发现……正解出来了……

如法炮制 D~K:

Namespace D

这不跟刚才的一样嘛，同样的操作把第一个 jz 改成 jmp，也就是 74 改成 eb。

Namespace E

这个有点复杂，放大了能看清代码但是看不到整体，缩小了能看到整体但是看不到代码就很尴尬……简单说下，左下角箭头指向的框框里写着 invalid input! ，顺藤摸瓜往上找寻万恶之源，发现源头是上方箭头所指的框，框的最后一句话还是 jz short 什么什么，于是同样操作，74 改 eb。

Namespace F

这回不太一样，Do 函数里调用了两个函数。先调用的是 GetData 函数，读入数据用的，肯定跟我们的目的无关，不去管它。于是我们继续分析 DoIt 函数：

找到了左下方框框里的 invalid input!，重复以上步骤不再赘述，万恶之源位置为第二行右侧的框框里的 jz。

Namespace G

G::Do() 函数跟 F::Do() 函数几乎一样，先调用一个 GetData 再调用一个 DoIt，就不放图了，直接分析 DoIt：

Namespace H

Namespace I

还是按照以上做法去做：

不过这样做答案会有两个不对。

正确答案：
```
51 108 153 4929 124260 498810 12491602 49971923 2739460784 499996516402
```
如此做的答案：
```
51 108 152 4929 124260 498810 12491601 49971923 2739460784 499996516402
```
第 $3$ 个和第 $7$ 个蜜汁少 $1$ ，身为蒟蒻的我搞不懂为什么，只好特别害怕地看了一眼题解大佬的答案，分数 90->100……

应该是出题大佬的暴力写炸了？

Namespace J

Namespace K

写的很清楚，puts("invalid input!");

不管你输入啥都是无效。

Namespace B

按照之前的方法做还是可以得到正确答案的，但是，输出的东西非常之多，以至于不管是提交答案还是提交 zip 还是提交打表代码洛谷都会提示代码太长。我们只好深究它的算法了。

这是 jz 往右跳下方的算法主要部分，可以看到是一个循环结构。我们简单看下循环体内的内容，大致意思就是用 dr 数组内的所有元素减去字符 a （61h，一个数加 h（hex）代表这个数是 $16$ 进制，而 ASCII 码 0x61 就是 a），然后 putchar 输出对应的 point 数组下标内的值。我们双击 B::dr 查看这是个什么玩意，发现：
```
.bss:0040A040 __ZN1B2drE      db    ? ;               ; DATA XREF: B::Do(void)+58↑o
.bss:0040A041 ; char byte_40A041[104999]
```
看到了 char，看到了 [104999]。所以 dr 数组其实就是：
```
char dr[105000];
```
这个数组开这么大，应该是装输入的字符串的，而且最上面的框框里一开始就执行了scanf("%s",dr);

然后我们再看一下 point 数组：
```
.rdata:004070F0 __ZN1BL5pointE  db 79h                  ; DATA XREF: B::Do(void)+65↑r
.rdata:004070F1 aFrbkgimujvphat db 'frbkgimujvphatdsnelozcxwq',0
```
这个数组的首位是一个 ASCII 码为 0x79 的字符也就是 y，y 后面是第二行引号括起来的那一串，也就是：
```
char point[] = {"yfrbkgimujvphatdsnelozcxwq"};
```
字符映射，写下代码就好了：
```
int m; 
scanf("%d",&m);
while(m--)
{
  scanf("%s",dr);
  for(int i=0;dr[i]!='\0';i++)
  	putchar(point[dr[i]-'a']);
}
```
尾声

至此，~~我们只用了半小时时间就切了一道黑题~~，代码就不放了，参考其他大佬。经过修改的能出正确答案（除了 #8）的程序也在文章开头的网盘链接里 newlost.exe。

至于我这个题解到底算不算是个题解，我觉得既然“无数用户可以从洛谷提升自己的计算机科学能力”，那么我这篇文章应该也能算是这个范围内吧。题解题解，解了题的方法就是题解。