随便写一些算法

EDU124

C. Fault-tolerant Network
题目大意
一间教室里有两排电脑，每排有 $n$ 台，每台电脑有自己的一个等级。
第一排的电脑等级依次为 $a_1, a_2, \cdots, a_n$ ，第二排的电脑等级依次为 $b_1,b_2, \cdots, b_n$

起初，对于每一排电脑，所有相邻的电脑之间有网线连接。因此两排电脑是相互独立的两套计算机网络。
你的任务是把两排电脑连接到同一个计算机网络中，你可以在两排电脑之间连接一或多对计算机。
将第一排的第 $i$ 台电脑和第二排的第 $j$ 台电脑相连需要花费 $|a_i - b_j|$ 的代价

你可以把一台电脑与另一排的多台电脑相连，但是你联通的网络需要满足最基本的容错性：
不管哪台电脑坏掉，这个网络的剩余部分都不会断开（即其他计算机仍可以两两互通）。

你需要最小化代价。

思路分析
画一下图，可以发现 $\{a_1, a_n\}$ 一定要有到 $b$ 的链接，同时 $\{b_1, b_n\}$ 也要有到 $a$ 的链接
可以用反证法证明
不妨设 $a_i$ 坏掉了，如果 $a_n$ 没有到 $b$ 的链接的话，那么 $(a_{i+1}, \cdots, a_n)$ 这些电脑是链接不到 $b$ 的
$b$ 也同理

所以就依次考虑 $(a_1, a_n)$ ， $(b_1, b_n)$ ，对于 $(a_1, a_n)$ ，枚举 $b$ 中哪个点距离它最近
$(b_1, b_n)$ 同理，这样就保证了 $a_1, a_n, b_1, b_n$ 四条线都被连上了，一定是一组合法的解

值得注意的是， $(a_1, b_1), (a_n, b_n), (a_1, b_n), (a_n, b_1)$ 彼此相连的情况
并不需要 $4$ 条线

下面来讨论一下

$(a_n, b_n)$ 连，此时若 $b_i$ 坏了，对于 $b_{i-1}$ 要想连到 $b_{i+1}$ ，需要
$b_{i-1} \to \textcolor{red}{b_1 \to a_{j} } \to a_{n} \to b_{n} \to b_{i+1}$ ，此时对于 $b_1$ 找到最小的 $a_j$ 即可
同理， $a_i$ 坏了， $a_{i-1}$ 要通过 $a_1$ 才能连通到 $b$ ，此时需要找到最小的 $\textcolor{red}{(a_1 \to b_j)}$
$(a_1, b_1)$ 连，同理，连最小的 $\textcolor{red}{a_n \to b_j}$ ， $\textcolor{red}{b_n \to a_j}$
$(a_1, b_n)$ 连，连最小的 $\textcolor{red}{a_n \to b_j}$ ，和 $\textcolor{red}{b_1 \to a_j}$
$(a_n, b_1)$ 连，连最小的 $\textcolor{red}{a_1 \to b_j}$ ， $\textcolor{red}{b_n \to a_j}$

CF778（div1+div2）

C. Alice and the Cake
题目大意，给你一块蛋糕，切 $n-1$ 次，每一次选 $w\geqslant 2$ 的块，切成两部分

分别是 $\displaystyle \left\lfloor \frac{w}{2} \right\rfloor$ 和 $\displaystyle \left\lceil \frac{w}{2} \right\rceil$ ，这样得到一个序列 $a$
现在给你一个序列 $a$ ，问你这个序列能不能拼接成完整的蛋糕，能输出yes，否则输出no

算法分析

这种问题一般有两种考虑，第一种是由序列倒着来拼，还有一种就是枚举初始蛋糕到底是那一块

先尝试倒着来拼接， $(x_1, x_2)$ 拼接，那么 $x_1 = (w \gg 1), \quad x_2 = ((w-1) \gg 1) + 1$

右移运算还原成 $w$ 比较麻烦，所以考虑其他做法

注意到 $\displaystyle \left\lfloor \frac{w}{2} \right \rfloor + \left \lceil \frac{w}{2} \right \rceil = w$ ，所以切割过程，蛋糕质量不会凭空消失

由此蛋糕的总质量一定是 $S = \sum a_i$

这样就可以考虑对蛋糕进行切割了，贪心地做，因为蛋糕只会越切越小
所以用两个堆维护当前蛋糕的最大块，和当前待匹配的序列的最大值
如果当前蛋糕最大块都小于序列最大值，那么怎么样都不可能匹配上了，直接返回错误
如果最大块和序列最大值相等，记一次匹配，同时弹出最大块和最大值
如果最大块更大，那么把最大块切成两部分，并且弹出原来的最大块
模拟这个过程，如果最后序列都匹配上的话，那么就是合法的

总结
这是一个 $\max1 \geq \max2$ 的问题，这类问题要想到用两个堆去维护

CF747(div2)

C. Make Them Equal

题目大意就是说，给你一个字符 $\text{c}$ ，和一个长度为 $n$ 的串
你必须把串所有数都改成 $\text{c}$ ，问最少操作几次
修改的要求是，每一次你都可以任意选择一个 $1 \leqslant x \leqslant n$ 的数
一次修改，可以把下标不能被 $x$ 整除位置的数都改成 $c$

算法分析
不难发现最多修改 $2$ 次就可以，因为你可以选择 $n$ ，这样把 $[1, n-1]$ 位置都变成 $c$
然后对于 $n$ 这个位置，你选择 $x = n-1$ ，把 $n$ 这个位置也变成 $c$

考虑能不能一次完成，那么首先标记待修改的位置 $vis$
枚举 $x$ ，同时枚举 $x$ 的所有倍数，如果发现一个倍数在 $vis$ 中， $x$ 就不可以选了
否则就可以选出 $x$ ，一次完成

D. The Number of Imposters

题目大意就是说， $n$ 个人，每个人可能是诚实的或者是说谎的
给你 $m$ 个条件， $(i, j, c)$ 表示 $i$ 说 $j$ 是一个 $c$ 类型的人
$c = 1$ 表示 $i$ 这个人诚实， $c = 0$ 表示 $j$ 这个人不诚实
问最多的老实人个数

扩展域并查集

$i$ $i$ 说 $j$ $j$ 是老实人
- $i$ 如果老实， $j$ 也老实
- $i$ 如果不老实， $j$ 也不老实
$i$ $i$ 说 $j$ $j$ 不老实
- $i$ 如果老实， $j$ 不老实
- $i$ 不老实， $j$ 是老实人

这可以用扩展域并查集来求解，并查集初始化成 $[1, 2n]$ ，对于某个人 $i\in [1, n]$ 而言
编号 $i \in [1, n]$ 表示这个人是老实人，编号 $(i+1) \in [n+1, 2n]$ 表示这个人不是老实人

简而言之， $i$ 说 $j$ 老实，那么 $i, j$ 属于一个集合
否则的话， $i$ 和 $j$ 分属两个不同的集合

那么最后一个问题就是如何回答询问
如果一个人 $\text{find}(x) = \text{find}(x+n)$ ，那么矛盾
否则的话 $\sum_x \text{sz}(\text{find}(x))$ 求出老实人集合数，和 $\sum_x \text{sz}(\text{find}(x+n))$ 不老实人集合数

然后考虑这两个集合交换一下，取最大值
因为经过上面的分析，我们发现 $i, j$ 的情况用两个集合就可以概括了
与这两个集合哪个是老实人集合，哪个是不老实人集合无关

所以答案实际上就是
$\displaystyle \max\left(\sum_x \text{sz}(\text{find}(x+n), \sum_x \text{sz}(\text{find}(x) \right)$

AtCoder Beginner Contest 254

Together Square

题目大意，给定 $n$ ，求 $\leqslant n$ 的两个数 $(i, j)$ ，（注： $(1, 4), (4, 1)$ 算 $2$ 次）
问能找到多少对这样的数对，使得 $i \times j$ 是完全平方数

思路分析
对于 $i \times j = x \times x$ ，考虑 $x \in [1, n]$
并且尝试从 $x \times x$ 重构出 $(i, j)$

首先对于每一个 $x \in [1, n]$ ，将其因子分成两部分，分别是
$(p_1p_2\cdots p_k) \times A^2$ ，其中 $A^2$ 表示最大的平方因子
$(p_1p_2\cdots p_k)$ 表示不是完全平方的因子

容易发现，从 $x \times x$ 构造 $i \times j$
$(p_1p_2\cdots p_k)$ 这部分是确定的， $i, j$ 都必须包含这部分因子

所以每一个 $x$ 的方案可以和 $v = p_1p_2\cdots p_k$ 方案一一对应
那么我们只需要处理出，对于 $x$ 而言对应的 $v$
并且记一下 $v$ 能够配上多少给平方因子 $c(v)$
当然不配任何平方因子， $(i, j) = (v, v)$ 也是一种方案
但这里用了一个技巧，将 $1$ 也看作是一个平方因子，统计到 $c(v)$ 中

所以答案就是 $\displaystyle \sum_{v} c(v) \cdot c(v)$

注意，因为我们是从小到大枚举的，所以对于每一个非平方因子 $v$
我们依次检查了 $(v\times 1), (v \times 2^2), (v\times 3^2), (v\times 2^23^2)\cdots$
不会漏解

Atcoder Beginner Contest 250

E - Prefix Equality

题目大意，给定 $A[1\cdots n], B[1\cdots n]$ 两个数组，然后有 $Q$ 个询问
每次询问给你两个数 $x, y$ ，问 $A[1\cdots x], B[1\cdots y]$ 这两个前缀集合中
去重后是否相等

哈希方法
这里用一种哈希的方法来判断，前缀哈希的做法如下

预先遍历数组 $A$ ，对于每个元素 $a_i$ ，将 $a_i$ 映射成一个随机数，如果映射过了就跳过
具体来说用一个 $\text{map}$ 记录一下 $\text{mp}(a[i]) = \text{rand}()$

然后用一个 $\text{set}$ 存放 $a_i$ ，同时计算哈希

unsigned long long ha[n+1];

for i = 1 to n:
  ha[i] = ha[i-1];

  如果 a[i] 不在前缀集合中：
    ha[i] += mp[a[i]];
    将 a[i] 插入集合

计算哈希的关键在于，每一次只在 $x$ 第一次放入集合的时候计算哈希

Codeforces Round #787 (Div. 3)

E. Replace With the Previous, Minimize

题目大意，给你一个字符串，你可以操作 $m$ 次
每一次操作都可以选择一个字母 $c$ 变成 $c-1$ ，注意此时字符串中所有的 $c$ 字母都会变成 $c-1$
你要使得操作完之后字典序最小

思路分析
贪心地看，从前往后，把每一个字符都尽量改成 $a$
模拟这个过程，比如 $f \to a$ ，那么一次操作所有的 $f \to e$
接下来所有的 $e \to d$ ，以此类推

可以考虑用并查集维护，每一次操作的过程
相当于 $(S_i)$ 所在的集合和 $(S_{i} - 1)$ 所在集合合并

具体到代码实现上，并查集维护集合最小值 $\text{minv}$
比如找到 $x$ 所在集合的最小值，在并查集中，只需要找到 $x$ 所在集合的根
即 $r = \text{findpa}(x)$ ， $\text{minv}[r]$ 给出的就是 $x$ 所在集合的最小值

算法实现如下

从前往后扫描每一个字符 $s_i$ ，修改前它所在集合的根是 $r1 = \text{find}(s_i)$
当前 $s_i$ 所在集合的最小值 $v_i = \text{minv}[r1]$ ，令 $s_i = v_i$
只要发现 $m > 0$ 并且 $s_i > a$ ，那么就尝试减小 $s_i$
减小后的集合的根应该是 $r2 = \text{find}(s_i - 1)$ ，合并两个集合，即 $\text{join}(r1, r2)$
一次修改操作完成后，重新确定新集合的根 $r = \text{find}(a[i])$
更新 $a[i]$ 为新集合的最小值，即 $a[i] = \text{minv}[r]$