BZOJ2707:「SDOI2012」走迷宫 – 题解

主要思路

这题细节真他妈多。

首先,看到 SCC 大小少于 \(100\) 就可以知道是 DAG DP + Tarjan + 高斯消元了,比较显然。然而实现起来非常麻烦。我们在反图上做 DP 的时候,从 queue 拿出顶点后先高斯消元一波,把环内的、SCC 之间的(也就是之前求出的 \(dp[u]\))一起放到方程组里进行消元即可。细节看代码吧,真的呕了。

继续阅读BZOJ2707:「SDOI2012」走迷宫 – 题解

LibreOJ#3077. 「2019 集训队互测 Day 4」绝目编诗 – 题解

主要思路

这道题是要求你实现一个 Checker,来判断是否有长度相同的环。实现的主要方式是找出所有的环并放到桶里面进行统计。我们可以观察出一些简单的性质,来做一次判断:

  • 如果存在一个边双连通分量,其 \(|E| – |V| \geq \sqrt{|V|} \),那么一定是存在两个同长环的。这个具体证明可以进行平方,然后发现差值的平方大于点数,感性理解:通过鸽巢定理,出会有一些边构造出相同长度的环。

之后,我们可以考虑把度数为 2 的点去掉,缩成一张新的图。然后,再做暴力的 DFS 来判断是否存在同长环:具体而言,选择一个起点,然后在 DFS 之后删去。

时间复杂度是 \(\Theta(n^2)\) 的。

继续阅读LibreOJ#3077. 「2019 集训队互测 Day 4」绝目编诗 – 题解

「国家集训队 2011 扬天」解题报告

A – 等差子序列

因为是个排列,读入时我们可以把已有的数值放在数轴上,发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组,维护串和反串的哈希然后判断即可。

继续阅读「国家集训队 2011 扬天」解题报告

牛客CSP-S提高组赛前集训营 2 – 解题报告

这次比赛必须要仔细反省,不能再出现暑假的精神状态。

A – 服务器需求

假设我们有很多服务器了,我们现在按天考虑,进行服务器的分配:假设有一个服务器编号集合\(\{id_i\}\),考虑一天天分配若干台,这样就可以保证每一台服务器的分配中不会出现同样的日期。

这样就可以分配完了,直接就有\(\sum a_i \leq |id_i| m\)。然后就是傻逼代码了。

继续阅读牛客CSP-S提高组赛前集训营 2 – 解题报告

[CEOI2011]Traffic 题解

主要思路

我们发现这其实就是一个多源覆盖问题。注意到「保证边在交点以外的任何地方不相交」,大概画个图就可以知道这样我们所覆盖的是一个区间(这有点像某年的一道跟种田有关的题目)。

如果没有这个性质,那么我们只能用 bitset 来维护所能到的点集,在缩完点上的 DAG 做需要\(\Theta(\frac{n^2}{32})\)的时间。然而,有了这个性质之后我们可以直接记录上下端点,相减得到答案。

继续阅读[CEOI2011]Traffic 题解