比赛链接

Solved by nikkukun & Potassium & qxforever.

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

1. 有鱼，抓一条鱼
2. 有蛤，抓一个蛤，鱼饵 +1
3. 可能没有鱼，但必能鱼饵 -1 来抓一条鱼
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$。

【留给 qxforever 的部分】

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 nikkukun.

水题不表。