UOJ 2016 [APIO 2016] Gap

传送门

思路

  唉，我太弱了，什么都不会，题也做不来。这道题简直就是利用交互题的名字来降低难度的，但是我还是一点都不会做……

  对于子任务一，要求最多只能查询 n+12 n + 1 2 $\frac {n + 1} {2}$ 次。我们可以从两边向中间逼近，一次确定两个数，这样就能够在规定次数内确定所有的数。数都到手了还不会做？唉，我太弱啦！

  对于子任务二，计数器等于查询次数 + 查询到的数，注意计数器最多可以到 3n 3 n $3n$（没读题的我默认最多为 n n $n$ QAQ）。首先我们总得确定数的范围是吧，这会花费 n+1$n+1$$n + 1$ 次查询。对于中间的，我们把它分成 n−2 n − 2 $n - 2$ 个块，然后分别查询。最后的答案就是块与块之间的最小值减去最大值（不要忘了一开始的最小值和最大值）。为什么呢？如果每一块中恰好有一个数，这显然正确，否则答案一定出现在跨过至少一个块的地方，这还是由一个最小值减去最大值得来的，不会是一个块内产生的答案。

参考代码

#include "gap.h"
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int maxn = int(1e5) + 5;
int n;
long long a[maxn];

LL solve1()
{
    LL min = 0, max = LL(1e18);
    int cntL = 1, cntR = n;
    while (cntL <= cntR)
    {
        MinMax(min, max, a + cntL, a + cntR);
        min = a[cntL] + 1;
        max = a[cntR] - 1;
        cntL++;
        cntR--;
    }
    LL ans = 0;
    for (int i = 2; i <= n; i++)
        ans = std::max(ans, a[i] - a[i - 1]);
    return ans;
}

LL minVal[maxn], maxVal[maxn];

LL solve2()
{
    LL min = 0, max = LL(1e18);
    MinMax(min, max, &min, &max);
    if (n == 2) return max - min;
    LL step = (max - min - 1) / (n - 2);
    LL cnt = min + 1;
    for (int i = 1; i < n - 2; i++)
    {
        MinMax(cnt, cnt + step - 1, &minVal[i], &maxVal[i]);
        cnt += step;
    }
    MinMax(cnt, max - 1, &minVal[n - 2], &maxVal[n - 2]);

    LL ans = 0;
    cnt = min;
    for (int i = 1; i <= n - 2; i++)
    {
        if (minVal[i] == -1) continue;
        ans = std::max(ans, minVal[i] - cnt);
        cnt = maxVal[i];
    }
    ans = std::max(ans, max - cnt);
    return ans;
}

LL findGap(int type, int N)
{
    n = N;
    if (type == 1) return solve1();
    else return solve2();
}

交互题

  由于这是第一道交互题，这里总结下交互题怎么做。

交互题大致形式

  一般来说是这样哈，反正我也没做过什么交互题。

  在我的印象中，大部分题目都是交互库处理的输入，交互库才是老大，因此你的程序不需要写 main 函数，也不需要写输出函数，只需要按题目要求返回交互库的调用，或者告诉交互库你的需求或答案。

  不过好像还有种交互题是利用输入输出进行交互的，不是很了解。感觉这种东西交互库没法写吧；像这道题交互库就很好实现……

Windows 平台下（Dev-C++）

  首先你要新建个文件夹……因为交互题需要的文件太多啦！

  一般来说（至少在 UOJ 上），会给你所谓的交互库，是一份源代码（以及头文件）。这也是为什么我觉得这种交互题要靠谱些，利用输入输出进行交互的怎么本题测试啊 QAQ。

  怎么编译呢？每次敲 G++ 太累了，可以写一个批处理文件，用的时候提前打开一个控制台就好啦！

@echo off
g++.exe gap.cpp grader.cpp -o gap.exe -static -DLOCAL -g3 -Wl,--stack=1073741824 2> compile.log
type compile.log
del compile.log

  首先，g++.exe 需要输入编译器全路径（如果你没有环境变量的话），这里为了节省空间就不写了。可以在 Dev-C++ 里面随便编译一个东西，看看编译日志，就知道全路径了。紧接着写两个要编译的源文件：gap.cpp 和 grader.cpp，分别是最后要提交的东西和交互库。注意，gap.cpp 中需要包含交互库提供的 gap.h。

  -o 编译指令表示输出的文件，这里我们就叫做 gap.exe 就好了（不要脑残打成 gap.cpp 了）。-static 可以不加，只是为了静态编译，如果运行出错可以试试，一般都不会。-DLOCAL 是自定义的宏，可以不加。-Wl,--stack=... 表示设置栈空间，如果题目说了开大栈空间就加上，否则最好不加，免得本地过交上去就 RE。最重要的一点是 -g3 编译选项，表示打开调试开关，打开了这个你才可以用 Dev-C++ 调试（使用 gdb 的犇犇？既然你都用 gdb 了那你还来看我这个干吗？）

  最后设置输出文件，2> 表示错误输出（stderr）。g++ 编译器的错误和警告信息均会输出到错误输出中。如果错误输出为空，说明编译成功；否则编译有错（由于没有打开警告的编译开关，因此并没有警告信息）。

  最后，我输出了编译错误信息并在硬盘中删除了它（为什么要删，我开心啊！）。如果编译成功，那就成功了。

  但是你想双击批处理程序来编译，结果就一闪而过了；加了个 pause 后，哪怕编译成功也会暂停，感觉很不爽，怎么办呢？这时需要手动判断一下结果。在编译成功时，g++ 的返回值为 0，否则为非零。然后我也不会了……不管了，将就用吧。

Ubuntu 平台下

  唉，我太弱了，连 Linux 都不会用。下面讲一下怎么用 NOI Linux。

1. “批处理”
     Linux 下，没有 bat 一说，而是直接用一个没有后缀名的文本文件代替。
     方法：新建空白文件（右键），取名为 compile，无需后缀名。输入以下命令：

g++ gap.cpp grader.cpp -o gap -DLOCAL -g3 2> compile.log
cat compile.log
rm compile.log

  直接写 g++。

  对比一下，与 Windows 相比有几个区别，但所幸区别不大：不用打 @echo off（用于关闭回显）；不能指定栈空间（-WL,--stack=...）；type 变成了 cat；del 变成了 rm。那如何设置栈空间呢？（不设了，够用）

1. 运行
     与 Windows 不同的是，不能直接输入文件名运行，必须要加上“当前目录”的标记。与 Windows 又不同，Linux 路径中的斜杠是正的：

./compile
./gap

  另外，compile 文件需要给它运行的权限。方法是点击右键，在属性里面改。

  这样就能编译并运行了。

1. 使用 Guide 调试
     直接调试就好啦（虽然好像难用得****）！记住要打开 -g3 编译选项。