IOI2020国家集训队作业试题乱做 Part 2

难度标签：$\color{red}\texttt{[HARD]}$，$\color{blue}\texttt{[NORMAL]}$，$\color{green}\texttt{[EASY]}$。

CF555E Case of Computer Network

$\color{green}\texttt{[EASY]}$

考虑一个点对 $(s,t)$。若 $(s,t)$ 之间有两条路径，那么可以构造一个环，显然最优。否则，即 $(s,t)$ 之间只有一条路径，这意味着路上存在割边。

考虑先缩边双，那么边双之内的边一定存在一种定向方案使得边双内节点之间均合法。然后就剩下了一棵树，只需要使用树上差分，计算对于每一条边，有多少路径要从下至上经过，多少路径从上至下经过。若两种路径均有，则无解。

CF553E Kyoya and Train

$\color{blue}\texttt{[NORMAL]}$

先列个柿子，显然设 $\text{dp}_{u,i}$ 表示当前在 $u$ 点，已经经过了 $i$ 的时间，期望还需要多少代价可以到达。那么有：

• 若 $u=n$ 且 $i\le t$，$\text{dp}_{u,i}=0$。
• 若 $u=n$ 且 $i> t$，$\text{dp}_{u,i}=x$。
• 若 $u\ne n$ 且 $i\ge t$，$\text{dp}_{u,i}=x+\text{dis}(u,n)$。
• 否则 $\text{dp}_{u,i}=\min_v\Big\{\sum_{j=1}^{t} p_{e,j}\times \text{dp}_{v,i+j}+c_e\Big\}$，其中 $e$ 是当前边。

直接转移是 $\mathcal{O}(mt^2)$，考虑优化。

令 $\text{val}_{i,j}$ 表示当前已经经过 $j$ 的时间，准备经过第 $i$ 条边，还需要的期望代价，那么：

$$ \text{val}_{i,j}=\sum_{s=1}^t p_{i,s}\times \text{dp}_{b_i,j+s} $$

发现这实际上很像一个差卷积的形式，所以考虑一下多项式。又由于这个东西和时间相关，所以考虑半在线卷积，即分治 $\text{FFT}$。

考虑先递归右半边，然后考虑右半边的 $\text{dp}$ 数组对左半边的 $\text{val}$ 的贡献，在分治树的叶子节点取 $\min$ 即可。具体实现细节较多。时间复杂度 $\mathcal{O}(mt\log^2t)$。

本题提示了我一个看起来很显然的东西——分治并不一定要先处理左半边，而是可以灵活处理。有时候看到卷积形式，但是需要使用一些还待求解的值，则考虑分治 $\text{FFT}$。然后关键就在于如何考虑一半边对另一半的贡献了，这一般都可以通过若干次卷积解决。

CF566C Logistical Questions

$\color{red}\texttt{[HARD]}$

发现函数是下凸的，所以必然存在一个点最优，越往外则带权距离和越大。

那么考虑一步一步朝着更优的解出发，若当前在 $u$，考虑朝着儿子 $v$ 去，那么假设向着 $v$ 的方向移动 $x$ 的距离，那么距离和为：

$$ \sum_{i\notin\text{subtree(v)}} (\text{dis}(i,u)+x)^{3\over 2}+\sum_{i\in\text{subtree(v)}} (\text{dis}(i,u)-x)^{3\over 2} $$

由于函数下凸，所以能让答案更小的 $v$ 必然只有 $\le 1$ 个。因此，我们只需要判断这个权值的趋势即可，既然只要找趋势，就只需要看其导数。

令 $x\leftarrow 0$，那么上面柿子的导数是：

$$ \dfrac{3}{2}\sum_{i\notin\text{subtree(v)}} (\text{dis}(i,u)+x)^{1\over 2}-\dfrac{3}{2}\sum_{i\in\text{subtree(v)}} (\text{dis}(i,u)-x)^{1\over 2} $$

其中 $x$ 是小量可以忽略。

那么就只需要从 $u$ 开始 $\text{DFS}$，找到每个节点的上述权值，然后看减去哪一个子树的值的两倍可以使得该值 $<0$，到这个子树内即可。

但是这样是 $\mathcal{O}(n^2)$，考虑优化。明显可以根据点分治的思想进行计算，这样就只需要对 $\mathcal{O}(\log n)$ 的点做上述操作，复杂度 $\mathcal{O}(n\log n)$。

本题告诉我们，对于一般的离散的函数，若其存在一定的性质（比如本题中函数下凸），可以考虑将其看做一个连续的函数，然后通过求导来判断其变化趋势，从而得到其最优解的方向。

同时，点分治的思想可以在各种方面进行运用，比如本题中减少点的枚举个数，思路需要记住。

CF538G Berserk Robot

$\color{blue}\texttt{[NORMAL]}$

发现横坐标、纵坐标的移动次数有些麻烦，可以考虑将坐标系旋转，具体来说，令 $x_i'=x_i+y_i,y_i'=y_i-x_i$，那么发现四种移动分别对应 $(+1,+1),(+1,-1),(-1,+1),(-1,-1)$，这样就可以分离横纵坐标，因为任意一种横纵坐标的移动方案，总有一种移动方式与其对应，于是可以对横纵坐标分别求解，然后组合起来得到其对应的移动方向。

接着就只需要考虑一维的情况，进一步，我们设 $t$ 时刻点 $(x,y)$ 变为 $(\dfrac{x+y+t}{2},\dfrac{y-x+t}{2})$，如果除不尽必然无解，那么移动就变成 $(+1,+1),(+1,0),(0,+1),(0,0)$，更好处理了。

然后就变成现在需要构造一个 $01$ 序列，令前缀和数组为 $s_i$，那么某一个前缀 $s_p$ 加上全体的和 $s_l$ 的若干倍等于一个固定值。

将所有点按照 $p$ 排序，然后两个前缀和之间差分，就可以得到关于 $s_l$ 的一些不等式。解一下然后重新推一边求方案即可。复杂度 $\mathcal{O}(n \log n)$。

本题的 $\text{key observation}$ 在于将坐标系进行旋转，之前机房同学出的题是将移动变为 $x,y$ 中仅有一维变化，而本题中是将仅有一维变化变为两维都变化，这取决于两种等价形式中哪一种较为容易处理。本题这个方式是否依赖于方向数=$+1,-1$ 的组合总数？是否可以拓展到更多移动方向的情况？

CF566E Restoring Map

$\color{red}\texttt{[HARD]}$

考虑距离 $\le 2$ 意味着什么，什么样的点对会距离 $\le 2$。我们发现，对于一条长度为 $4$ 的链，两侧两个点的集合必然交大小为 $2$，且就是链中间两个点。那么这样就可以得到所有非叶子节点之间的连边——判断任意两个集合交大小是否为 $2$，若是则交中两个点有边。

再考虑叶子节点。观察发现，一个叶子节点 $x$ 的集合，必然是所有包含 $x$ 的集合中大小最小的，这样就可以得到所有叶子节点的集合。接着，观察发现，若仅考虑非叶子节点之间的连边，那么叶子节点 $\le 2$ 的集合 $=$ 父亲节点的连边集合，那么暴力判断来找父亲即可。

用 $\text{bitset}$ 就可以做 $\mathcal{O}(\dfrac{n^3}{\omega})$。

还有一些特殊情况 毒瘤，比如 $n\le 2$，或者非叶子节点 $\le 2$ 之类的，还需要特殊判断。

本题不套路，但可以从中找到一些小 $\text{trick}$。首先，本题同样可以从链的情况开始考虑，这就可以判断出第一个性质；同时，短距离的点对之间往往可以找到一些奇怪的规律，例如本题中交为 $2$ 则有边，或者叶子的集合 $=$ 父亲的非叶子节点连边集合。

总之要提高思维能力。

CF559E Gerald and Path

$\color{blue}\texttt{[NORMAL]}$

考虑 $\text{dp}$。把区间按给出的端点排序，设 $\text{dp}_{i, j, 0/1}$ 表示已经考虑到第 $i$ 个区间，目前最右区间为 $j$，$j$ 的方向为向左/向右。

但是发现不好转移，因为可能会出现新的区间填充进之间的空隙导致答案增加。于是不妨直接枚举下一个有效区间 $k$ 在哪里，然后直接忽略 $[i+1,k-1]$ 中的所有区间（因为我们知道如果忽略多了一定不优），所以是没有问题的。同时需要注意，在枚举 $k$ 的时候，$[i+1,k-1]$ 中可能出现区间越过 $k$ 成为最远区间的情况，所以在从小到大枚举 $k$ 的时候还需要顺便维护一下当前 $[i+1,k]$ 中间最远的右端点在哪里，更新 $\text{dp}$ 值的时候也要直接更新到这个最远右端点的位置。

复杂度 $\mathcal{O}(n^3)$。

本题状态并不难想。主要在于忽略中间的区间一个操作没有想到。总结一下用忽略部分物品的几个条件：

• 状态中对状态有贡献的位置并不多。
• 考虑的物品包含信息量较大，以至于无法在加入新物品的时候快速求解贡献的 $\Delta$。
• 已知该转移方式可以转移出最优解。
• 少考虑一些可能存在的限制一定不优（这往往体现在贡献为正）。

CF568C New Language

$\color{red}\texttt{[HARD]}$

先建立 $\text{2-SAT}$ 的图，然后考虑如何求解。

字典序小，且不小于给定字符串，那必然要有一个前缀相等，且前缀越长越好。考虑枚举这个前缀的长度，从长到短，然后就可以得到接下来一个字符。

首先判断当前前缀是否合法，然后在接下来一个位置字典序要大于原字符串的字典序。接下来就可以填尽量小的字符了，具体来说，选择两个集合中最小的字符，然后判断是否可选，如果可选则接着考虑下一位。

至于考虑合法，直接从 $\text{2-SAT}$ 的图上的点开始移动，记录 $\text{vis}$ 数组，如果 $x$ 和 $\lnot x$ 都走到了则不合法，否则可以合法。

时间复杂度 $\mathcal{O}(nm)$。

本题给出了 $\text{2-SAT}$ 更为广泛的运用——$\text{2-SAT}$ 在一定条件下是可以构造最优方案的（尽管复杂度可能不算十分优秀），也就是遇到 $\text{2-SAT}$ 不一定要缩点，因为建立的图实际上已经给出了很强的限制，在上面直接跑可以判断局部是否合法，从而更为灵活地根据局部的情况来判断解的可行性，从而求解最优解。

CF568E Longest Increasing Subsequence

$\color{blue}\texttt{[NORMAL]}$

为啥这题想不到啊......

考虑求最长上升子序列的过程：记录长度为 $i$ 的上升子序列中，结尾数字最小为多少，然后二分处理。考虑同样使用这个方式。

首先发现在上升子序列中不存在重复元素，所以很多地方是不需要再次讨论重复元素情况的，这很好。因此按上面的方式维护，遇到一个空，就暴力枚举这里放 $m$ 个元素中的哪一个，然后暴力更新数组。但是这里不能二分，不然带个 $\log$，改成双指针即可。

这样就得到了最大答案，再考虑构造方案。

记录所有非空位置的最大长度，挂在长度的 $\text{vector}$ 上。然后从最长的结尾开始往前推。若存在一个合法的前驱，就直接跳过去，否则合法位置必然是上一个空，跳到那里之后贪心地选最大的合法数字即可。

复杂度 $\mathcal{O}((n+m)k)$。

CF571D Campus

$\color{blue}\texttt{[NORMAL]}$

考虑离线。

发现前两种操作实际上就是建立了树的结构，然后把 $\text{dfn}$ 搞出来，剩下的操作在树上就是一个子树修改。

时间复杂度 $\mathcal{O}((n+q)\log n)$。

CF575A Fibonotci

$\color{green}\texttt{[EASY]}$

$\text{sbt}$。

直接用循环节维护矩阵快速幂，碰到不一样的就暴力改即可。区间矩阵乘积可以直接倍增一下。感觉这题难度全部都在代码上 但是由于代码鸽了所以这题口胡变成了普及题