随便写一些算法（二）

AtCoder Beginner Contest 254

题目大意，给定两个集合 $A$ 和 $B$ ，每一次你可以把 $A$ 中的数 $x$ 替换成 $2x$
或者把 $x$ 用 $\displaystyle \left\lfloor \frac{x}{2} \right\rfloor$ 替换
问最少几次可以让 $A, B$ 两个集合相同（计算重复元素）

方法一，维护堆
对于 $A$ 中的元素 $x$ 与 $B$ 中的元素 $y$ ，以上操作影响的是最后一位

首先考虑到如果 $y$ 最后一位是 $1$ ，但 $x$ 最后一位是 $0$ ，那么无解
因为两种操作都不能够在某一位上引入一个 $1$
考虑 $y$ 的最后一位是 $0$ ，那么如果 $x > y$ ，那么只要令 $x \gg 1$
然后比较 $x$ 更高的位，而如果 $x < y$ 呢？
考虑 $x < y$ ，假设当前处理的是 $x$ 的 $i$ 位与 $y$ 的 $j$ 位
此时令 $x \ll 1$ ，这样 $x[i+1]$ 和 $y[j]$ 都是 $0$
然后接着比较 $x[i]$ 与 $y[j-1]$ ，所以这一步的操作，等价于 $y \gg 1$
上述是一个 $\max > \max$ 的问题，可以考虑用两个堆维护
如果 $A_{\max} > B_{\max}$ ，尝试令最大值 $x \gg 1$ ，然后继续比较
反之则需要判断 $B$ 最大值 $x$ 的最后一位是不是 $0$
最后只有在堆为空的时候，算法执行成功

方法二，01-Trie
上述过程还有一种模拟方法，就是用 01-trie 来维护

先把所有的数看成 01 串，插入 trie 中，然后 dfs
从叶节点自底向上统计，因为我们需要让 $A$ 中的元素 $\to B$
所以插入 trie 的时候，对于 $A$ 集合元素，当它沿着树边走的时候，让沿途节点权值 $+1$
同理，插入 $B$ 集合，让沿途节点权值 $-1$ ，这样如果 trie 中的节点权值为 $0$
就说明这个位置， $A, B$ 两个集合匹配上了
自底向上修改，如果当前字符表示 $0$ ，那么根据方法一的分析
如果点的权值 $v > 0$ ，说明集合 $A$ 中有一些元素比集合 $B$ 中大
对这些元素每一个都执行 $\gg 1$ ， $ans += v$
同理如果 $v < 0$ ， $ans += |v|$
然后考虑当前字符表示 $1$ ，如果 $v < 0$ ，说明 $B$ 中以 $1$ 结尾的元素个数大于 $A$ 中相应的个数
而这些 $1$ 并不能通过规定的操作删去，所以直接返回错误
否则的话，操作次数为 $ans += v$
然后回溯到根，就做完了

Rectangle GCD
题目大意，给你两个数组 $A[1\cdots n], B[1\cdots n]$ ，构成 $n \times n$ 的矩阵
矩阵中 $(i, j)$ 的值定义为 $A_i + B_j$
有 $Q$ 个询问，每次询问给出 $[h_1, h_2], [w_1, w_2]$ ，问 $[h1, h2] \times [w_1, w_2]$ 区域内
所有数的最大公约数

算法分析
对于 $\text{GCD}$ ，有一个很重要的结论
$\text{gcd}(x_0, x_1, x_2, \cdots, x_n) = \text{gcd}(x_0, x_1-x_0, x_2 -x_1, \cdots, x_i - x_{i-1}, \cdots)$

矩阵的 $\text{gcd}$ 可以写成如下形式，对列作差分

$\begin{pmatrix} A_i+B_j & A_i +B_{j+1} & A_i + B_{j+2} & \cdots & A_i + B_{j'} \\ A_{i+1}-A_i & \cdots & \cdots \\ A_{i+2}-A_{i+1} & \cdots & \cdots \\ \vdots \\ A_{i'} - A_{i'-1} & \cdots & \cdots \end{pmatrix}$

再对行作差分，可以得到

$\begin{pmatrix} A_i+B_j & B_{j+1}-B_j & B_{j+2} - B_{j+1} & \cdots & B_{j'}-B_{j'-1} \\ A_{i+1}-A_i & \cdots & \cdots \\ A_{i+2}-A_{i+1} & \cdots & \cdots \\ \vdots \\ A_{i'} - A_{i'-1} & \cdots & \cdots \end{pmatrix}$

所以所求的 $\text{gcd}$ 等于
$\displaystyle (A_i + B_j)$
$\displaystyle (A_{i+1}-A_i, A_{i+2}-A_{i+1}, \cdots, A_{i'}-A_{i'-1})$
$\displaystyle (B_{j+1}-B_j, B_{j+2}-B_{j+1}, \cdots B_{j'}-B_{j'-1})$

后面两部分，可以用线段树维护 $A, B$ 的差分数组，开两个线段树
然后用线段树的 $[i, i'-1], [j, j'-1]$ 区间来求解
其中差分数组 $A'[i] = A[i+1]-A[i]$

Codeforces Round 778

D. Potion Brewing Class
题目大意，给定一个正整数序列 $A_n$ ，并且给定 $n-1$ 条关系
每一条关系用 $\displaystyle \frac{a_{i}}{a_j} = \frac{x}{y}$ 来描述，保证已知 $a$ 中任意一个元素
可以推出其他元素

对于所有可能的序列 $A$ ，求出最小的 $\sum a_i$ 并对 $998244353$ 取模

算法分析

如果已知 $a_1$ 要推出 $a_k$ 怎么办，可以根据如下关系

$\displaystyle a_k = a_1 \cdot \frac{a_2}{a_1} \cdot \frac{a_3}{a_2} \cdots \frac{a_k}{a_{k-1}}$

对上述式子加以分析，不难发现，对于一对关系 $(a_1, a_2)$ ，给边赋上权值 $\displaystyle \frac{a_2}{a_1}$

那么从 $a_1$ 转移到 $a_2$ 就可以通过 $\displaystyle a_1 \cdot \frac{a_2}{a_1}$ 来完成

对于每一条关系，可以考虑建图，用 dfs 来求解

具体来说， $\displaystyle \frac{a_i}{a_j} = \frac{x}{y}$ ，先换成 $\displaystyle \frac{a_j}{a_i} = \frac{y}{x}$

然后再 $(i, j)$ 之间连一条边，边带上权值（用分数结构体表示） $\displaystyle \frac{y}{x}$

图建好了，那考虑怎么求解？

从 $1$ 节点出发 $\text{dfs}$ ， $1$ 节点的权值赋为 $1$ ，对于 $(u, v, e)$ ，计算出 $v = u \cdot \displaystyle e\left\{\frac{y}{x} \right\}$
然后将节点的权值化为最简分数， $\displaystyle \frac{1}{p_v}$
然后统计 $\sum{u}$ ，即每个节点的权值，此时直接用模 $P$ 意义下的乘法逆元相加即可
最后答案再乘上 $\text{lcm}(p_v)$ ，保证每个节点的权值是整数

算法实现上的细节
为了让写起来更简单一些，可以预处理打表 $x$ 所有的因子 $\text{fac}(x)$ ，在遍历的时候，从 $u \to v$
统计因子在分母中出现的最大次数，从而统计 $\text{lcm}$

不妨设 $v \leftarrow u \cdot \displaystyle\frac{y}{x}$

先遍历所有 $y$ 的因子 $f \in \text{fac}(y)$ ，令 $\text{cnt}[f] -= 1$

模拟约简的过程 $\displaystyle \frac{y}{x} \to \frac{1}{x/y}$ ，对于 $x$ 中所有的因子
$f \in \text{fac}(x), \quad \text{cnt}(f) += 1$

这样就统计出了 $\displaystyle \frac{1}{x/y}$ 的因子个数

另外我们要统计因子出现的最大个数，所以更新 $\text{cnt}(f) += 1$ 的时候
同时更新 $\text{mx}(f) = \max (\text{cnt}(f))$

最终计算 $\text{lcm}$ 的时候依次遍历每一个因子， $\text{mx}(x)$ 最多出现多少
就乘上几个 $x$

E. Arithmetic Operations

题目大意，给你一个长度为 $n$ 的序列 $A$ ，问最少修改几个数，使得 $A$ 变成等差数列

Codeforces Round #797 (Div. 3)

F. Shifting String

题目大意，给你一个置换，和一个字符串，问这个初始字符串经过几次置换，能够再变换成原来的串？

首先来看置换的一些性质
性质一
性质一，称为奇偶性，记一个置换序列，比如 $(5, 2, 3, 1, 4)$ 逆序对数目为 $\sigma(n)$
置换的符号为 $\displaystyle (-1)^{\sigma(n)}$

性质二，置换的环分解

如果置换 $T$ 是一个大小为 $n$ 的环，那么 $T^k$ 分解后是大小为 $\displaystyle \frac{n}{\text{gcd}(n, k)}$ 的环
并且这样的环有 $\text{gcd}(k, n)$ 个

证明如下，对于环 $T$ ，步长为 $k$ ，可以沿着 $T$ 的轨道走
原来需要 $n$ 次走完，现在只需要 $\displaystyle \frac{n}{\text{gcd}(k, n)}$ 次

所以分解出来的新的环长度为 $\displaystyle \frac{n}{\text{gcd}(n, k)}$ ，并且这样的环有 $\text{gcd}(n, k)$ 个

这样不断地轮换下去，每一个环对应原来序列 $T$ 中的下标
$\displaystyle i \bmod \text{gcd}(n, k) = 0, 1, 2, \cdots$ 的元素组成

$T = (1, 3, 5, 2, 4, 6)$
$T^2 = (1, 5, 4)(2, 6, 3)$ ，其中 $\text{gcd} = 2$ ，所以每个循环下标是
按照 $\bmod 2$ 的余数，对下标进行分类
$[0]: \{0, 2, 4\}, \quad [1]: \{1, 3, 5\}$
所以分解成 $T^2 = (1, 5, 4)(3, 2, 6)$

继续轮换下去，还可以发现 $T^7 = T$
所以一定有 $\displaystyle T^k = T^{(k-1) \bmod n + 1}$

性质三
$\text{gcd}(n, k) = 1$ 时的情形
同样令 $a = T, a' = T^k$ ，初始时，有 $a[0] = a'[0]$
然后开始考虑沿着轨道走，步长为 $k$ ，这样就有 $a'[i] = a[ik \bmod n]$
注意下标从 $0$ 开始

有了这些置换的性质之后，这个问题就简单了

首先对该置换进行环分解， $\text{cycle}[i]$ 这个 $\text{vector}$ 表示第 $i$ 个环是哪些数的下标
然后我们考虑第 $i$ 个环，假设第 $i$ 个环中有 $(1, 3, 5)$ 这个元素，我们就把 $s_1, s_3, s_5$ 单独拿出来
令 $t = s_1s_3s_5$ ，看看走多少步之后，（假设是 $k$ 步），使得 $t \to t$

具体到算法实现上，可以先对置换 $T$ 生成的所有串打表
$T^0 = s$ ，然后依次打表 $\{T^1，T^2, \cdots, T^k\}$
可以写一个 $\text{gen}$ 函数来实现：根据置换生成串

对于每一个循环 $i$ ，从 $j \in [1\to k]$ 检查，将 $T^k$ 中和 $\text{cycle}(i)$ 相关的下标取出来，记为 $t_k$
同时把 $T^0$ 相关下标取出来，记为 $t_0$ ，如果 $t_0 = t_k$
那么很显然循环 $i$ 的幂指就是 $mi(i) = j$

最后求 $\text{lcm}(mi(i))$ 就是答案

G. Count the Trains
题目大意，铁轨上有 $n$ 节车厢，每节车厢可以达到一个最高速度，记录在一个序列 $\{a_i\}$ 中
车厢从左到右编号是 $1 \to n$

现在让车厢向左，并且尽可能快地开动，要求靠右的车厢实际速度不能超过靠左的车厢
这样形成了若干段速度一致的数节车厢，称为一节火车，比如序列 $a[10, 13, 5, 2, 6]$ 对应车厢运行速度为
$[10, 10, 5, 2, 2]$ 形成了 $3$ 节火车

车厢行驶时，给你 $m$ 条形如 $(k, d)$ 信息，表示第 $k$ 节车厢最高速度下降了 $d$
需要维护这个过程中火车的总节数

算法分析
可以利用线段树，考虑维护区间内有多少节车厢 $cnt$
对于区间合并，用 $suf$ 表示区间后缀中的最后一个数是多少， $pre$ 表示前缀的第一个数，那么

$l.suf > r.pre$ 左右两区间不能合并，此时 $cnt = l.cnt + r.cnt$
$l.suf \leqslant r.pre$ 左右两区间可以合并， $cnt = l.cnt + r.cnt - 1$
然后维护 $pre, suf$ ，只需要 $pre = l.pre, \ suf = r.suf$

接下来是修改操作，注意本题给出的车厢速度和实际速度并不相同，实际速度是单调递减的
线段树应该维护的是车厢的实际速度，对于修改操作， $a[x] \leftarrow a[x] - d$
可以在线段树上找出 $x$ 这个叶节点的实际速度 $v$ ，修改后 $v = \min(v, a[x]-d)$

那么对于实际速度序列来说，我们需要在线段树上找到第一个 $< v$ 的数的位置 $r$
区间 $[x, r)$ 的速度都应该执行线段树区间修改，改成 $v$

线段树上找到第一个 $< v$ 的数，二分逻辑
需要维护区间的最小值 $minv$ ，如果 $l.minv < v$ ，那么去左子树中找，否则去右子树

方法二，珂朵莉树
注意到列车的实际速度是非严格单调下降的，我们仿照珂朵莉树
用一个二元组 $\left<id, v \right>$ 来表示列车实际运行速度

第一次插入 $x$ 的时候，如果 $\text{prev}(it).v \leqslant x$ ，那么 $x$ 是没有用的
就把 $x$ 删掉，这样就保证了初始序列是严格单调减的
然后考虑将 $a[i] -= d$ ，实际上可以暴力地来做
就是先令 $a[i] -= d$ ，然后插入二元组 $\left<i, a[i] \right>$
这里需要维护好单调性，就是插入结束后，从刚插入的位置 $it$ 开始，到 $\text{set}$ 的结束
所有的值都必须 $< x$ ，凡是 $\geqslant x$ ，我们就把这个元素删掉
这样做的复杂度是 $O((n+m) \log n)$ 的，因为任何一个元素只会被删除 $n+m$ 次

AtCoder Beginner Contest 255

D - ±1 Operation 2
题目大意，给你一个序列 $A= \left<a_1, a_2, \cdots, a_n \right>$ ，一次操作中，你可以对任意一个数 $+1, -1$
有 $Q$ 个询问，一次给你一个数 $x$ ，问将 $A$ 中所有数都变成 $x$ ，所需要花费的最小代价

算法分析
这个问题实际上就是问 $\displaystyle S = \sum_{i = 1}^{n} |a_i - x|$ 的最小值
可以先对 $a_i$ 排个序，这样就存在 $a_1 \leqslant a_2 \cdots \leqslant a_n$

这样的话， $S$ 就可以分段表示，只需要知道第一个满足 $a_j > x$ 的位置 $j$ ，那么 $S$ 就可以表示成

$\displaystyle \sum_{i = 1}^{j-1} (x-a_i) + \sum_{i = j}^{n} (a_i - x)$

leetcode 杂题

1723. 完成所有工作的最短时间
根据数据范围 $1 \leqslant k \leqslant 12$ ，不难想到可以用状态压缩来做
具体来说，就是枚举子集

第 $i$ 个工人的任务分配状态，可以从第 $i-1$ 个工人转移过来
定义 $dp(i, st)$ ，表示对 $i$ 个工人分配任务，已分配任务的状态是 $st$ 时，集合的最大值最小是多少

枚举 $st$ 的子集 $p$ ，那么存在 $i-1 \to i$ 的转移，对应第 $i$ 个人分配到的任务，状态压缩成 $p$
先计算出 $p$ 中有哪些工作是一定要做的，这些工作的完成时间记为 $\text{sum}$
然后计算出 $st$ 的补集 $q$ ，将 $p \cup q = st$ 的过程中，存在状态转移