比赛链接

Solved by nikkukun & Potassium & qxforever.

有 $n \leq 2 \times 10^6$ 个池塘，每个池塘里有蛤和鱼（可能都有，可能都没有，可能不都有）。依次经过所有池塘，每个池塘可以：

1. 有鱼，抓一条鱼
2. 有蛤，抓一个蛤，鱼饵 +1
3. 可能没有鱼，但必能鱼饵 -1 来抓一条鱼
4. 摸鱼

求最多能抓的鱼。

显然有鱼时一定抓鱼，于是变成决策仅有蛤的时候是抓蛤还是抓鱼。考虑每个仅有蛤的位置贪心与其之后的空池塘匹配，剩余的仅有蛤的位置贪心匹配即可。

Solved by qxforever & nikkukun.

给一个长度 $n$ 的字符串，$q$ 次操作

• 将最左边 $x$ 个字符移到最右边或将最右边的字符移到最左边
• 询问下标 $x$ 对应的字符

第一种操作相当于移动字符串起始位置的下标。维护这个下标即可。

Solved by qxforever.

给定一个多边形，表示右手的形状。有 $t$ 组询问，每组询问给 $20$ 个点，判断这些点形成的是右手还是左手。

比赛时没细想，直接当成判断两个多边形是否全等做了。枚举起点，依次判断角度及边长，$O(n^2)$ 。可以 hash + kmp 做到 $O(n)$ 。

其实因为给定的一定是左手或者右手，只需要判断最长边的下一条边的长度。

Solved by qxforever.

在二维平面上选 $n$ 个整点染为黑色，其他整点为白色。问是否存在一种方案使得恰好有 $m$ 对黑白点对的曼哈顿距离为 $1$ 。$n\le 50$

考虑按矩形填充黑点。设 $f_{i,j}$ 表示 $i$ 个黑点，围成底边长为 $j$ 的矩形的点对数量，这个比较容易计算。 再设 $dp_{i,j}$ 表示 $i$ 个黑点，形成 $j$ 对点对是否可行。由 $f$ 进行 dp 的转移，类似背包的过程。时间复杂度 $O(n^4)$ 。

Solved by qxforever & nikkukun.

给一个长度 $n \leq 2 \times 10^5$ 的数组 $a_1, a_2, \ldots, a_n$，元素范围在 $[0, 10^9]$ 且 $n$ 为偶数。对 $1 \sim n$ 的数两两匹配，你需要给出两种匹配方案，满足两种方案中不存在相同的匹配，并最小化

$$ \sum_{i = 1}^n |a_i - a_{p(i)}| + \sum_{i = 1}^n |a_i - a_{q(i)}| $$

其中 $p(i)$ 和 $q(i)$ 依次表示 $a_i$ 在两次匹配中匹配的下标，且 $p(i) \neq i,\ p(p(i)) = i$。

显然最小是 $1 \sim 2,\ 2 \sim 3,\ \ldots,\ n-1 \sim n$ 这样的匹配。手玩之后发现第二小的匹配可以分成很多段长度为 4 或长度为 6 的段，段内匹配为 $1 \sim 3,\ 2 \sim 4$ 和 $1 \sim 3,\ 2 \sim 5,\ 3 \sim 6$，DP 即可。

Solved by nikkukun & Potassium & qxforever.

$10^5$ 次给出 $a, b$（$\leq 2 \times 10^6$），寻找正整数 $c, d, e, f$ 满足：

1. $\dfrac cd - \dfrac ef = \dfrac ab$
2. 两个分数分母小于 $b$
3. 两个分数分子不超过 $4 \times 10^{12}$

或说明无解。

先考虑 $(a, b) \neq 1$ 的情况，并令 $a' = \dfrac a{(a, b)},\ b' = \dfrac b{(a, b)}$，显然有 $\dfrac {a'+1}{b'} - \dfrac {1}{b'} = \dfrac ab$，于是只用考虑 $(a, b) = 1$ 的情况。

发现将式子通分后，分母很像二元一次方程的形式，为了有解应当尽可能让 $(d, f) = 1$，因此如果能找到互质的 $d, f$ 满足 $df = b$，则分母的方程 $cf - de = a$ 必然有解，且最小正整数解在 $\mathrm{lcm}(d, f)$ 内。这个互质的数可以在线筛过程中用其最小质因数的幂处理。

特殊地，如果 $b = p^k$ 是一个质数的幂，则可以取 $d = p,\ f = p^{k-1}$，只不过此时需要特判一下 $p \mid a$ 是否成立，其他地方同上。最后再判一下 $b = 1$ 时无解即可。

Solved by Potassium & nikkukun.

给一棵树， $q$ 次操作，每次将选定点所在集合连接的所有点合并成一个集合，求最终每个点所属集合。$1\le n,m,q\le 8e5$。

暴力模拟，启发式合并邻接表即可。

要学会集合交换函数：s1.swap(s2) 。

Upsolved by nikkukun.

为了方便说明，下标使用和原题有所不同。

有一个长度为 $n \leq 2 \times 10^6$ 的串 $s_0 = \mathtt{"01234567890123.."}$。现在按照如下方法构造 $s_1, s_2, \ldots, s_n$：

1. 题目给定一个 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$，和一个范围在 $[0, 9]$ 的数组 $d$；
2. 对 $i = 1, 2, \ldots, n$，将 $s_{i-1}$ 的第 $p_i$ 个位置修改为 $d_i$，获得 $s_i$。

最后对 $n + 1$ 个二元组 $(s_i, i)$ 升序排序，给出在此结果下每个 $i$ 的名次。你需要给出一个 $O(n)$ 的算法。

先假设第 $k$ 次操作修改了第一个值（即 $p_k = 1$），且修改后的值 $d_i$ 与原来的值不同，则当值被往大改时，$[1, k-1]$ 的排名一定永远小于 $[k, n]$；当值被往小改时，$[1, k-1]$ 的结果永远大于 $[k, n]$。这样问题就可以递归下去：找到区间中 $p_i$ 最小的位置，若右边的区间较大，则给右边区间的排名整体加一个偏移量，接着递归两个子区间。整体加偏移量的操作用前缀和差分就能实现，而递归找最小值的操作正是笛卡尔树做的事。

有个 tricky 的技巧：若某次修改前后相等，则可以令 $p_i = n + i$，这样就可以将本次操作放到所有使 $s$ 改变的操作之后，得到正确答案。

Solved by nikkukun.

水题不表。