NOIP 前做题

CF1439B Graph Subset Problem

对于二可以用一个经典的求 k-core 的算法，每次拓扑删除那些度数小的点。然后到了 (k) 的时候我们就直接看一下是不是全部被删光了即可。

关于第一个求团。我们发现一个大小为 (k) 的团在不存在 k-core 的情况，这些点都必然是 (k-1)-core 中的点。于是我们对于每个在求 (k-1) 的时候求出来的点遍历它所有连接的点，然后判断是否是团。这个单次操作是 (O(k^2)) 的。

但是，实际上 k-core 点的个数是 (O(m/k)) 的级别的，这意味着求团的复杂度为 (O(mk))。然后，团的边数应该在 (O(k^2)=O(m))，也就是说复杂度是 (O(msqrt{m}))。

具体操作时，我们维护一下 deg，然后用 unordered_map 作邻接矩阵。本人曾经使用过 unordered_set 来代替 vector 和 deg 存邻接表，然后被卡常死了。然后数据中还存在卡 unordered_map 的数据……

https://codeforces.com/contest/1439/submission/131558660

CF1340D Nastya and Time Machine

考虑其欧拉环游序。每一次一个点出现，它必然是不同的时间。可以得到理论下界为 (D=max deg(u))。实际上这个下界可以达到。考虑钦定每个点出来的时间是进来的时间 -1。这是可以构造完成的。遍历的时候，如果一个点加到 (D)，就穿越到 (D-deg(u))。

https://codeforces.com/contest/1340/submission/131561302

CERC2014 Outer space invaders

时间离散化，然后对时间做区间 DP。考虑一个区间 (f(l,r)) 的全部被杀死的方法。容易知道这个区间中距离最远的一定被直接带走。（注意，一定是被完全包含的那一个，否则会被更大的区间统计到）所以我们枚举带走他的时间。

https://codeforces.com/gym/100543/submission/131607895

CERC2017 Justified Jungle

存在 (k) 的解相当于子树大小为 (frac{n}{k+1}) 倍数的个数为 (k+1)。于是对于一个子树我们更新即可。

https://codeforces.com/gym/101620/submission/131608594

COCI2019.12 Sob

首先题面说了对于任意 (n,m) 都可实现，所以考虑递归求解。

找到 (A) 中最大的数，设其为 (u)；我们暴力找到 (B) （设其为区间 ([l,r]) ）中最小的 (v) 与其匹配。可以证明，(B) 的 ([l,v]) 和 (A) 的 ([u-v+l,u]) 区间都能一一顺次匹配。于是就能转化为更小规模的问题了。

https://loj.ac/s/1271785

AGC043B 123 Triangle

很人类智慧。首先全体 -1，这样保证数字都在 0~2 之内。

然后首先 (0) 对答案没有影响。看 (1,2)。

考虑设一个数的被计算次数为 (c_i)，表示这个数在运算中出现了多少次（算正负）。

(1) 算了奇数次：那么答案必然为 (1) （必然为奇数）。
(1) 算了偶数次：那么答案为 (0)。
(1) 没有出现且 (2) 算了奇数次：那么答案为 (2)（加减偶数次的话变化一定是 (4) 的倍数，也就是加减 4，所以为 (2)）。
(1) 没有出现且 (2) 算了奇数次：那么答案为 (0)。

至于如何算出现次数，第 (i) 位会被算 (inom{n-1}{i-1}) 次。(inom{n}{m}equiv 1 pmod 2) 的充要调键位 (n&m=m)。

https://atcoder.jp/contests/agc043/submissions/26519645

CF1322B

考虑影响第 (k) 取值的东西。考虑 (b_i=a_i\%2^{k+1})，则 (a_i+a_i) 在第 (k) 位为 (1) 当且仅当他们的和 (in [2^k,2^{k+1}-1]cup [2^k+2^{k+1},2^{k+2}-2])。two-pointers 扫一下即可。注意数对无序所以/2。

https://codeforces.com/contest/1322/submission/131726261

CF1379C

有种被 div2 反杀的奇怪感觉……

首先显然一定是一堆同样 (b) 加上一些 (a) 的形式。那么枚举这个 (b) 是啥，然后看 (a) 选哪几个即可。二分出比 (b) 大的最小的 (a)。

https://codeforces.com/contest/1379/submission/131731985

CF1410F

一开始看错题了……不过无论有没有看错题这题都挺简单的。

维护一棵线段树。设一个点的高度为这个点的区间长度对 (2) 取对数（叶节点深度 (0) 其他为子节点深度 (+1)）。然后每个点维护一串标记，(t_{u,i}) 表示 (u) 子树中高度为 (i) 的点需不需要交换自己的两个子节点。这个标记是容易执行容易下放的。复杂度 (O(nlog n+qlog^2n))。