主要思路
这题细节真他妈多。
首先，看到 SCC 大小少于 \(100\) 就可以知道是 DAG DP + Tarjan + 高斯消元了，比较显然。然而实现起来非常麻烦。我们在反图上做 DP 的时候，从 queue 拿出顶点后先高斯消元一波，把环内的、SCC 之间的（也就是之前求出的 \(dp[u]\)）一起放到方程组里进行消元即可。细节看代码吧，真的呕了。
标签归档： Tarjan
LibreOJ#3077. 「2019 集训队互测 Day 4」绝目编诗 – 题解
主要思路
这道题是要求你实现一个 Checker，来判断是否有长度相同的环。实现的主要方式是找出所有的环并放到桶里面进行统计。我们可以观察出一些简单的性质，来做一次判断：
- 如果存在一个边双连通分量，其 \(|E| – |V| \geq \sqrt{|V|} \)，那么一定是存在两个同长环的。这个具体证明可以进行平方，然后发现差值的平方大于点数，感性理解：通过鸽巢定理，出会有一些边构造出相同长度的环。
之后，我们可以考虑把度数为 2 的点去掉，缩成一张新的图。然后，再做暴力的 DFS 来判断是否存在同长环：具体而言，选择一个起点，然后在 DFS 之后删去。
时间复杂度是 \(\Theta(n^2)\) 的。
「国家集训队 2011 扬天」解题报告
A – 等差子序列
因为是个排列，读入时我们可以把已有的数值放在数轴上，发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组，维护串和反串的哈希然后判断即可。
[Fortuna OJ]Jan 10 省选组 – 解题报告
在纪中，不铺好蚊帐就等着第二天比赛 GG。
kal0rona
牛客CSP-S提高组赛前集训营 2 – 解题报告
这次比赛必须要仔细反省，不能再出现暑假的精神状态。
A – 服务器需求
假设我们有很多服务器了，我们现在按天考虑，进行服务器的分配：假设有一个服务器编号集合\(\{id_i\}\)，考虑一天天分配若干台，这样就可以保证每一台服务器的分配中不会出现同样的日期。
这样就可以分配完了，直接就有\(\sum a_i \leq |id_i| m\)。然后就是傻逼代码了。
[CEOI2011]Traffic 题解
主要思路
我们发现这其实就是一个多源覆盖问题。注意到「保证边在交点以外的任何地方不相交」，大概画个图就可以知道这样我们所覆盖的是一个区间（这有点像某年的一道跟种田有关的题目）。
如果没有这个性质，那么我们只能用 bitset 来维护所能到的点集，在缩完点上的 DAG 做需要\(\Theta(\frac{n^2}{32})\)的时间。然而，有了这个性质之后我们可以直接记录上下端点，相减得到答案。