zhangxixi的博客

弱周期定理WPL (Weak Periodicity Lemma.) 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121712 因为 sis_isi​ 可以去到 si−p,si+q…s_{i-p},s_{i+q}\dotssi−p​,si+q​… ，因此可以表示成 ap−bqap-bqap−bq 的形式。 本质：划分等价类，等价类有一个迭代的过程，怎么都可以走到 gcd⁡(p,q)\gcd(p,q)gcd(p,q) ，但走不到更小的

二分+dp优化：CF1550E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135117074 https://www.luogu.com.cn/problem/CF1550E 一眼二分，然后有个朴素dp， f(i,2k)f(i,2^k)f(i,2k) 表示在 iii 位置满足已经存在 sss 是否可行。发现记录的值只有0 / 1，直接状态如dp， f(s)f(s)f(s) 表示满足 sss 的最前位置。 继续优化。状态明显不可以优化，只能优化转移了。这种...

（口胡）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...