zhangxixi的博客

图论（边次数限制）转流：P3163危桥 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135058446 https://www.luogu.com.cn/problem/P3163 考虑一条无向边 (u,v)(u,v)(u,v) 可走 www 次。 我们直接这样子转换 因此直接跑即可 但此题中如果我们直接源点练出去，汇点连出入，可能会算错： 如果都能流对应的流量，那么我们把 s2,t2s2,t2s2,t2 交换也可以，这显然是充要的。 因此跑两遍...

破环成链+运用特殊性质进行区间dp：AGC039E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135041477 https://www.luogu.com.cn/problem/AT_agc039_e 数据范围很小，考虑枚举很多东西。 看到环，首先肯定要破环成链，直接令 nnn 连出。考虑现在我们有一个 [1,n−1][1,n-1][1,n−1] 的区间，其中第 kkk 个点往外连了，为了确保联通， [1,k−1],[k+1,n−1][1,k-1],[...

李超线段树维护斜率dp：P4655 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135036474 https://www.luogu.com.cn/problem/P4655 这东西长得就很像斜率优化的东西，但是不能用朴素斜率优化，因为横坐标不满足递增。 但我们可以直接用李超线段树维护即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454...

树的合并+类似树上差分的思路实现树上链加：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时好像见到过一种可撤销背包。 使用条件： 计数类，非最优性问题 物品之间顺序无影响 因此我们直接撤销是对的