第20届宁波大学程序设计竞赛-题解

难度预测：

easy:BDH

middle:EFGK

middle-hard:A

hard:CIJ

Problem A. 0-1翻转

知识点：贪心

对于每次操作，可以发现奇数位的 $0$ 和 $1$ 与偶数位的 $0$ 和 $1$ 同时增加或减少，所以奇数位和偶数位 $0$ 和 $1$ 的数量差不变。要想把数全变成 $0$ 的充分必要条件，是奇数位的 $1$ 和偶数位的 $1$ 数量相等。要想把一个奇数位的 $1$ 和一个偶数位的 $1$ 全变成 $0$ ，需要进行操作的最少次数为这两个 $1$ 之间的距离。

所以，我们只需要最小化奇数位和偶数位 $1$ 之间的距离，考虑贪心，将奇数位和偶数位 $1$ 的位置分别按从小到大排序，然后从小到大枚举 $1$ 之间的距离，统计贡献求和，可以保证操作次数最少。我们可以在 $O (n)$ 的时间复杂度下，求出结果。

Problem B. 类银河恶魔城

知识点：贪心，排序

对于每款游戏而言，剩下的一项艺术性指标如果是 $100$ 分，并且其他游戏都是 $0$ 分，这样自己的排名能够更靠前。所以只要比较每款游戏已经确定的分数与排名第 $K$ 的游戏的分数差，能否用艺术性指标的 $100$ 分追回即可，实现该操作只需要对总分进行排序。因为数据范围很小，可以直接冒泡排序或者选择排序，时间复杂度为 $O (n^{2})$ 或 $O (n l o g n)$ 。

Problem C. 平泽唯删圆

知识点：计算几何，最大生成树，拓扑排序

首先，注意到 $n$ 的范围只有 $500$ ，考虑预处理出每两个圆重叠部分的面积，两圆相交面积直接调用板子即可。将每个圆的圆心看作点，两个圆重叠部分的面积看作边权，通过边连接这两点，于是该题可转化为图论问题，不难发现该图是 $n$ 阶完全图。

然后，每次操作相当于选一个点和连向该点最大边权的边，要想使分数最大化，选出的点和边一定是构成该图的最大生成树。又因为任意两个圆重叠部分面积均不同，所以最大生成树一定唯一。

最后，考虑如何安排删圆的顺序，删圆相当于删点，每次删的点的度数一定为 $1$ (最后一个点除外)。不难想到拓扑排序，但是要求字典序最小，可以考虑使用优先队列维护进行 $b f s$ ，时间复杂度 $O (n l o g n)$ 。因为 $n$ 的范围只有 $500$ ，所以也可以直接 $O (n^{2})$ 暴力贪心，我们每次从小到大找到第一个能删的点删除，同时将与该点相连的点的度数减 $1$ ，这样得到的删点顺序的字典序一定最小。

总的时间复杂度 $O (n^{2} l o g n)$ 。

Problem D. 翔子小姐学均值不等式(easy version)

知识点：枚举

注意到 $x, y$ 的数据范围很小，可以考虑暴力枚举 $(a, b)$ 的值（注意枚举的范围），时间复杂度 $O (n^{2})$ 。

Problem E. 翔子小姐学均值不等式(hard version)

知识点：二分

因为 $x, y$ 的数据范围很大，直接枚举显然超时，考虑二分优化。由题意可知，不等式中间部分 $\frac{2}{\frac{1}{a}+\frac{1}{b}}\leq \sqrt[]{ab}\leq \frac{a+b}{2}\leq \sqrt[]{\frac{a^2+b^2}{2}}$ 恒成立，所以我们只需要满足 $x \leq \frac{2}{\frac{1}{a}+\frac{1}{b}}$ 和 $\sqrt[]{\frac{a^2+b^2}{2}} \leq y$ 两边即可，式子进一步化简可得 $(a+b)x \leq 2ab$ 和 $a^2+b^2 \leq 2y^2$ ，由于两者都具有单调性，所以我们可以先枚举 $a$ 的值，再对 $b$ 的值进行二分查找，分别统计两个不等式 $(a, b)$ 的数量，取两者的交集即可，时间复杂度 $O (n l o g n)$ 。

Problem F. 回文串

知识点：最短路，dp

普通魔法可以看作是一条从 $a_{i}$ 连向 $b_{i}$ 的有向边，边权为 $c_{i}$ 。超级魔法可以看作是所有字母两两之间连了一条边权为 $w$ 的无向边。现在要把字符串 $s$ 变为回文串，就是要把 $s_{i}$ 和 $s_{n-i+1}$ 都变成同一种字母。

设 $f [a] [b]$ 表示把字母 $a$ 变成字母 $b$ 需要消耗的最小法力。可以用 Floyd 求出所有的 $f [i] [j]$ 。

而把 $a, b$ 都变成同一种字母既可以是都变成 $a$ ，也可以是变成 $b$ ，还可以是都变成另一种字母 $c$ 。因此需要考虑 $g [a] [b]$ 表示把字母 $a$ 和字母 $b$ 都变成同一种字母需要消耗的最小法力，这也可以用类似 Floyd 的方法求出。

Problem G. 雫露露的背包

知识点：深度优先搜索（DFS）

考虑深度优先搜索（DFS）算法，我们可以将所有取法的情况全部算一遍，如果某个取法能够恰好装满背包，则答案加1。因为 $a_{i}$ 的总乘积不超过 $1 0^{6}$ ，所以枚举所有取法的情况不会超时。

Problem H. 樱花庄的樱花树

知识点：树，数学

不难得出，节点 $x$ 的三个子节点分别是 $3 x - 1, 3 x, 3 x + 1$ ；节点 $x$ 的父节点是 $\lfloor \frac{x+1}{3} \rfloor$ (向下取整)。为了求出两点的最近公共祖先，可以每次找节点编号比较大的那个点，让它向上跳。显然在树上，这两个点最后一定会相遇，相遇的位置就是我们想要求的 $L C A$ 。因为完全三叉树的树高为 $O (l o g n)$ ，所以单次查询时间复杂度为 $O (l o g n)$ 。

Problem I. 库洛牌小喵钓鱼

知识点：概率 $d p$ ，前缀和优化

设 $d p_{i}$ 表示剩余 $i$ 张花色牌时 $T o m o y o$ 获胜的概率。洗牌后， $d p_{i}$ 可以转移到 $dp_i,dp_{i-1},dp_{i-2},...,dp_0$ 。于是我们可以得出，当 $i \ge 2$ 时的状态转移方程：

\begin{aligned} dp_i=\frac{2}{(i+1)(i+2)}\sum_{j=0}^{i}(i+1-j)dp_j \end{aligned}

注意到其中 $\sum_{j=0}^{i}(i+1-j)dp_j$ 的部分可以用前缀和表示，于是我们可以先根据 $d p_{0} = 1$ 和 $d p_{1} = 0$ ，在 $O (n l o g n)$ 时间复杂度下进行预处理，递推得到所有 $d p$ 的值，然后 $O (1)$ 处理每组数据，总的时间复杂度为 $O (n l o g n)$ 。

Problem J. 双端队列

知识点：树状数组

如果直接使用双端队列虽然可以很快完成操作1、2、4，但是执行删除操作很慢，因此考虑使用树形结构来维护。

可以用权值树状数组维护第 $i$ 个位置上是否有数。

对于操作1、2，维护左右端点 $l, r$ ，表示当前已使用的树状数组下标范围为 $[l, r]$ ，初始状态 $l = q, r = q + 1$ ，执行操作1或2就把树状数组 $l$ 或 $r$ 位置上的值修改为1;同时对每个数都记录 $p o s$ ，用于保存这个数每一次插入到树状数组的位置。

对于操作3，取出 $x$ 最后一次插入的位置 $l a s$ ，直接对树状数组的 $l a s$ 位置进行修改，这样每次删除只影响1个位置，其他数字的位置仍然不变。

对于操作4，因为使用的是权值树状数组，要想找到第 $x$ 个有数的位置，就是要在树状数组上找到前缀和等于 $x$ 的第一个位置，因此一种可行的方法是二分位置 $p$ ，每次对树状数组求 $s u m (p)$ ，这样一次操作的复杂度为 $O (l o g n)$ ，本题时限较宽松，只要常数不是太大都是可以通过的。

此外，还可以使用树状数组树上倍增求第 $k$ 小值的方法以 $O (l o g n)$ 的复杂度完成一次查询。

Problem K. 多拉博弈

知识点：博弈论

题意可以化简为有数量分别为 $x_{1} - x_{0}$ 和 $y_{1} - y_{0}$ 的两堆石子，每次操作相当于从其中一堆石子中取 $1$ 至 $3$ 颗石子，取走任意一堆的最后一颗石子的人输掉游戏。

假设两堆石子的数量分别为 $a, b$ 。易知，当 $(a, b)$ 为 $(1, 1)$ 时，先手必输，所以 $(1, 1)$ 为必败状态。又因为当先手从任意一堆中取 $k$ 颗石子，后手可以从另一堆中也取 $k$ 颗石子，所以 $(n, n)$ 也为必败状态。

又因为每次操作取 $1, 2, 3$ 颗，所以无论先手取多少颗，后手总能保证共同从一堆石子中取走 $4$ 颗，于是 $(n, n + 4), (n, n + 8) . . . . . .$ 也属于必败状态，同理，一般化后得到 $(n + 4 k_{1}, n + 4 k_{2})$ 也属于必败状态，而其他状态则属于必胜状态。

所以如果两堆石子的数量差为 $4$ 的倍数，即 $|a-b| \ mod \ 4 = 0$ ，则先手必败，否则，先手必胜。

题解 | #0-1翻转#