ICPC2023西安站

A

$\quad$ 针对 $\text{rad}(i)$ 的定义入手：

$\quad$ 我们试图把式子中含 $i+r$ 和 $i-r$ 的部分统一成同一个形式： $\quad$ 令 $C_i=2A_i-ki$ ，则有： $\quad$ 接下来令 $D_i=C_i-C_{i-1}$ ，则 $\text{rad}(x)$ 满足： $\forall 1 \le r \le \text{rad}(x)$ ， $\sum\limits_{i=x-r+1}^{x+r} D_i=2b$ 。

$\quad$ 当 $r=1$ 时： $D_x+D_{x+1}=2b$ 。

$\quad$ 当 $r>1$ 时有： $D_{x-r+1}+D_{x+r}=0$ 。不难发现 $x-r+1$ 与 $x+r$ 奇偶不同，则令 $G_i=(-1)^iD_i$ ，则有 $G_{x-r+1}=G_{x+r}$ 。

$\quad$ 当询问 $\text{rad}(x)$ 时，应先判断 $D_x+D_{x+1}=2b$ 是否成立，若不成立则 $\text{rad}(x)$ 自然为0，若成立则找到最大的 $len$ 使逆序段 $[x-len+1,x]$ 与正序段 $[x+1,x+len]$ 完全相同。考虑用二分答案+哈希来解决这个问题。

$\quad$ 因此，需要维护一个数据结构，要求单点修改差分序列以及维护正序、逆序的区间哈希值，可以用线段树实现，单词修改的时间复杂度为 $O(logn)$，单次查询的时间复杂度是 $O(log^2n)$ 。

E

$\quad$ 竞赛图中离心率 $\le 2$ 的点通常称为king。另记：

$\quad$ 即所有“打败” $x$ 的顶点集合。

$\quad$ 先考虑存在点的出度为 $n-1$ 的情况，这种情况下king只可能是那个出度为 $n-1$ 的点，因此可以直接输出 Not found。

$\quad$ 排除掉上述的情况，先试图证明竞赛图一定有至少一个king。考虑用数学归纳法证明。

$\quad$ 当竞赛图只有三个点时，只存在 a->b->c->a 和 a->c a->b b->c 两种情况，都存在king。

$\quad$ 当竞赛图有 $k$ 个点且存在king时，设其中一个king为 $a$ ， $a$ 能一步到达的点集为 $B$ ，只能两步到达的点集为 $C$ 。现在考虑加入一个新的点 $d$ ，分几种情况讨论：

$\quad$ 1.a->d ，显然 $d\in B$ ，在这个 $k+1$ 个点的竞赛图中 $a$ 仍然是king。

$\quad$ 2. d->a且 $\exist\ b \in B$ 使得 b->d ，则 $a$ 可以通过 $b$ 两步到达 $d$ ，即 $d \in C$ ，在这个 $k+1$ 个点的竞赛图中 $a$ 仍然是king。

$\quad$ 3. d->a且 $\forall\ b \in B$ 使得 d->b ，则令 $B'=B\bigcup {a}$ ， $C'=C$ ，$d$ 作为这个 $k+1$ 个点的竞赛图的king。

$\quad$ 因此可以证明：竞赛图一定存在一个king。

$\quad$ 接下来证明竞赛图中出度最大的点一定是king，考虑用反证法证明：设竞赛图里出度最大的点为 $x$ ，若存在点 $y$ 使得 $x$ 无法两步之内到达 $y$ ，则 $y$ 一定可以直接到达 $x$ 以及 $x$ 可以直接到达的点，即 $y$ 的出度至少为 $x$ 的出度加一，这样 $x$ 就不是出度最大的点了，矛盾。即证得竞赛图中出度最大的点一定是king。

$\quad$ 因为找到的king的出度一定不为 $n-1$ ，$N^-(x)$ 一定不为空，接下来证明：由 $N^-(x)$ 中的点构成的竞赛子图中的king一定也是整张图的king。不妨设 $y$ 为 $N^-(x)$ 中的点构成的竞赛子图中的king，显然 $y$ 一定能在两部之内到达 $N^-(x)$ 中的点，且 $y$ 可以直接到达 $x$ ，而剩余的点都可以通过 y->x->z 来两步到达。因此 $y$ 也是整张图的king。

$\quad$ 令 $x'=y$ ，以此法还能再找到一个king $z$ ，因为 $z \in N^-(y)$ 而 $y \in N^-(x)$ ，所以 $z$ 和 $x$ 一定不是同一个点，这样就找到了三个互不相同的king。

G

$\quad$ 先对 $n$ 进行质因数分解：

$\quad$ 再将 $p$ 和 $q$ 以同样的方式表示：

$\quad$ 显然 $b_i+c_i \le d_i$ ，且有：

$\quad$ 可以注意到 $b_i-c_i$ 是独立的，且 $b_i-c_i \in [-d_i,\ d_i]$ ，可以在这个区间内任取，由乘法原理可得， $r$ 的不同值个数为 $\prod\limits_{i=1}^m2d_i+1$ ……吗？

$\quad$ 显然不是，因为有 $p\leq q$ 的限制存在，应该先排除 $p=q$ 的情况再加上剩下情况数的一半，答案为： $\frac{(\prod\limits_{i=1}^m2d_i+1)+1}{2}$ 。

H

$\quad$ 假设第 $i$ 名选手一路晋级到最后，记 $L_{i,j}$ 为前 $j$ 场比赛选手 $i$ 可能遇到的对手所处在的区间左端点，同理有 $R_{i,j}$ ，不难发现，选手 $i$ 能打赢前 $j$ 场当且仅当他是 $[L_{i,j},R_{i,j}]$ 中级别最高的那个。为使选手尽可能赢更多的比赛，我们要将区间外级别小于 $a_i$ 的选手的级别与区间内级别大于 $a_i$ 的选手的级别交换。交换能否成功要看两点：交换次数是否充足以及可供交换的人是否充足。

$\quad$ 考虑级别从小到大处理，用树状数组来维护需要交换以及可供交换的选手数量即可，时间复杂度为 $O(2^nn^2)$ 。

N

$\quad$ 纯粹的模拟题，注意实现细节即可。