计蒜客20180415 Sol.

计蒜客20180415 Sol.

……把福利赛打成退役赛吗……

B

无向图，判断五元环。$ |V|\le200 $ .

一直在往 dfs 树的返祖边考虑……但其实不能这么做。

枚举一个点和一条边后，剩下就是要看这个点和这条边的两个端点是否各存在一个公共邻点。这个可以用 bitset 加速判定。据说不用也可以过。复杂度是 $ \mathcal O({n^4\over 64}) $ .

实现的时候要注意两个端点都要有一条连出去的点且不能是对方。

其实这个问题我在之前辗转反侧的夜晚考虑过数次。但今天刚好忘了得出来的结论是返祖边不能做或者至少不好做。而判断三元环、四元环这些经典问题都是直接用 bitset 。我似乎对经典题毫无察觉。学到了学到了。

考虑一下六元环怎么做？三元环计数怎么做？

C

给出一个集合，可重复抽三个数。已知最后各个数的组成方案数，求复原原集合或不可能。$ |U|\le6 $ .

注意这是一个集合异或卷积的三次方…… FWT 一下看看原幂级数合不合法存不存在就可以了……

细节很多。比方说域的特征不能为 $ 2 $ ，最后所有数的和要为 $ n $ ，不能出现负数，行末不能有空格，立方根可能不是整数。

想到这个思路应该很简单的啊……应该说意识还不够……不熟练？一直往 DP 方向想，可是要是写出状压式子不久完了吗…………菜爆。

G

求所有点对的最小瓶颈路径。$ |V|\le10^5 $ .

套路 MST. 然后我建出这棵树后就开始取最大边来边分了……T爆。

实际上由一个技巧，就是注意到连接两个连通块时我们并不关心是哪两个点具体连边。那么在并查集上直接维护子树 tag 即可。不带路径压缩比较好写，但是每次加边多带一个 $ \log $ . 总的时间是 $ \mathcal O(n\log n) $ ，全部瓶颈在于排序。