做题记录——2.28-3.4
2022.2.28
CF1381C Mastermind
令 \(y = y-x\)。
那么选 \(y\) 的时候的充要条件是出现次数最多的颜色小于一半。
所以选 \(x\) 的时候大力选出现次数最多的就可以了。
CF1515F Phoenix and Earthquake
首先大力猜想，每次选和最大的两条边是最优的。方案用启发式合并，总能搞出来。貌似这个结论是对的。
更为简单的实现是找出一棵生成树。随便挑一个儿子。如果这个儿子的权值大于等于 \(x\)，就先修建这条边。否则最后修建这条边。证明归纳即可。
CF1361C Johnny and Megan's Necklace
你考虑枚举答案。然后你建 \(2^i\) 个虚点，每个点往对应虚点连边。
然后跑一个欧拉回路就行了。
CF1470C Strange Shuffle
毛估估想了个分块做法。
看了题解发现内鬼一定等于 \(k\)。
那就做完了。
2022.2.29 2022.3.1
CF1637F Towers
硬点一个 h 最大的点为根。然后只需要保证每个子树内有一个叶子，塔高度大于等于当前结点即可。
CF1474E What Is It?
一个很牛逼的构造题。
想让答案尽量大，然后毛估估一个答案上界。
然后构造一个就行了。
（我在写什么废话（。
CF1439B Graph Subset Problem
首先度数小于 \(k-1\) 的都可以扬了。
然后如果此时最小度数 \(\geq k\)，就搞定了。
否则 \(O(k^2)\) 特判一下。
最多只会被判 \(O({\sqrt m})\) 次。
CF734F Anton and School
我草我差点切了，然后交上去疯狂 WA13。
搞出唯一解 \(a\) 之后，要带回去判一下 \(b,c\) 是否合法。
CF1391E Pairs of Pairs
麻了看错题了。以为配对的两个点之间必须有边。
首先搞出 dfs 树，然后如果有链就直接选链。
否则就同一个 \(dep\) 的两个点配对就行了。
每个 \(dep\) 最多失配一个点，就行了。
CF1492E Almost Fault-Tolerant Database
只想出了 \(O(n m^2)\) 的暴力做法，太菜了 /kk 。
注意到显然要换和第一列不同的数。
于是要换的数的数量就是 \(min(4n,m)\) 级别的。
然后你结合上面这个暴力，大力搞一下就没了。
CF1479C Continuous City
好题。
首先可以把 \(L\) 转化为 1，接下来考虑 \(R = 2^k - 1\) 的情况。
我们考虑构造 \(i\) 个点，第 \(i\) 个点满足 \([1,2^i - 1]\)。
构造方法是第 \(i\) 个点向第 \(j(j>i)\) 个点连 \(2^i\) 的边就行了。
再考虑 \(R = 2^k + t\) 的情况。先把 \(R\) 减一，然后对于每一位，连接到对应的 \(i\) 号点就可以了。
CF1528D AaParsa
一开始想了个把每个点按时间分层做，然后死在了空间上，因为有 \(O(nm)\) 条边。
dijkstra 学傻了.jpg。
后面发现直接按照 dijkstra 的思想，每次找一个点松弛，然后暴力等待就行了。
CF923D Picking Strings
好题！！1
首先手玩一下，BC 等价。可以删去 B 前面的 A。后缀 A 动不了。
然后你就很接近正解了。
但是这题细节巨多，我 WA 了好多发，到最后忍不住看了题解。
2022.3.2
CF1438E Yurii Can Do Everything
考虑一个暴力，强行令 \(a_l \ge a_r\)。
可以发现对于每个左端点，暴力枚举，复杂度是对的。
然后你 reverse 一下再做一遍就可以了。
CF1427E Xum
有两种做法，然而我都不会。
第一种是考虑每次删除最高位的 1。
具体的实现方法是构造 \(y = x<
然后 3 次 xor 就能删掉一位。
第二种是构造一个 \(y\) 满足 \(gcd(x,y) = 1\)。
然后搞出 \(ax-by = 1\)，之后乱搞。
CF23C Oranges And Apples
若干年之前看过的经典 trick。
考虑按照一维排序，然后每两个之间取另一维更优的即可。
2022.3.3
SDOI2011 黑白棋
K-Nim 游戏，指每次最多取 \(k\) 堆中任意数量石子。
必败的充要条件是把所有石子数量转成二进制，记 \(sum_d\) 表示 \(d\) 这一位的和，所有 \(sum_d = 0\) 。
\(dp\) 比较容易。
CTSC2008 祭祀
在 DAG 上，最长反链=最小可重链覆盖。
传递闭包之后，等于最小不可重链覆盖。
而这个东西可以拆点之后跑二分图匹配求。