题解 02

拿到了这周末 ICPC 2020 南京的名额。今天看新生赛打完，榜前几名都很强。就写点题解早点休息。

POJ 2236 Wireless Network

一群通过无线信号交流的电脑，位置固定，序号为 $1$ 到 $n$，交流半径为 $d$，允许中介。两种操作：

1. $O\,p$， 将 $p$ 号电脑置为可通信状态
2. $S\,p\,q$，检查 $p$ 和 $q$ 两台电脑能否通信

对于每个 S 操作，输出 “SUCCESS” 当可通信，“FAIL”当不可通信。

$1\leq n \leq 1001, 0\leq d\leq 10000$
操作不超过 $300000$ 次

并查集裸题。开一张表记录修好的点。每读入一个维修操作，遍历所有修好的点，把处于半径内的点都加入同一组；每读入一个查询操作，就查两个点是否在同一组。

CF 1457 C Bouncing Ball

一共 $n$ 个坑，编号从 $1$ 开始。一些坑已经被填上了，一些没有。扔过一个小球，第一次落地在第 $p$ 个坑的位置，随后每次落地，都在前一个位置之后的第 $k$ 个位置，如第二次落地在 $p + k$。
有两种操作：

1. 填上当前序列的任一个空坑，代价为 $x$
2. 永远移除当前坑序列的第一个坑，并将球的落点向后推一个位置，代价为 $y$

给定初始的坑序列被填上的情况，和 $p, k$，求最小的代价使球能跳过这个序列而不掉坑里。球至少落地一次。

$1\leq p \leq n \leq 10^5, 1\leq k\leq n, 1\leq x, y\leq 10^4$

两种想法。一种偏模拟，一种偏思维。

首先可以考虑枚举最后一次落点的位置，显然是只会在最后 $k$ 个位置；再枚举这是第几次的落点，即枚举删了多长的前缀能让球最后落在这里。在所有枚举的答案中取最小值。复杂度，一个 for 套一个跳着变的 while，大概是 $O(n)$。

另一种解法在我复述的题面里暗示了：删去第一个坑等价于第一次的落点向后推一个位置。首先我们可以利用动态规划求出这样一个数列 $dp[i]: 第一个落点在 i 时，跳过整个序列需要填的坑数$，从前向后或者从后往前 d 都可以，复杂度是 $O(n)$。然后枚举第一次的落点，所有结果中取最小。可以在 $O(n)$ 时间完成。

CF 1295 B Infinite Prefixes

给定一个长度为 $n$ 的 01 串 $s$，可以构造一个 01 串 $t$ 由 $s$ 重复无穷多次，即 $t = sss\dots$
设一个 01 串的平衡度为 0 的个数减去 1 的个数。给定 $x$，求 $t$ 中平衡度等于 $x$ 的前缀的个数。输出 $-1$ 当个数无穷多时。

$1\leq n\leq 10^5, -10^9\leq x\leq 10^9$

先算一下 $s$ 前缀的平衡度数列，往后接几个 $s$ 模拟一下可以发现，用整个 $s$ 的平衡度作为“初始量”去过一遍字符串，平衡度数列就是结果平衡度的“变化量” $delta[i]$，比如单个 $s$ 的平衡度是 $b$，两个 $s$ 的就是 $2b$，三个就是 $3b$。现在 $t$ 前缀的平衡度如何变化已经可以映射到一个 $s$ 的长度里去算了：前缀中完整的 $s$ 个数乘初始量，再加上剩下不完整的 $s$ 所对应的那个位置的“变化量”。

接下来就是看无限重复的过程中会出现几个平衡度为 $x$ 的前缀了。首先考虑无数个的情况，这只会在 delta[n - 1] == 0（循环一个周期后平衡度总是 $0$） 且 delta[] 中有值与 $x$ 相等的时候出现。此外，delta[n - 1] == 0 且 delta[] 中没有值与 $x$ 相等时，不会出现符合题设的前缀。

当 delta[n - 1] != 0 时，就可以用之前提到的算法去找符合条件的位置了，扫一遍 $s$ 即可。

CF 1453 C Triangles

一个 $n$ 行 $n$ 列的方阵，元素都是一位十进制正整数，单元格边长为 $1$。对于任何一个 $0$ ~ $9$ 中的数字 $d$，求符合如下条件的三角形的面积：

1. 三个顶点都在单元格中心
2. 顶点所在的单元格，元素为 $d$
3. 至少一条边与方阵的边平行。长度为 $0$ 的边与方阵两边都平行
4. 面积尽可能大，但可以为 $0$

对于每个 $d$，在确定这样的三角形之前，可以将方阵中任何一个位置的元素临时看作 $d$。
给定方阵，按 $d$ 从 $0$ 到 $1$ 的顺序输出面积的两倍值。

$1\leq n\leq 2000$

大模拟。

巨大无比，目前敲过最大的。当场没过，回去之后发现是几个变量写错了。

一个思路是维护好每行和每列中相隔最远的 $d$ 的位置，然后枚举那个平行边（底边）所在的行或列。如果这一行/列有至少两个 $d$，就取最大的高；只有一个 $d$，就在这一行/列取最长的底，再找到尽量大的高。这样属于枚举了所有可能的最大三角形。所有结果中取最大。

Tutorial 的思路是：对于每个 $d$，可以只考虑它作为平行边端点的情况，再将它所在行/列的最远点取成 $d$，最后只要找这条底边最远的 $d$ 作为高即可。不需要考虑枚举到的 $d$ 作为高顶点的情况，因为高顶点只能是最边上的 $d$；也不需要考虑取到的 $d$ 作为高顶点的情况，因为任意取，可以在面积不变的情况下把它移动到底边上。

CF 1453 D Checkpoints

编号从 $1$ 到 $n$ 的关卡，玩家从第一关开始向后连续通关。每一关至多有一个复活点，第一关一定有一个复活点。当玩家到达一个关卡时，该关的复活点立即被激活。
当玩家通过一个关卡时，可以到达整数连续的下一关；未通过该关时，会返回最近的被激活复活点所在的关卡（重新开始该关当未能通过一个有复活点的关卡时）。
对每个关卡，假设玩家通过和不通过的概率都是 $\frac{1}{2}$。给定玩家全部通关时总通过关卡数的期望 $k$，求一个符合条件的复活点分布。关卡总数至多为 $2000$。

$1\leq n\leq 2000, 1\leq k\leq 10^{18}$

可以看出经过一个复活点之后，前面的期望就完全独立了，可以加起来。那么只考虑一个有复活点的关卡后面跟着若干空关卡的情况，即可构造出答案。

对于只有一关的游戏，可以算出通关期望是 $2$：设期望是 $x$，有一半的概率一次通关，另一半概率是在期望上多试一次，列出方程 $x = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot (x + 1)$。对于“10”这样的分布，$x = \frac{1}{2} \cdot \frac{1}{2} \cdot 2 + \frac{1}{2} (x + 1) +\frac{1}{2} \cdot \frac{1}{2} (x + 2)$，第一项是确定的无死亡通关，第二项是第一关没过，第三项是第二关没过，解得 $x = 6$。可以猜出方程，也可以随机模拟一遍再猜。复活点后面跟着 $n$ 个空关卡的通关期望方程是

$$\begin{array}{c} x = \frac{n + 1}{2^{n + 1}} + \sum_{i = 1}^{n + 1}\frac{i}{2^i} + \sum_{i = 1}^{n + 1}\frac{x}{2^i}\\[2ex] x = \frac{n + 1}{2^{n + 1}} + \sum_{i = 1}^{n + 1}\frac{2^i - 1}{2^{n + 1}} + x \cdot \frac{2^{n + 1} - 1}{2^{n + 1}}\\[2ex] x = 2^{n + 2} - 2 \end{array}$$

换成数组上的表达，一个 a[] = 1000... 的数组，走通第 $i$ 个位置的期望是 $p_i = 2^{i + 2} - 2$。

再跟一下这个数列，发现它在 60 多项就会超过 long long 的范围，看一下 $k$ 的范围只要维护大概这么长就行了，加起来不会超过 $2000$ 关的。

最后，根据维护好的数组，从 $k$ 里减去对应的值，构造答案即可。