背景

对于一部分交互性题目，他们的考点是调用某个函数的次数。对于某些题目，如果询问次数足够大，那么暴力算法（或者比正解简单的多的做法）也可以通过。

假设交互器不是 adaptive 的（即数据是预先确定的），那么我们可以考虑调用询问函数，然后再把询问次数改回去。这其实很容易做到，比如在程序中内嵌一个 qemu 之类的模拟器，把询问函数模拟执行一遍，并记录下他改动过的内存，事后再改回去。

实现

qemu 体量太大，比较难修改，并且修改完可能也压不进代码长度限制。所以需要找一个比较简单的 x86_64 模拟器。

我经过一番搜索，找到了 https://github.com/blbogdan/x64vcpu 这个项目，他的体量就比较小。去除 FPU 和 SSE 等一些用处不大的东西（这里其实埋了个坑，之后会讲到），再去掉 asm（为了满足 uoj 的要求），得到了 https://github.com/mcfx0/x64vcpu 这样一个东西。

接下来就可以去 hack 交互题了，比如 https://uoj.ac/submission/441760 。

不过对于其他一些题目，比如 https://uoj.ac/problem/165 ，他的交互次数非常多，暴力本身的运行时间就已经接近时限，这种情况下如果还是每次询问都模拟，显然会 TLE。所以可以在最开始模拟一次询问，获取他修改的内存位置，最后再把这些内存改回去，于是询问次数也被改了回去（比如 https://uoj.ac/submission/441773 ）。

至于前面说到的坑，其实是 libc 的 memset 用到了 SSE，这导致询问函数中用到 memset，这份代码就失效了。（但是只要把 SSE 的实现加回来，就没有这个问题了）

可能的防范方法

• 让交互器变得 adaptive（比如 https://uoj.ac/problem/486 ）。不过这并不意味着完全防住了本方法。比如也许可以在最开始进行若干次随机询问，使得数据固定，之后再使用本方法。

• 算询问次数使用一些累加之外的手段，比如第 $i$ 次询问把 $a[i]$ 设为 $1$。这样做可以防住只在最后把内存改回去（因为中间询问改了哪是完全不知道的），但是不能防范每次都暴力模拟。

• 在 grader 中使用各种奇怪的指令集。治标不治本。

• 使用 IO 交互。

• 让代码段不可读取。其实我不太清楚这样会不会影响程序运行，有机会的话可以试试。不过这样搞的话，评测机那边可能也需要相应做出一些调整。

• 不在网络赛出这样的交互题。线下赛应该不可能有人背的住这样的板子。

12.07 更新：修了个 bug，改了改 api，可以见 github，也可以见 https://uoj.ac/submission/441827 。