P16420 [IATI 2022] Ones

有一个隐藏的 $N$ 位数组 $a_0, \ldots, a_{N-1}$。每次询问时，你可以选择序列中的若干个位置，并将这些位置上的比特翻转。将 $0$ 翻转为 $1$，将 $1$ 翻转为 $0$。每次询问后，你会得到新数组中由连续 $1$ 组成的最长子数组的长度。这类询问的效果是持续的，即之前询问中被翻转的比特将 **保持翻转**，直到再次被翻转回来。 你希望在完成所有询问后，找出数组中最长的全 $1$ 子数组（如果存在多个，找出其中任意一个）所在的位置。请编写一个程序，用尽可能少的询问次数来达成这一目标。 ### 实现细节 每个测试包含 $T$ 个子测试。 你的程序需要实现一个具有以下原型的函数： ```cpp std::pair find_longest_subarray_of_ones(int n); ``` 该函数在每个测试中会被调用 $T$ 次，并接收整数 $N$ 作为参数——即隐藏数组的长度。函数应返回一个对 $\{l, r\}$，其中 $l$ 是该子数组最左端元素的下标，$r$ 是该子数组最右端元素的下标。 你应当使用函数 `flip_bits` 来发起询问： ```cpp int flip_bits(const std::vector &flips); ``` 它接收一个长度为 $N$ 的比特向量 $flips_0, \ldots, flips_{n-1}$，其中 $flips_i = 1$ 表示 $a_i$ 应被翻转。在翻转指定的比特后，该函数返回隐藏序列中最长连续 $1$ 子数组的长度。 你必须将包含 `find_longest_subarray_of_ones` 函数的文件 `ones.cpp` 提交到系统中。该文件可以包含其他对你的工作必要的代码和函数，但不得包含 `main` 函数。同时，你不得从标准输入读取数据，也不得向标准输出打印内容。你的程序还必须通过预处理器指令包含头文件 `ones.h`： ```cpp #include "ones.h" ``` ### 本地测试 提供了文件 `Lgrader.cpp`，你可以将其与你的程序一起编译来测试。它将首先读入该测试的子测试数 $T$，接着读入每个子测试的描述。对于每个子测试，首先给出整数 $N$，下一行给出 $a_0 \dots a_{N-1}$。如果程序运行正确，它会输出 $1$ 以及你所使用的最大询问次数；否则输出 $0$。

无

无

### 样例交互 设初始数组为 $1, 0, 1$。通信的一种可能过程如下： | 选手的函数 | 裁判程序 | |:-:|:-:| | | 调用 `find_longest_subarray_of_ones(3)` | | 调用 `flip_bits({0, 0, 0})` | 返回值 $1$ | | 调用 `flip_bits({0, 1, 0})` | 返回值 $3$ | | 返回 $\{0, 2\}$ | | ### 数据范围 - $T = 5$ - $1 \le N \le 10^4$ - $0 \le a_i \le 1$ 如果你的程序对任何子测试出错，你的得分为 $0$。否则，你在本题获得的分数取决于你的程序解决单个子测试所使用的最大询问次数 $Q$。你获得的分数为： 若 $Q \geq 60$： $$ \left(\frac{60}{Q}\right)^{0.215} \times 70 $$ 否则 $Q < 60$，分数为： $$ -\frac{3}{2}\max(40, Q) + 160 $$ 翻译由 DeepSeek V4 Pro 完成