zhangxixi的博客

定二分所谓的界+调整法：[AGC045B] 01 Unbalanced 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135125239 https://www.luogu.com.cn/problem/AT_agc045_b 考虑0为1，1为-1，然后就是使前缀和极差最小。（套路1） 一个常见思路是二分，也就是定上界M，使下界尽可能大，但此题不满足单调性，所以不能够二分。 我们考虑调整法。我们先让所有？为-1 然后求出当前max值为Z。则M的下界为Z。 如...

broder剃头去尾的新broder 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135122233 若红色为1串的broder，则显然黄串为2串的broder 因此broder在剃头去尾 可以用于均摊分析 题目：POI2012」Prefixuffix

Broder 和 Period 的性质 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121825 一个字符串的 border 可以被划分 O(log⁡n)O(\log n)O(logn) 段等差数列 border 和 Period 一一对应 现在等价于求 Period 为等差序列。 设有 p1,p2p_1,p_2p1​,p2​ 的Period。 p1,p2≥∣S∣2p_1,p_2\ge \frac {|S|} 2p1​,p2​≥2∣S∣​ ，...

周期引理 PL (Periodicity Lemma.) 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121747 原先串：若干 ppp ，加一个前缀，因此是 A(x)1−xp mod xn+1\dfrac {A(x)}{1-x^p}\bmod x^{n+1}1−xpA(x)​modxn+1 这个：  mod xn+1\bmod x^{n+1}modxn+1 为0。（多项式） 我们有 R(x) mod xn+1=0,deg(R)∈nR(x...

弱周期定理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，所以恰有偶数个奇点，两两匹配后完成。一条边的贡献是一入度一出度，而入度和出度...