zhangxixi的博客

势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093792 https://www.luogu.com.cn/problem/P7446 https://www.luogu.com.cn/problem/CF1491H 看到题，发现只有减，就和势能有关。维护势能，像这种题，树形ds显然不好做，所以可以去考虑进行分块。 考虑分块。每个块记录一个 bib_ibi​ ， iii 的...

考虑全选然后删的代价转最小割+最小割同一类连inf的边：AT_arc107_f 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093630 https://www.luogu.com.cn/problem/AT_arc107_f 理论上界为 ∑∣bi∣\sum |b_i|∑∣bi​∣ 。考虑现在减少会有什么情况： 不选。代价为 ai+∣bi∣a_i+|b_i|ai​+∣bi​∣ 原先为正，所在连通块取绝对值后变负。代价为 −2∣bi∣-2|b_...

数学方法转化限制条件（使大于小于等于号左右互为相反数，变成绝对值）+加减交错法构造博弈论下界推出最优解再用限制代入：AT_agc056_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135089890 https://vj.imken.moe/contest/600552#problem/G 考虑对题目进行转化 L≤Sa≤RL \le S_a \le RL≤Sa​≤R 2L≤2Sa≤2R2L\le 2S_a \le 2R2L≤2Sa​≤2R 2L+Sb≤...

阴阳反转——运用INF巧妙建网络流：P3980 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080814 https://vj.imken.moe/contest/598718#problem/L 考虑一个奇妙的转化： 有很多 inf⁡\infinf 个人要走 nnn 扇门，第 iii 扇只能走 inf⁡a−i\inf_a-iinfa​−i 个人，有 mmm 个通道，可以把一个人从 sis_isi​ 运到 ti+1t_i+1ti​+1 ，但要给 c...

通过费用流中的贪心来保证计数正确性：P4249剪刀石头布 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080431 https://vj.imken.moe/contest/598718#problem/K 三元环数量尽量多，也就是非三元环数量尽可能少。非三元环的充要条件是存在一个点度数为2，而每条边可以给一个点一个度数，然后就变成了经典网络流问题。 但是，对于一个点，我们还是无法求最少流。考虑转化为费用流。一个点向汇点连很多条边，分别代表着度数为1...

插入数计数类 / 转为换行类dp：AT_agc024_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135078944 https://www.luogu.com.cn/problem/AT_agc024_e 首先题目可以转化成每次插入一个数，满足字典序递增。 如果只考虑暴力dfs，先别上dp，想想怎么合法和不算重。 合法，也就是插入数有3种情况 插到末尾 插到比他小的前 插到和它相等的数，然后后面退了一位后刚好满足 前2种是好做的，但如...

坐标前后限制转点的坐标取值+网络流拆维拆点：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​ 即可。因为差值更大的我们显然可以最后又会规约成这种情况...