swift's blog

模拟赛 T2

http://47.92.197.167:5283/contest/236/problem/2

模拟赛 T2

http://47.92.197.167:5283/contest/240/problem/2

首先求出一棵 dfs 树，把要割的变分成树边和非树边两类，存在一个结论：

如果存在一个割掉的边的子集，使所有没被割掉的非树边都覆盖了偶数条在这个集合内的树边，那么这种割边方案可以使原图不连通。

Phorni

后缀平衡树模版，开个线段树维护区间询问就行。

code: /code/2022.4.22/bz3682.cpp

【集训队作业2018】小Z的礼物

Min-Max 容斥后可以得到答案：

ARC062D

首先找出所有的点双，对于不在点双内（在一个两个点的点双内）的边，显然提供 k 的贡献，对于为环的点双，答案可以用 Burnside 引理来算，对于不为环的点双，发现我们很容易把任意两条边交换到同一个度数 >2 的点上，

前夕

设 $G_i={n \choose i}2^{2^{n-i}}$ 为钦定 i 个元素在交集中的方案数，但由于 n 太大没有办法直接二项式反演。

[CQOI2012]局部极小值

考虑容斥，钦定一些位置为局部极小值，因为 4*7 的格子中最多有 8 个局部极小值，可以考虑状压 dp 。

[JLOI2015]装备购买

用拟阵可以证明最小线性基就是从小到大尝试插入得到的，所以直接做就行。

第一次用 std::valarray。

最小树形图

模版。

code: /code/2022.4.14/ac8994.cpp

Sereja and Arcs

设出现次数 $>\sqrt{n}$ 的颜色为“大颜色”，剩下的为“小颜色”，小-小 的答案因为相同小颜色的点对最多只有 $n \sqrt n$ 个所以可以直接扫描线 + 树状数组，注意去除四个颜色都相同的情况。