ICPC 杂题选做

Escape from the Island

有一幅有向图，你一开始在某一个结点上。

每一次时刻你可以选择移动一步或者原地休息。

若选择移动一步，则可以花费一个时间单位向所有与它 有边相连 的点移动，即可以沿着有向边反向走。这个操作最多连续进行 $k$ 次。
若选择原地休息，也花费一个时间单位，并且若这个点有出边，则会随机沿着一条出边走。

求从每一个点开始到达 $n$ 最坏情况 下的最小时间，或返回无解。

$1 \le n \le 10^5, 1 \le k \le 50$

解法

首先由于求的是最坏情况，因此原地休息时默认会走到代价最大的后继。

设状态 $f{i,j}$ 表示第 $i$ 个点，还能连续走 $j$ 步的最小代价，那么最终输出的就是 $f{i,k}$。

然后考虑转移，显然要分 $j=0$ 与 $j\ne 0$ 两类讨论：

$j=0$ 时，$f_{i,j}$ 下一个状态只能是 $f_{v,k}$，因此有 $f_{i,j}=\max_{i\to v}\{f_v,k\}+1$。
$j\ne 0$ 时，$f_{i,j}$ 下一个状态可以是休息后得到 $f_{v,k}$，也可以是走一步得到 $f_{v,j-1}$ 因此有 $f_{i,j}=\min\{\min_{i\to v \lor v \to i}\{f_{v,j-1}\}\max_{i\to v}\{f_v,k\}\}+1$。

但是这样子的话 $f_{n,j}$ 就是终止状态了，我们应当把它变成起始状态。

其实也不难，对上面的全部建反边就行，然后根据转移分为 $\max, \min$ 两种边。

显然 $\min$ 边可以直接转移，考虑到我们的转移方式是 bfs 且边权为 $1$，因此转移 $\max$ 边时若一个点所有 $\max$ 边都被转移过了，那么当前这一条边一定是取到了 $\max$，可以当做 $\min$ 边来转移。然后处理一下原地休息的细节就行了。

不难发现这样子的话每一个点最多被转移 $k$ 次，由于只有 $f_{i,k}$ 的转移代价之和是 $O((n+m)k)$ 的，因此直接转移就是 $O((n+m)k^2)$ 的。

于是就做完了。

Building Blocks

有一个 $n\times m$ 的矩阵，每一个元素都有一个权值。

现在对于所有 $k \in [1, n+m]$，告诉你 $\max_{i+j\in[k-1,k]}\{a_{i,j}\}$，并告诉你若干个 $a_{i,j}$，问你有多少种可能的矩阵。

$1\le n, m \le 10^5, a_{i,j}\le 10^9$

解法

首先注意到这个问题可以转化为序列问题，然后发现其实就是告诉你相邻两项的 $\max$，然后某一些位置钦定了，只是有一些序列中的元素计算贡献时能选的更多一些而已，本质上没什么区别。

你可以先推一推式子，或者手模一下样例，会发现不是不能做，但是会非常屎。

因此考虑用 DP 解决，这里我们考虑对 题目给出的序列 进行 DP。

我们不妨设 $f_{i,0/1}$ 表示前 $i$ 项都满足条件，且最后一项有余地/恰好满足的方案数。

显然这里最后一列需要恰好满足，因此答案是 $f_{n+m,1}$。

考虑我们对于每一项都能求出它当前最大到达了多少，显然超过给出的阈值就可以直接跳出了。

我们显然还能求出每一项有多少个点是自由的。

然后考虑转移，简单讨论一下 $0\to 0, 0\to 1, 1\to 0, 1\to 1$ 四种转移即可。

Hold the Line

单点修改区间前驱后继

$n \le 5\times 10^5, q \le 10^6$

解法

首先显然可以树套树，但是常数太大估计过不了。

然后注意到可以离线转化成数点，听说就能两 $\log$ 过。

其实还可以底层分块然后用亚 $\log$ 数据结构艹过去。

反正是垃圾题，不说了

Erasing Numbers

给你一个排列，每一次可以选出三个相邻的数然后删除最大值和最小值放回原位，问有哪些数可能会活到最后。

$n\le 5\times 10^3$

解法

首先这种只与比较有关的判定性问题可以想到转成 $01$ 序列或一些类似的东西，这里考虑转成 $\pm 1$ 序列。

不难发现序列若同时存在 $\pm 1$ ，则一定存在一个三元组既包含 $+1$ 又包含 $-1$。

那么可以考虑不断消这种三元组，因此若转化后的序列和为 $0$ 则必然有解。

考虑不为 $0$ 的情况，现在我们就要让它尽可能变为 $0$。

注意到对于连续三个相同的，我们可以消去其中两个。

我们先假设序列和 $>0$，显然 $+1$ 过多要消去。

不难发现，若一段区间的和 $\ge 3$，就一定可以消去 $2$。

因此不断求最大字段和然后 $\ge 3$ 就 $-2$，最后看看能消掉多少。

显然如果能消到 $0$ 及以下则有解，否则没有。

$-1$ 显然同理。

复杂度 $O(n^2)$。

Constructing Ranches

给定一棵树，点有点权，问有多少条路径使得取出其上面的所有点权可以组成一个多边形，必须每一个数值都用上。

$1 \le n \le 2\times 10^5$

解法

首先这种阴间 DS 肯定要先把它要求的东西转化得阳间一些。

考虑形成一个多边形的条件，其实就是最大值的两倍小于和。

然后考虑怎么数路径数量，这个数据范围不难想到点分。

考虑对于一个分治中心怎么处理。

显然与根有关的路径可以直接求，那么接下来只需要考虑子树间的贡献

考虑对于一条前缀链，它的和为 $l$，最大值为 $x$

考虑剩下的所有链当中，能与当前点产生贡献的，一类是最大值小于当前的，那么真实的最大值就以当前这个为准，因此只需要考虑这一部分中和小于某个值，具体来说就是 $2x-l< L, X<x$，另一类刚好反过来应该是 $X\ge x, 2X-L<l$

发现这是一个二维数点，那么已经有一个显然的数套树做法了。

考虑利用离线优化掉一维，因此注意到 $x$ 这一维可以考虑通过扫描线消除。

注意到这里扫描线需要把这个点分中心所形成的子图中的所有点带权排序，因此同一子树内会被多算。

那么就还需要清除自己与自己的贡献，这个简单容斥一下就好。

容斥后复杂度是 $O(n\log^2 n)$

Incoming Asteroids

有 $n$ 个点，有一些人在观察这些点，每一个人最多观察 $k$ 个点。

每一个都有一个阈值 $y$，若他观察的所有点的点权之和超过了 $y$ 他就走了。

有 $q$ 次操作，每次操作要么加入一个新人，要么给一个点加一定的权值。对于后者你还需要输出这次操作后有哪些人走了。

强制在线

$n, q \le 2\times 10^5, y \le 10^6, k \le 3$

解法

首先考虑根号分治，发现并没有优化于是弃了。

然后意识到没有什么平均复杂度的数据结构可以实现这个问题，因此考虑均摊复杂度的结构。

那么不难想到每一个点超过一定阈值就暴力重构，否则这个点也不可能被删除。

不难发现某一个人观察的所有点若在上次重构后新增的量都没超过了这个人剩下的观察量的 $\frac{1}{k}$，则他不可能走开。

而如果超过了，重构次数就是 $\log$ 级别的。

因此直接对于每一个点维护一个 std::set 记录人极其阈值，然后每一次更新就暴力重构这个人，复杂度就是 $O(n\log^2 n)$ 的。

Traveling in the Grid World

有一幅 $n\times m$ 的网格图，你每一次可以花费两个格点间欧几里得距离的代价从一个格点走到另一个，你需要保证相邻两次行走斜率不同且每次不能经过其他格点，问你 $(0,0)\to (n,m)$ 的最小代价。

多组数据 $\sum \max\{n,m\} \le 10^6$

解法

首先毛估估感觉只需要最优解折一次。

其实是可以证明的，考虑若你选取一条拐点数 $>1$ 的路径，你可以只取其中一个拐点，然后连成一条一个拐点的路径。

若路径经过了整点，则以哪个整点为拐点继续调整，不难发现只会越来越优。

然后考虑找最优解。

毛估估感觉答案就在 $(0, 0)\to (n, m)$ 连成的线附近，事实也是这样。

可以用类似的调整法证明，不赘述了。

所以加上 $\gcd$ 的复杂度是 $O(n\log n)$ 的。

The Journey of Geor Autumn

给你 $n, k$，问你有多少个 $1\sim n$ 的排列满足 $\forall i \in [k+1,n], a_i > \min_{j\in[i-k,i-1]}{a_j}$

$n, k \le 10^7$

解法

不难发现最小值一定要在前 $k$ 个中，因此枚举其位置。

若它在第 $i$ 个，那么前 $i-1$ 个随意放，后面变成了一个 $n$ 更小的子问题。

那么设当前 $k$ 下，$n=i$ 的答案为 $f_i$，有：

$\begin{aligned} f_i &=\sum_{j=1}^k f_{i-j}\times (j-1)! \times \binom{i-1}{j-1} \\ &=\sum_{j=1}^k f_{i-j}\times (j-1)! \times \frac{(i-1)!}{(j-1)!(i-j)!} \\ &=\sum_{j=1}^k f_{i-j}\times \frac{(i-1)!}{(i-j)!} \\ &=(i-1)!\sum_{j=i-k}^{i-1}f_j\times \frac{1}{j!} \end{aligned}$

直接前缀和优化 DP 即可。

复杂度 $O(n)$

Sky Garden

有 $n$ 个半径 $1\sim n$ 递增的以原点为圆心的同心圆，被 $m$ 条过原点的直线平均分为 $2m$ 个部分。

取出所有交点看作点，所有弧和线段看作对应长度边权的边，问形成的图上两两间最短路长度之和。

$n, m \le 500$

解法

首先考虑按同心圆分层，从内到外依次是 $1\sim n$ 层。

考虑不同层的两个点，显然层数大的那一个要先走到同一层，因此转化为了同一层的问题。

考虑同一层的两个点要么走弧要么走两条半径，数据范围允许直接枚举。

算上一些零碎的其他贡献再算一些系数就做完了。

可能有一些 border case，判一下就好。

Ragdoll

有 $n$ 个可重集，初始每一个可重集里面只有一个元素。

定义一个可重集 $S$ 的权值如下：

$\sum_{u, v \in S \land u<v}[\gcd(u,v) = u \oplus v]$

其中 $u \oplus v$ 表示 $u,v$ 按位异或后的结果。

有 $m$ 次操作，每一次操作可以新建一个包含某个元素的可重集，或者合并两个可重集，或者单点修改某个元素。

求每一次操作后所有可重集的权值之和。

$n\le 10^5, m \le 2\times 10^5, 1\le a_i \le 2\times 10^5$

解法

毛估估一下，感觉满足 $\gcd(u,v) = u \oplus v$ 的二元组应该不多。

打表发现对于同一个 $u$，能与它成立的 $v$ 最多也就 $70$ 个左右，可以直接预处理出来然后暴力扫。

因此直接暴力启发式合并就做完了。

复杂度大概是两只 $\log$ 的。

Strange Memory

给定一棵以 $1$ 为根的有根树，点有点权。

问你：

$\sum_{i=1}^n\sum_{j=i+1}^n [a_i \oplus a_j = a_{\text{lca}(i,j)}](i \oplus j)$

其中 $x \oplus y$ 表示 $x,y$ 按位异或后的结果。

$n \le 2\times 10^5, a_i\le 10^6$

解法

这种 lca 有关的树上为题不是虚树就是 DSU on tree。

这里显然可以考虑维护出一个关于其他子树的集合，然后在 lca 处计算贡献。

现在相当于问你一个集合中所有 $\oplus a_j$ 之后 $=a_{\text{lca}(i,j)}$ 的元素 $i$ 与 $j$ 的异或值之和。

考虑对于每一个值 $a_j$，维护出它每一个元素二进制下每一位几个 $1$ 几个 $0$，直接算贡献就行。

复杂度 $O(n\log n \log a)$。

Just Another Game of Stones

给你一个序列 $a$，两种操作：

区间 $a_i \gets \max\{a_i, x\}$
取出区间所有数，加上一堆 $x$ ，玩 nim 游戏，问先手有多少种取第一步的方法使得必胜，若两种方法不同堆或不同量则定义为不同。询问互相独立。

$n, q \le 2\times 10^5, a_i \le 2^{30}$

解法

首先考虑给你这个序列，你怎么求答案。

考虑我要必胜，那么我取完之后一定要异或和为 $0$。

换言之，假设序列当前异或和是 $s$，我是 $x$，那么方案数就是 $\sum x > x\oplus s$。

简单分析一下发现维护出拆位后每一位 $0/1$ 出现次数就能求出答案。

因此考虑直接上 SegBeats!，发现这是个支持快速合并的信息。

因此似乎 $O(n\log n \log a)$ 做完了。