zhangxixi的博客

原根 + 背包 + bitset优化 + 二进制分组：0115B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135609260 http://47.92.197.167:5283/contest/451/problem/2 原根： g1,…,gp−1g^1,\dots,g^{p-1}g1,…,gp−1 在  mod p\bmod pmodp 意义下取遍 1∼p−11\sim p-11∼p−1 。在 ppp 为质数时， ggg 不超过 p14p^{\fr...

对上面有要求的树形dp：0115A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135608809 http://47.92.197.167:5283/contest/451/problem/1 我初始的思路是维护一个 dp(i,j)dp(i,j)dp(i,j) ，表示以 iii 根，向下染黑最远 jjj 层，但这样子统计贡献就很难维护。 不妨换个思路，这个 jjj 变成往上钦定要至少 jjj 层。那样子每个染黑的时候的贡献是已经确定了的。 而对于儿子的 ...

枚举LCA+分类讨论列式子：0111B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135540375 http://47.92.197.167:5283/contest/447/problem/2 考虑部分分，枚举LCA 先单纯考虑一个点 iii 作为 xxx 祖先的概率。打表 / 推式子得 xxx 失无关变量。 我们现在预处理了期望深度 depidep_idepi​ 和期望祖先 fif_ifi​ 然后现在要努力列式子。 对于 xxx 要同时是 u,vu...

改变枚举顺序二分斜率时考虑斜率单调性来去掉log：0111A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135540204 <47.92.197.167:5283/contest/447/problem/1> 考虑区间dp，然后每个点维护下凸壳，转移时在凸壳上二分 这样子是带log的。考虑区间dp时改变枚举顺序，就可以满足斜率递增，不用二分了

观察性质 + 奇偶分类构造二分图+ 二分图匹配：0109C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135489832 http://cplusoj.com/d/senior/p/SS240109C 通过手模可知 f(a)+2C=f(a+2C)f(a) + 2C = f(a + 2C)f(a)+2C=f(a+2C) 于是这题很多时候要在模 2C2C2C 意义下讨论。 假设 iii 位置放 kkk ，则 2k−i+12k-i+12k−i+1 位置 k+c...

根号分治优化dp——暴力dp +类整数划分：0103C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135402981 http://47.92.197.167:5283/contest/441/problem/3 首先有个暴力dp。 f(i,j)f(i,j)f(i,j) 和为 iii ，末项为 jjj 。 看到这种和达到平方级别，比如初项和长度成反比的题目，应该要想到根号分治 我们随便分，比如初项 ≤B\le B≤B ，那 jjj 不超过 2B2B2B ...

min-max容斥 + 轮廓线dp：0103B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135381602 http://cplusoj.com/d/senior/p/SS240103B 网格图，其中一个 ≤6\le 6≤6 ，这是明显的轮廓线dp 然后 ppp 概率出事，于是期望 1p\frac 1 p p1​ 步到下一个状态这个结论很显然。（前提：剩下 1−p1-p1−p 是不动） 但这样子我们只能求第一个出事，不能求最后出事的 上面的形式就是：...

树剖+set（动态维护树上直径（形态不变，点权变））：0103A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135372558 http://cplusoj.com/d/senior/p/SS20240103A 显然可以点分树，然后被卡空间 任何一条树上的链都可以这样表示： 因此我们可以把所有轻儿子挂在重链上，然后求重链的最大子段和 因为我们要支持删除，同时树上每个节点要求连出去轻儿子中的最大，因此我们树上每个节点拿个set维护所有轻儿子 1234...

二分图+生成树构造：留下一条边：AT_arc119_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135341327 https://www.luogu.com.cn/problem/AT_arc119_d 首先，我们可以发现，同行和同列的红色格子会相互影响。因此我们可以考虑连边。这里我们容易想到两种连边方式： 红色格子之间连边。 位于 (i,j)(i,j)(i,j) 的红色格子，把第 iii 行和第 jjj 列连边。 考虑第一种连边方式。一...

reverse后差分循环同构：CF1045B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135333770 https://www.luogu.com.cn/problem/CF1045B 分析题目可得，一个 xxx 不能被凑出的充要条件是： ∀a∈A\forall a \in A∀a∈A ， ∃ a′∈A\exist\, a'\in A∃a′∈A ，满足： a+a′≡b(modM)a+a'\equiv b\pmod Ma+a′≡b...