中间相遇法（分治类问题非等大分治的平衡做法）
中间相遇法（分治类问题非等大分治的平衡做法）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321701
分治，如果分成两半大小不一样，很容易被卡到
在某些题目中，利用中间相遇法，我们可以优化这个过程
其优化的前提是分治的大头在找分界点
复杂度不用证，很好理解吧
这层找地越久，下一层就越均匀
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-26
分治常见Trick——启发式分裂+中间相遇法：CF1181E2
分治常见Trick——启发式分裂+中间相遇法：CF1181E2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133323437 https://www.luogu.com.cn/problem/CF1181E2 首先E1，也就是分治应该很好想 考虑到E2，首先看到题目是二维平面，有很多种分割方法，所以我们可以考虑拆维。 拆完之后我们考虑枚举分界点。枚举分界点暴力遍历过大，于是自然而然的，我们可以考虑中间相遇法。 但如果优雅的维护对应的集合呢？朴素思路使用s...
2023-09-23
具有部分单调性的区间个数计数问题——考虑分治：GZOI2023Day1T3
具有部分单调性的区间个数计数问题——考虑分治：GZOI2023Day1T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133218885 询问有多少区间满足 Sum×Len≤Max2Sum\times Len\le Max^2Sum×Len≤Max2 发现在 MaxMaxMax 定的情况下，显然满足单调性 对于此类题目，可以考虑分治处理 对于当前分治区间，我们采用的分治策略是左右独立算+计算跨区间 显然必然是一段后缀加一段前缀。 先枚举左端点，然后根据上...
2023-09-25
坐标系上的交互+分治与交互：CF788D
坐标系上的交互+分治与交互：CF788D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133281428 https://codeforces.com/contest/788/problem/D 坐标系上的交互有一种常见套路，就是抓住一些关键的线 x轴y轴 y=x（就是此题） 然后考虑接下来怎么做。 交互题常见有二分的套路，此题我们可以考虑推广到分治。 不断判断mid，然后就可以求出最近的范围，并递归下去即可 1234567891011121...
2023-09-26
启发式分裂
启发式分裂 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133321898 启发式分裂和启发式合并类似 对于一个数据结构，我们要对它进行分裂的时候，如果暴力拆成两个数据结构，很容易被卡 这个时候我们就可以考虑启发式分裂，把小的分出去，大的保留 在分治、set等题目中有广泛应用
2023-09-27
线性代数+分治：446E
线性代数+分治：446E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133336367 https://codeforces.com/problemset/problem/446/E 把官方题解翻译了一遍 考虑暴力，肯定想到dp，然后变成矩阵。设 用 代替 （这样子数之间的差值不会变化，但对于问题的处理能方便很多） 我们先令（也就是初始时的方案数） ，然后尝试构造转移矩阵 BBB BBB 的大小应该为 n×nn\times nn×n ，每个格子对...
2023-11-12
分治构造：P9384
分治构造：P9384 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134366235 https://www.luogu.com.cn/problem/P9384 分治构造是很常见的一种构造 不能有三元环和五元环，考虑推广出去，也就是不能有奇环 那如果我们让每种颜色都为二分图，那么必然满足 考虑 0-9 总共10个数字，数据范围1000，考虑 210>10002^{10}>1000210>1000 ，考虑 logloglog 级复杂度的做...