zhangxixi的博客

（口胡）dp+四边形不等式优化+矩阵优化：P8864 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135116753 https://www.luogu.com.cn/problem/P8864 一个经典套路，只是以前是用在差分上，现在是异或，所以我们设前缀异或和序列为 sss ，每次操作相当于交换 si−1s_{i-1}si−1​ 和 si+1s_{i+1}si+1​ 。区间内原先1的个数相当于 sss 的段数。 我们考虑 sss 中的1的连续段，可以是...

平面图转对偶图 + 平面图上最小割转对偶图上最短路 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135111564 如上图所示，有一个平面图，有很多点组成，每个接触线有一个权值。我们可以把平面图转成对偶图。我们在 (s,t)(s,t)(s,t) 之间画一条直线，把外面分成两个面。我们把每个面视为一个点。如果两个面有接触线，他们就连一条边，边的边权，就是接触线的边权。 在上图上，如如果我们想求 s→ts\to ts→t 的最大流，根据最大流 = 最小割，我...

竞赛图及其缩点成链、强连通分量相关性质：CF1268D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135110596 考虑如何判断一个竞赛图是否强联通。 如果一个竞赛图不强联通，说明其存在一个子图，满足这个子图没有入边 / 出边。 我们以没有出边的情况来讨论。首先大小为 nnn 的子图之间至少产生 n(n−1)2\frac {n(n-1)}22n(n−1)​ 个出度，因为没有出度，所以我们就令其出度为这个就行了。从贪心角度考虑，我们直接按出度排序即可。 ...

通过欧拉回路及其相关性质对边进行定向：CF527E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135107666 https://www.luogu.com.cn/problem/CF527E 出入度都为偶数？而且还联通 ?明摆和欧拉图、欧拉路径相关。 可以先猜一个结论，当所有点度数都为偶时，一定可以成功定向。 先看无向图。首先一个点的度数，必须为偶数。而无向图一条边的贡献为2，所以恰有偶数个奇点，两两匹配后完成。一条边的贡献是一入度一出度，而入度和出度...

二进制下传优化AND连边：UOJ176 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135106721 https://vj.imken.moe/contest/600665#problem/E 一个朴素思路是枚举 ppp ，然后再枚举 x&y=px\&y=px&y=p ，如果 x,yx,yx,y 不在一起，则连一条边。 考虑优化。如果 x,yx,yx,y 的交集更大，则不是 ppp 。所以一个思路是取出 ppp 所有0的位置，然后...

若竞赛图中有环，则一定构成三元环 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135099517 考虑一个 n(n≥4)n(n\ge 4)n(n≥4) 元环，肯定有弦。 我们就可以通过这个弦不断把环缩小即可。 同时竞赛图中不存在两个点的强连通分量。

竞赛图缩点后成链状（拓扑序唯一） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132993089 一个常见结论 竞赛图缩点后必然成链状。 不是真正的链，只是类似链的偏序关系。

斐波那契的平方、立方问题——考虑几何立体意义（数形结合法）：P9510 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135094722 https://www.luogu.com.cn/problem/P9510 关于斐波那契和的平方，其实就是正方形的面积和： 也就是 f(i)∗f(i+1)f(i)*f(i+1)f(i)∗f(i+1) 我们现在要求立方，但我们可以可以发现红色部分的结果是一样的： 直接三条棱表示除了，就是 f(i)∗f(i−1)∗f(i...

势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093792 https://www.luogu.com.cn/problem/P7446 https://www.luogu.com.cn/problem/CF1491H 看到题，发现只有减，就和势能有关。维护势能，像这种题，树形ds显然不好做，所以可以去考虑进行分块。 考虑分块。每个块记录一个 bib_ibi​ ， iii 的...

考虑全选然后删的代价转最小割+最小割同一类连inf的边：AT_arc107_f 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093630 https://www.luogu.com.cn/problem/AT_arc107_f 理论上界为 ∑∣bi∣\sum |b_i|∑∣bi​∣ 。考虑现在减少会有什么情况： 不选。代价为 ai+∣bi∣a_i+|b_i|ai​+∣bi​∣ 原先为正，所在连通块取绝对值后变负。代价为 −2∣bi∣-2|b_...