0124 训练小记

0124 训练小记

ARC153F Tri-Colored Paths

图上问题感觉我做的不多，也没什么好套的常见套路。

所以考虑从特殊情形和边缘情况什么的入手。

那么我们考虑环。

正难则反，统计不存在有三种颜色的路径的图的个数。

对于三色环，大小只能为 \(3\)，否则一定矛盾。

此外三色环只能有一个点有其他边，而且这条边是原图的一个割边，然后其他的外面的边都是同色的。

双色环想想发现肯定不存在。

然后只有单色环，这种情况找一个割点，把图分成若干个部分，每个部分颜色相同。

所以就分成了两种情况分别讨论一下，用点双维护即可。

注意 \(n\le 4\) 比较特殊，手玩之后特判一下。

时间复杂度：\(O(n)\)。

Gym 100134I I Identification of Protein

source NEERC2012

转成整数，发现 \(\text{lcm}\) 非常的大，在 \(n\le 400\) 内 \(P,Q\) 个数是固定的。

先解出来，然后 \(dp\)。

\(dp(i,j,k)\) 表示前后缀分别考虑 \(k\) 个，前缀有 \(j\) 个 \(P\)，后缀有 \(k\) 个 \(P\)，转移是容易的。

在做 \(dp\) 的时候要同时考虑前后缀，因为不能相同。

感觉可能有点细节，没写（

时间复杂度：\(O(n^3)\)。

ARC154E Reverse and Inversion

首先拆一拆贡献，令 \(f(i)\) 为位置 \(i\) 的贡献。

容易发现 \(f(i)=i(i-p_i)\)，证明是容易的。

然后打一张表发现任意数字 \(x\)，经过若干次操作后，除了在初始位置 \(q_x\)，其他都是对称的。

\(q_x\) 的多出来的情况全都是一次都没有操作到 \(x\) 的。

也就是对于一个数字 \(x\) 被操作过，期望位置在 \(\frac{n+1} 2\)。

再统计一次都没操作过的即可。

时间复杂度：\(O(n\log V)\)

Baekjoon12219 Symmetric Trees (Large)

这种很对称的东西，让我们想到重心。

如果这棵树有一个重心，必定在轴上，那么以他为根把所有子树拿出来。

所有子树中只有至多两个可以在轴上放，而且得满足自身是对称的。

其他都得两两配对，整个过程树哈希后贪心即可。

有两个重心的情况，要么重心都在轴上，这个时候转为类似第一种情况。

否则两边各一个，断开中间的边，两棵子树匹配就可以。

时间复杂度：\(O(n\log n)\)。

AT_dwacon6th_prelims_e Span Covering

有一个很重要的事情，把线段长度从大到小排序做。

这么做的好处在于，不存在后来的线段完全覆盖前面的线段，这样也就不存在，覆盖两段空格。

也就是每次覆盖到的只是一段空格，所以就不用关心目前的覆盖状态了，dp 状态不用维护指数级的。

然后是一个比较抽象的 dp，这里贴一个 CG 的题解。

AT5744 Span Covering - Rushroom!

Gym102268J Jealous Split

source 300iq contest I

300iq 题好难。

结论题，结论为 \(\sum s_i^2\) 最小的方案一定合法。

然后变成了 wqs二分 板板。

但是这个题要输出方案很坑啊！！

具体来说三点共线的情况要分别把最大段数和最小段数分别算出来。

找方案的时候时时刻刻保证 \(mn\le k\le mx\)。

时间复杂度：\(O(n\log V)\)。