AGC001F

已单独写题解就不粘过来了。

Gym101806T

根据某知名贪心，先给 $L$ 加上 $D$ ，然后按照 $L$ 排序，可以得到一个正确的顺序，最后答案的序列一定是在这个顺序下选取的。

相当于我们需要选择一个最长子序列，满足这个子序列任意一段前缀的和小于等于这个位置的 $L$ 。

这个问题类似于 LIS 。有一种直接贪心的做法。我们考虑对当前位置，维护出满足当前位置以及之前所有位置的限制的的最长的子序列，且满足 $\sum D$ 尽量小。

我们用堆维护当前子序列中所有的 $D$ 。每次到一个位置 $i$ ，我们先尝试把这个数给加进去，然后看看是否满足限制。如果不满足，我们弹出堆中最大的元素。不难发现弹出一个元素后一定可以满足这个位置的限制，同时由于弹出的是最大的，我们可以得到这个位置前缀的最优序列。

复杂度 $O(n\log n)$ 。

Gym101239L

大概这题不会是因为不会哈夫曼编码。

哈夫曼编码的思想大概是，每次合并当前权值最小的两堆作为二叉树的两边，这个子树的权值就是两边的和。一直这么合并下去，直到只有一棵树，这个 trie 就是最优的编码树。

然后知道这个后这题就很板了。注意到不同的权值个数只有 $O(n^3)$ 种。我们用一个 pair 表示权值以及这个权值有多少种。然后每次拿最小的权值来合并。如果它的个数超过 $1$ 就把个数折半，权值乘 $2$ 也就是自己和自己合并，如果是奇数就留下一个。权值最小个数正好是 $1$ 那么就拿它和当前堆顶的一个合并即可。

CF1427E Xum

显然 $x$ 如果在黑板上，写出 $tx$ 只需要 $O(\log t)$ 次。

设输入的数是 $n$ ，那么最重要的观察在于，如果有数满足 $\gcd(n,a) = 1$ 并且都在黑板上，一定有 $a$ 模 $n$ 的逆元存在，也就是可以扩欧算出 $ya \equiv 1 \pmod n$ 。然后如果 $ya$ 是奇数，就用 $ya$ 和 $ya - 1$ 做异或，否则用 $ya + n - 1$ 和 $ya + n$ 做异或。这样一定可以得到 $1$ 。

如何构造一个 $a$ 呢，没想到题解的高论做法于是直接随机。。每次我们随机 $r_1,r_2$ 并且算出 $r_1n\ \text{xor}\ r_2n$ 。这个数看起来就具有很强的随机性，如果是均匀随机，算一下它与 $3 \times 5\times \dots \times 19$ 互质的概率大概是 $1/3$ ，所以随机次数非常的少。

但是呢，注意 $2^{19} + 1$ 这个数。因为如果随机的范围不够大，可能这两个数都在 $2^{19}$ 内，然后就 $a(2^{19} + 1)\ \text{xor}\ b(2^{19} + 1) = (a\ \text{xor}\ b)(2^{19} + 1)$ 然后就 GG 了。所以经过各种调参发现两个数在 $10^7$ 级别随机会在乘起来不炸 $5\times 10^{18}$ 的情况下通过这种数据。。

实际上有优秀的构造方法。通过左移 $n$ 让 $n$ 最低位和最高位重合并且去掉，这样算出来就是 $n + (n \times 2^{k}) - 2^{k+1}$ ，必然与 $n$ 互质。

CF1398F Controversial Rounds

考虑当前位置在 $i$ ，从 $i$ 到 $i+k-1$ 是否可以通过换 ? 来整成全部相同。如果可以，那么我们可以直接让 $i$ 增加 $k$ 。否则，我们考虑把 $i$ 移动到 $i+k-1$ 所在的连续段的开头。在下一次移动 $i$ 的过程中，$i$ 一定会跳过下一个连通块本身。所以只需要至多 $2$ 次操作，就可以让 $i$ 增加 $k$ 。这么一直进行下去，复杂度 $O(n\ln n)$。

预处理每个东西最靠左的端点是啥，这个可以对每个位置维护以这个位置为 $0/1$ 向左可以延申到多少，再维护这个位置所在的连续段向左可以到多少。

Gym101239J

如图，长方形的面积是 $(a+b)(x+y) - ax -by = ay+bx$ ，满足 $a,b,x,y \ge 1$ ，明显这个东西就是个卷积的形式。$F$ 表示约数个数的生成函数，那么一个固定的面积的答案就是 $[x^i] F^2$ ，NTT 即可。

然后上个 ST 表即可。