zhangxixi的博客

坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075877 https://vj.imken.moe/contest/598718#problem/J 观察到数据范围很小，但一个很重要的信息我们缺失了，就是珠宝的数量，所以我们考虑枚举珠宝的数量 kkk 。 对于横纵坐标什么至多至少的限制，比如 aia_iai​ 前最多偷 bib_ibi​ 个，可以转化为第 [bi+1,k][b_i+1,k]...

分数规划+费用流：LibreOJ - 2003 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075828 https://vj.imken.moe/contest/598718#problem/H 一坨分数的东西，显然二分，然后移一下项，可得 ci=ai−kbic_i=a_i-kb_ici​=ai​−kbi​ ，然后要选择一组最大匹配满足 ∑ci≥0\sum c_i\ge 0∑ci​≥0 根据霍尔定理必然存在匹配，所以我们直接跑费用流即可

离线ODT线段树 + 二分双指针：CF1034D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135071061 https://www.luogu.com.cn/problem/CF1034D 多组询问查询区间并是好做的，经典套路：离线+ODT+线段树 考虑这道题，显然二分一下， 然后我们暴力跑ODT和线段树的过程， 每次在线段树上二分即可（当然也可以建主席树），复杂度双log，听说过不了 但是显然具有单调性吧，所以two-pointers即可

上下界取min/max的线段树问题：P8518 [IOI2021] 分糖果 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135070831 https://www.luogu.com.cn/problem/P8518 没有要求在线，显然离线（。维护时间戳，上线段树。 好了，我们现在知道一个人的曲线变化了。怎么做呢？ 前面所有碰上下界的都是没用的！我们只需要找最后一段的时间段满足差值为 cic_ici​ 即可。因为差值更大的我们显然可以最后又会规约成这种情况...

有顺序多匹配的网络流——每个人已经不一样了：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 一个点要确定一个取值，然后每个取值还有代价，我们就拆成一条链： 源汇点就可以连对应代价的差分 然后题目肯定有某些一堆限制，关于某两条链的取值有什么限制，我们就可以在链之间连很多很多无穷的边来解决，比如： 这就代表如果第一条链 ≥...