zhangxixi的博客

区间dp（刷表法转移）：P5336 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028996 https://www.luogu.com.cn/problem/P5336 离散化后枚举 g(l,r,mn,mx)g(l,r,mn,mx)g(l,r,mn,mx) ，和 f(l,r)f(l,r)f(l,r) （全删情况），然后考虑使用刷表法来转移。 ar+1a_{r+1}ar+1​ 加进来，更新 mn,mxmn,mxmn,mx 即可 不加进来，停表...

妙妙区间dp（从大往小，计算小对大的贡献（2^n的区间dp））AGC035D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028688 https://www.luogu.com.cn/problem/AT_agc035_d 设 f(l,r,fl,fr)f(l,r,fl,fr)f(l,r,fl,fr) 表示现在在区间 [l,r][l,r][l,r] ， al−1+1a_{l-1}+1al−1​+1 对答案贡献为 flflfl ， frfrfr 同理。...

容量很大体积很小背包 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028489 在 https://blog.csdn.net/zhangtingxiqwq/article/details/132216843 提到过关于容量很大体积很小的背包问题，现在简要梳理一下： 先贪心选 选了的就上可删除dp，没选的就是朴素dp，把dp范围控制在 [L−m,L+m][L-m,L+m][L−m,L+m] 以内 加入过程直接二进制分组优化

可删除背包（计数类）： P4141 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028419 https://www.luogu.com.cn/problem/P4141 看完第一眼想到打分治，然后记得以前打abc时好像见到过一种可撤销背包。 使用条件： 计数类，非最优性问题 物品之间顺序无影响 因此我们直接撤销是对的

信息合并类+ST表：CF1707E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134982534 https://www.luogu.com.cn/problem/CF1707E f([l1,r1]∪[l2,r2])=f(l1,r1)∪f(l2,r2)f([l_1,r_1]\cup [l_2,r_2])=f(l_1,r_1)\cup f(l_2,r_2)f([l1​,r1​]∪[l2​,r2​])=f(l1​,r1​)∪f(l2​,r2​) f([l1,...

普通环的构造计数——计数链，然后合成：1211T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134929628 http://47.92.197.167:5283/contest/437/problem/3 我们要构造环，肯定要构造链，然后题目还和我们说了是个二分图，我们就让链的端点在同一边（假定在右边） 那样考虑左边每个点又什么用？很显然，粘！可以把两条链粘一起，或者把链变成环。 所有很明显了，我们直接dp。 f(i,j)f(i,j)f(i,j) 表...

1211T2：分层图跑最小割（要割几次的最小割） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134926699 http://47.92.197.167:5283/contest/437/problem/2 k=1k=1k=1 就是个最小割 发现我们可能要割很多次，我们可以直接建分层图，在分层图上完成

二分+dp：[ARC120E] 1D Party 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134754875 https://www.luogu.com.cn/problem/AT_arc120_e 考虑二分时间，然后设 dp(i,0)dp(i,0)dp(i,0) 表示第 iii 个人开头往左走，掉头后剩余步数。 dp(i,1)dp(i,1)dp(i,1) 表示第 iii 个人先往右走，最多走多少步就有掉头。 然后在纸上画一画就是小学的相遇问题，直接转...

每个点取值拆成多个点的最小割问题：CF1430G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134751924 https://vj.imken.moe/contest/597216#problem/I 题目等价于求 min⁡∑uau(outu−inu)\min \sum_{u}a_u(out_u-in_u)min∑u​au​(outu​−inu​) 发现每个数的取值范围最多到 nnn ，然后又有一堆限制，考虑拆点+网络流。 每个点拆成 n+2n+2n+...

最小割构造 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134750195 考虑跑完最大流，我们再从源点跑一遍bfs，所以能跑到的点都属于点集A，否则属于点集B