11.11 写题

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

_H_33_XB_HR_KGX401MU`7J.png

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

然后上个 ST 表即可。

文章作者: yijan
文章链接: https://yijan.co/2020/11/18/1111-xie-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog