「Codeforces」Good Bye 2019

A. Card Game

比较最大值即可

给出长度为 $n$ 的序列 $a_i$ ，问是否存在一个子区间 $[l, r]$ 满足 $\max_{i=l}^{r} a_i - \min_{i=l}^{r} a_i \ge r - l + 1$

$n \le 2 * 10^5$

考场上写了个比较复杂的做法，实际上只需要检验所有相邻两个位置是否满足即可

给出一个长度为 $n$ 的序列 $a_i$ ，你需要在末尾添加 $d(d \le 3)$ 个数，使得 $\sum_{i=1}^{n+d} a_i = 2 * \bigoplus_{i=1}^{n+d} a_i$

$n \le 10^5$

只需要添加一个数 $X$ . 设原序列的和为 $S_1$ ，异或和为 $S_2$

乘二相当于二进制下左移一位，于是从低到高位考虑，若 $S_1$ 该位上的值不等于 $S_2$ 下一位上的值，则调整 $X$ ，使得 $S_2$ 的下一位变成 $S_1$ 该位的值

交互题.

有一个长度为 $n$ 的序列 $a_i$ ，和参数 $m, k$

给出 $n$ 和 $k$ ，你可以向交互库询问一个大小为 $k$ 的下标集合，交互库会返回这个下标集合中权值第 $m$ 小的数的下标和权值

用不超过 $n$ 次询问求出 $m$

$1 \le k < n \le 500$

[交互]

考场降智，没做出来

询问 $k+1$ 次，第 $i$ 次询问 $[1, i) \cup (i, k+1]$ 这个集合。总共会返回两种不同的值，其中较大的那个值的出现次数就等于 $m$

证明略

平面上 $n$ 个互不相同的点，要求分成两个非空集合，使得不存在一种点对之间的距离长度 $x$ 满足 $x$ 既可以被同一集合内的两个点连出，又可以被跨集合的两个点连出。

$n \le 10^{3}, -10^{6} \le x_{i},y_{i} \le 10^{6}$

[构造]

考虑按 $x + y$ 的奇偶性分集合，显然能够满足题意。但是这样分出来不一定满足集合非空，于是考虑 $x + y$ 均为偶的情况怎么做。为奇的时候可以平移成为偶的情况。

不断旋转并缩小坐标系，即 $(x, y) \Rightarrow (\frac{x+y}{2}, \frac{x-y}{2})$ (类似于曼哈顿转切比雪夫距离)，再检查此时是否所有点 $x + y$ 的奇偶性相同。若不全相同则输出答案，否则继续旋转缩小。这样最终一定可以区分出两个集合。

感性理解一下正确性

因为在旋转缩小坐标系时，一定是成比例缩小的，所以任意两个点的坐标一定不相同

但是如果无穷无尽地缩小的话，点坐标会越来越接近 $(0, 0)$ ，会越来越趋近相等，所以会在相等前的那一次缩小被分出奇偶性

定义一个区间 $[l, r]$ 是好的，当且仅当 $r - l + 1$ 是 $[l, r]$ 中 $1$ 的个数的倍数

给出一个长度为 $n$ 的01串，统计好区间的个数

$n \le 200000$

[根号平衡]

考虑固定右端点 $r$ 统计答案，若区间 $[l + 1, r]$ 合法，则需要满足 $r - l = k \cdot (sum_r - sum_l)$ . $sum_i$ 表示前缀和数组

发现要统计 $l, k$ 这两维的信息，考虑根号平衡，设参数 $T$

若 $k \le T$ :

$l - k \cdot sum_l = r - k \cdot sum_r$ . 枚举 $k$ ，用个桶统计合法 $l$ 的个数即可

复杂度 $O(n\cdot T)$
若 $k > T$ :

$\displaystyle sum_r - sum_l = \frac{r - l}{k} \le \frac{n}{T}$ . 枚举 $sum_l$ ，则得到对应的 $l$ 的范围，统计存在其中存在多少个合法 $k$ 即可

复杂度 $O(n \cdot \frac{n}{T})$

$T$ 取根号时最优，复杂度 $O(n\sqrt n)$

给出一个长度为 $n$ 的序列 $a_i$ ，满足 $i - n \le a_i \le i - 1$

找出一个下标集合，满足

$n \le 10^6$

[构造] [思维]

好巧妙的一道构造题.

题目条件转化为 $1 \le i - a_i \le n$ ，即 $i \rightarrow (i - a_i)$ 会构成一棵基环内向树，考虑把环提出来会发生什么

\begin{aligned} i_1 - a_{i_1} &= i_2 \\ i_2 - a_{i_2} &= i_3 \\ &\vdots \\ i_k - a_{i_k} &= i_1 \\ \end{aligned}

把上述式子相加，发现