zhangxixi的博客

树的合并+类似树上差分的思路实现树上链加：P7897 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135034609 https://www.luogu.com.cn/problem/P7897 没说在线，果断离线。如果是朴素dp会有一个取max的过程，这里就是一棵子树若为正，我们才合并，采用这种思路来进行。 现在要维护的是新增子树，求子树大小。和子树有关的显然上dfs序。我们直接在挂的那个地方加，然后在当前树根节点在原树上父亲位置减即可，因为那个位置还没...

决策单调性 =＞ 二分队列：P3515 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135033351 https://www.luogu.com.cn/problem/P3515 pi=max⁡j=1n(aj+∣i−j∣)−aip_i=\max_{j=1}^n(a_j+\sqrt {|i-j|})-a_ipi​=maxj=1n​(aj​+∣i−j∣​)−ai​ ， ppp 之间独立，直接拆绝对值，到时候reverse再做一遍即可。 拆绝对值后，显然具有决...

背包+根号分治：loj6089 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135032303 https://loj.ac/p/6089 考虑根号分治，前面是个多重背包，直接分组部分和优化。 然后后面是个完全背包，直接做容易炸，但直接上整数划分dp即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...

区间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 就是个最小割 发现我们可能要割很多次，我们可以直接建分层图，在分层图上完成