zhangxixi的博客

根号分治优化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...

Hall定理证明可行性来贪心 + 模拟断流与增流： CF1009G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135333029 https://www.luogu.com.cn/problem/CF1009G 显然是流，然后贪心，然后要每次流一下证明可行性，这里提供两种解决方法： Hall定理 左边点数只有6，我们直接 262^626 跑Hall定理 模拟断流 用EK实现网络流。我们直接少流当前位置的。显然一条流最多经过14个点，因此复杂度是对的。 H...

随机类问题解法——利用统计学：1229B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135332294 http://47.92.197.167:5283/contest/440/problem/2 结论： nnn 个随机 [0,1][0,1][0,1] 变量的期望最小值为 1n+1\frac 1 {n+1} n+11​ 因此我们以输入的数为随机种子生成随机数。相同的种子生成的数是一样的，所以相当于有 mmm （不同数）个数的随机数。我们取最小值即可...

闵可夫斯基和 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329408 几何上可以理解为B沿着A一周覆盖的图形。也可以是B偏移和A交的向量。 对两个凸包归并

反向贪心决定博弈+博弈论中条件改变人的决策满足单调性：1229A 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135329131 http://cplusoj.com/d/senior/p/SS231229A 结论： 人们倒着来，每个人去掉当前对自己最不利的 因此我们有了 O(n3)O(n^3)O(n3) 考虑当一个人变了后，每个人的决策必然满足单调性，因此就可以平方了 12start coding at 20:19passing at 21:18 123...

12.29听课笔记 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135297427 A 1，n个0，n个1 B -1 放最小 +1 放最大 C 假如根定，可以直接dp 打表得只要根是叶子，答案取最小 直接暴摊也是对的 D 假如定根， DPuDP_uDPu​ 内部分辨要多少个点。则 DPu=∑DPv−[存在一个儿子为叶子且分支>1]DP_u=\sum DP_v-[存在一个儿子为叶子且分支>1]DPu​=∑DPv​−[存在一个儿子为叶子且分支&...