2.17~2.18 题单选做

Sister, Friend, Lover

いつだってそばにいるから

不论何时我都愿伴你左右

簡単にナシと决めないで

所以 不要轻易否决我

受け止めて

接纳我吧

CF1854D Michael and Hotel

考察可以通过询问完成：

1. \(k\) 取足够大 + 二分 得到某点指向的环上的一个点。

2. \(k\) 取 1 + 二分 得到某个点的后继。

这两个操作的复杂度均为 \(O(\log n)\)。

显然可以通过 \(O(n\log n)\) 还原整张图。但超出了询问次数。

考虑确定出 1 指向的环，即可 1 次操作判断一个点是否和 1 指向同一个环。设 \(1\) 指向的环为 \(R\)。设计阈值 \(\lambda\)。先找到环上的 \(\lambda\) 个点加入点集 \(S\)。然后我们做 \(O(\log\frac{n}{\lambda})\) 次如下扩增操作：

• 检查每个 \(S\) 之外的点通过 \(\lambda\) 步是否能到达 \(S\)，将可以到达的点加入 \(S\)。
• 将 \(\lambda\) 翻倍。

容易发现这样一定能保证 \(S \supset R\)。总操作次数 \(O(\lambda\log n+n\log\frac{n}{\lambda})\) 在 \(\lambda\) 取 \(\frac{n}{\log n}\) 时取到 \(O(n\log\log n)\) 可以通过。

CF1916F Group Division

增强条件构造 & 增量构造。

考虑维护这样一个过程：初始时 \(S_2\) 包含全部点，依次加入 \(n_1\) 个点并时刻满足条件。

做法：在当前 \(S_2\) 中找出一个和 \(S_1\) 连通的非割点。

存在性证明：\(S_2\) 任取一个割点去掉，分开的连通块均与 \(S_1\) 连通，反之整张图非点双。找到 \(S_2\) 圆方树叶子处的点双选择一个非割点即可。

CF1218G Alpha planetary system

同样是增强条件构造。联系边权集合和三分图的关系，猜测从模 3 意义下构造——三个点集中的权值模 3 分别取 1,2,3。

非常高妙的，考虑找出一棵生成树，将非树边填 3 不管，由于每个点权值确定，则每条树边权值也确定（用于调整它连接的儿子）。根节点可能无法调整。

1. 存在奇环。我们惊喜地发现在环上的边逐位加 1,2,1,2, 将其中单独一个点的权值 \(+1\)。这是我们将一个位于奇环上的点作为根即可完美构造。

2. 不存在奇环。图其实是二分图，我们将点重染色为 1 和 2。同样通过树边构造使得它们 模 3 同余 1,2。但是同样要纠结根节点错误的情况，不如设根期望填 1，但实际填了 2：

   1. 根节点儿子唯一：儿子权值一定大于根。不需要从模意义考虑直接满足条件。
   2. 根节点儿子不唯一：选两个儿子将它们的父边 +1。

CF1437F Emotional Fishermen

刻画排列（放置元素顺序相关）的一种方法：考虑特定的插入顺序。经过尝试后得出可行的转移方式。

将 a 从大到小排序。设 \(f_{i, j}\) 为考虑前 \(i\) 个元素，合法序列末尾大小为 \(j\) 的方案数。状态设计的优秀之处在于后面插入的元素无法改变前面元素的合法性——而从小到大 DP 则没有这样的保证。

考虑转移：

将 \(a_i\) 插在序列前面，需满足 \(2a_i\le j\)：\(f_{i-1,j}\to f_{i, a_i}\)。

将 \(a_i\) 插在序列其他位置：\(\lambda f_{i-1,j}\to f_{i, j}\)。

当满足 \(2a_i\le j\) 时 \(a_i\) 可以插在序列第二位，\(\lambda=i-1\)。否则 \(\lambda=i-2\)。

CF1218G Alpha planetary system

将区间按左端点升序排序。

设计状态 \(f_{i, c}\) 表示考虑前 \(i\) 个区间，满足最后一个纯色区间为 \(i\)，填颜色 \(c\)，且不存在纯色区间 \(j(j<i)\) 使得 \(r_j\ge r_i\) 的方案中纯色区间最大个数。

考虑转移：枚举下一个纯色区间 \(j(j>i)\)。当区间 \(i, j\) 相交或存在区间 \(k\) 同时和 \(i, j\) 相交时，\(i, j\) 的颜色必须相同。否则 \(j\) 的颜色不同于 \(i\) 可以任取。在扫描 \(j\) 的过程中，我们考虑统计可能的被区间 \(i\) 包含的纯色区间，显然它只能和 \(i\) 同色，并且肯定合法——这样我们就解决了上述状态中纯色区间不能包含的漏洞。

时间复杂度为 \(O(n^2c)\)。