zhangxixi的博客

dp状态设计——转封闭形式！：CF1517F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135140525 https://www.luogu.com.cn/problem/CF1517F 一些基本的转化： 求所有方案的 ∑r\sum r∑r ，然后除以 2n2^n2n 可以枚举 rrr ，然后求出答案至少为 rrr 的有多少种。此处不需要差分后再乘 rrr ，我们直接加，类似增量构造的思想即可 我们可以对好人为白，坏人为黑，目标是使黑人在 ...

平面图上最大流通过转对偶图再转成树+set维护计算几何求最小环：qoj5048 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135133585 https://qoj.ac/problem/5048 因此我们可以平面图转对偶图，如下图，假如我们割黄边，就是给所有蓝边加黄边的权值 每次找一条边权最小的边，满足它恰好有一侧是无界区域。将它删 去，将它的边权加到它所在最小环的其他边上。可以证明这个操作前后 任意两点的最大流大小不变。 对于转最小环的过程，我...

增量构造+答案上界推出增量构造上界确定复杂度：CF1063F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135129285 https://www.luogu.com.cn/problem/CF1063F 可以贪心一波， ttt 长度必然是 ans,ans−1,ans−2,ans−3,…,3,2,1ans,ans-1,ans-2,ans-3,\dots,3,2,1ans,ans−1,ans−2,ans−3,…,3,2,1 这样子。 如果一个 kkk 不存...

循环同构串的判断+broder剃头截尾法实现均摊：P3546 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135126979 https://www.luogu.com.cn/problem/P3546 两个串的循环同构可以表示成： AB ， BA ，所以我们等价于在原串求： 显然A可以枚举，我们现在就是要求原串所有中心串的最长不交broder。 这个方法之前提到过，我们可以用broder剃头截尾法。 设 fif_ifi​ 表示 AAA 的长度为 iii...

定二分所谓的界+调整法：[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 的最前位置。 继续优化。状态明显不可以优化，只能优化转移了。这种...