谷甚论Hack交互库（上篇）——搜索关键变量

零 写在前面

在练习或比赛中通过Hack交互库获得AC属于作弊行为。 恶意Hack交互库是违反洛谷社区规则的。本文所讲述内容仅供学习交流使用。

用Hack交互库的方法能过题仅仅属于侥幸。 本文介绍了一种方法，并不代表它是能用来通过大部分的交互题的通用方法。这种Hack其实很容易防御。

本文所附带代码仅仅在写本文时可以通过对应题目。如果交互库有更新，这些代码可能会失效。同时因为上一条的原因，这种方法随时可能失效。

Hack交互库的方法很多，本篇是上篇，仅介绍其中一种。下篇会讲解其他的方法（其实是一篇杂谈）↓

谷甚论Hack交互库（下篇）——杂谈

一 什么是交互题？

交互题既用户提交的程序，通过出题人提供的交互库，与判题程序（SPJ）进行交互并获得输入、解答问题。

——引自洛谷官方博客《交互题功能说明》

交互库的实现可以分为两种：函数交互和IO交互。

• 函数交互是将你提交的代码和交互库代码一起编译成一个程序，你可以调用交互库中的函数，交互库也可以调用你实现的函数。你的代码和交互库代码在同一个程序中运行，共享内存、运行时间等。
• IO交互分别编译你的代码和交互库代码，两个程序通过标准输入流的重定向交换数据。这两个程序的内存是独立的。

注意，在洛谷也可以同时使用这两种交互方法。

本文介绍的这种方法用于Hack函数交互。（实际上，IO交互通常也很难Hack，相当于你要Hack SPJ）。所以以下只讨论这一种交互方法。

接下来我们以P1947 猜数为例，介绍搜索关键变量的方法。

二 什么是关键变量？

我们所说的关键变量，应该满足以下几点：

• 是交互库所定义的
• 在交互过程中起关键作用
• 有足够明显的特征让我们认出它

所谓搜索关键变量，就是找到这样的变量，通过读取或者修改它来达到我们的目的的一种方法。

那么，我怎么知道交互库都定义了什么变量呢？

如果你有交互库的参考实现，你可以通过阅读其代码来猜测真正的交互库中都定义了什么变量。如果你没有，你可以思考：假如自己来写这个交互库，应该怎么写？从而猜测交互库中都有什么变量。

例子：P1947交互库的参考实现

在这份代码中，我们可以看到交互库定义了这几个变量：n，c，k和cnt。

其实我们最想找到的变量是k。如果我们能读取这个变量，直接返回它就可以AC了。很遗憾的是，这个变量并不满足上面的第三个条件。

只有cnt满足这三个条件。它代表了我们调用交互库的次数，并输出给SPJ处理。如果我们能把这个数修改成一个较小的值，那就可以无视交互库的调用次数限制从而用O(n)的暴力算法通过此题啦~

所以我们现在的目的很清晰：找到cnt，并且修改它。如果你看到这里已经开始迷惑/出现不理解的地方了，不用担心，请继续往下读。

三 如何搜索？

前面讲到，函数交互将你提交的代码和交互库代码一起编译成一个程序。由于这两者的代码在不同的文件中，你的代码是无法直接访问交互库定义的变量的。然而，代码无法访问，可不代表程序无法访问。

由于是同一个程序，你的内存和交互库的内存是直接共享的，而C/C++的指针提供了访问任意内存的方法。这里简单介绍一下C++中的内存模型，大致分成三类：

• 全局内存包括全局变量，和用static声明的变量。
• 栈内存包括函数中声明的局部变量、函数的参数和返回值（有时候）。栈内存的分配是从高向低的。
• 堆内存是动态分配的内存，如使用malloc函数、new关键字分配的内存，和一些STL使用的内存。

这只是一个简化的内存模型，实际的实现会更加复杂，也与编译器、运行环境、O2优化等有关。总之，大概有一个原则，就是同类内存放一起。

那么我们看到cnt是一个全局变量，应该在全局内存的空间内。我们尝试在全局内存中找到这个变量的地址。那么哪里是全局内存的空间呢？咱也开个全局变量然后它附近的空间就是了。（（（

解决了搜索范围的问题，我们还需要知道搜什么。这就是我们上面说的「明显的特征」的问题了。变量值随操作的变化是最明显的特征，其他的如数值范围、数字的性质等也可以作为识别变量的特征。在本例中，每次调用交互函数cnt的值就会递增，我们可以依据这一点识别该变量。

重新整理一下我们的思路。

1. 确定全局内存的位置（栈内存/堆内存同理）
2. 使用指针扫描附近适当大小的内存
3. 找到一个满足我们要找的关键变量特征的变量位置
4. 读取或修改这个值

剩下的就是代码问题了，以下为P1947的Hack交互库解法的参考实现。截至本文写作时这份代码可以AC。

#define S 1000
extern "C" int Seniorious(int);
int x; // 定义一个全局变量，用来确定全局内存的位置
extern "C" int Chtholly(int n, int c) {
    int *i = &x - 500, *rcnt;
    int a[S];
    for (int j = 0; j < S; j++) {
        i++;
        a[j] = *i;
    }
    // 指针i扫描x附近1000个int的内存，把内存的值缓存到数组a里。我们确信cnt就在这块内存里
    if (Seniorious(1) == 0) return 1;
    // 调用交互库。此时cnt的值已经变化了
    i = &x - 500;
    for (int j = 0; j < S; j++) {
        i++;
        if (*i == 1 && a[j] == 0) break;
        // 再次扫描内存，寻找一个调用交互库前为0，之后变成1的内存位置。我们可以认为这个位置就是找到的cnt
    }
    for (int j = 2; j <= n; j++) {
        *i = 0; // 每次操作前把cnt设置成0，调用次数限制去他妈
        if (Seniorious(j) == 0) return j;
    }
}

四 进阶

例题：P6541 [WC2018]即时战略

和刚才的例题相似，我们仍然可以把交互次数作为关键变量，通过修改它来绕过交互次数限制。但是这个变量不够关键。如果你只会O(n^2)的算法，就算调用次数限制限制不了你，也会因为时间复杂度而TLE。

我们大胆猜测，交互库可能定义了一个数组（假定它叫a），用来记录每个点是否被发现的状态。我们只需要找到这个数组并把它全改成true，就可以快乐AC啦~（实际上，当你打开样例交互库实现的时候发现确实是这样的）

这种比较大的数组通常都是定义在全局内存的，所以我们仍然要在全局内存里找。不过这有点困难，因为我们要查找一个数组的位置。

我们可以先扫描一遍内存，然后维护一个这个数组可能在的位置的列表。每次更新时筛去这个列表中不合法的元素，筛到只剩一个时就算找到了。（如果筛到最后一个都不剩，说明你失败了）

伪代码：

list<some_type*> b;
扫描内存，把所有符合a的初始状态的位置加入b
while (b.size() > 1) {
    随机探索，设这次修改把a[z]变成了v
    foreach (x in b) {
        if (x[z] != v) {
            remove x from b
        }
    }
}
a = b.front()

另外，如果你不知道扫描内存应该扫多大范围，你可以捕获段错误然后无脑扫描到出现段错误为止。本文的下篇有讲这个内容。链接

题外话：Hack了一晚上终于A了，感觉踩交互库比正解都难写（）于是就成为了本题最快+最短AC代码（（（（（

Extra 练习题（Hack交互库这种东西真的有练习的必要么）

这种东西就没啥推荐题目了（）可以去洛谷主题库里找一些函数交互题来做。

在尝试做这些练习题之前，请谨记本文「写在前面」一节中的内容。