zhangxixi的博客

有顺序多匹配的网络流——每个人已经不一样了：P2053 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135070777 https://vj.imken.moe/contest/598718#problem/G 每个人可以修多辆车，但我们要想成，修第二辆车时，这个人已经不是原先那个人了。 所以对于每个师傅，拆成修倒数第一个、倒数第二个时的他，然后跑费用流 即可。

分析性质+上下界网络流：CodeForces - 1416F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135069614 https://vj.imken.moe/contest/598718#problem/E 分析一波性质，一个位置旁边有比他小的那没问题，如果没有只能找朋友了。 找朋友，也就是形成环，由于每次只能上下左右，所以必然是个偶环。我们直接全部拆成二元环，因为一定可以拆。二元环，就可以匹配了。 但有些点可能旁边有比他小，但他也要拿去匹配，但...

最小割树：loj2042 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135069486 通过对最小割建树，实现快速查询图上两点间的最小割 既然是树，就采用建分治树的思想。假设当前分治点集为 SSS ，我们任取两点 u,v∈Su,v\in Su,v∈S ，然后求出他们在 原图 上的最小割。此时会被划分是两个点集 U,VU,VU,V ，它们就是新的分治点集了。我们在树上连的边就为当前最小割。 然后我们查询两点在原图上的最小割，只需要查询树上路径的最大值即可。...

约束条件转保序回归问题——之间用贪心+单调栈维护：P7294 / 1218T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135067510 https://www.luogu.com.cn/problem/P7294 http://47.92.197.167:5283/contest/439/problem/3 发现行很大，那肯定是一列列枚举。 考虑单个询问 (x,y)(x,y)(x,y) ，假设第 iii 列向第 i+1i+1i+1 列的转折点是 p...

逆序对排列计数 & 行列式：1218T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135065670 http://47.92.197.167:5283/contest/439/problem/1 显然可以拆维，然后满足每一维是排列，然后逆序对奇偶会对答案有±1的贡献。然后分别算概率再乘起来。 接下来两个思考方向： 顺着思考 两个取值都在红色范围，显然可以交换，然后逆序对奇偶正好取反，贡献为0。因此就从左到右，强制钦定每个区间的取值必须是它...

把状态拆成长链来跑网络流（转化为最小割）：LibreOJ - 2384 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135058691 https://vj.imken.moe/contest/598718#problem/C 一个点要确定一个取值，然后每个取值还有代价，我们就拆成一条链： 源汇点就可以连对应代价的差分 然后题目肯定有某些一堆限制，关于某两条链的取值有什么限制，我们就可以在链之间连很多很多无穷的边来解决，比如： 这就代表如果第一条链 ≥...

图论（边次数限制）转流：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序。我们直接在挂的那个地方加，然后在当前树根节点在原树上父亲位置减即可，因为那个位置还没...