MiQiu

[L4] 并查集 本篇是并查集的理论部分，只负责回答“并查集是什么、什么时候用、为什么能用、基础代码怎么写”。 具体题型、完整模板和例题放在 并查集题型整理。 学习顺序按下面这条线走： 概念 →\to→ 地位 →\to→ 用途 →\to→ 核心原理 →\to→ 代码实现 1. 概念：并查集是什么 并查集是一种用来维护若干个互不相交集合的数据结构。 它关心的不是集合内部每个点怎么排列，而是每个点

[L4] 倍增策略 1. 生态位 倍增 是基于二进制拆解的策略 —— 任何正整数都可唯一分解为若干个 2k2^k2k 之和。 地位：分解问题的一种思维方式。 用途：用于解决 RMQ 问题的 ST 表，以及树上倍增 LCA 和 后缀数组 SA 等高级数据结构的基础。 识别： 静态区间查询：数组内容不发生修改。 幂等律：维护的信息满足 f(a,a)=af( a, a ) = a

CF2193F - Pizza Delivery 1. 题面梗概 快递员从 (Ax,Ay)(Ax, Ay)(Ax,Ay) 出发，要去 nnn 个点送外卖，最后回到 (Bx,By)(Bx, By)(Bx,By)。移动规则：只能往右 (x+1)(x+1)(x+1)、往上 (y+1)(y+1)(y+1) 或往下 (y−1)(y-1)(y−1) 走。 求完成所有任务的最短时间。 2. 逻辑推导 我们从移动

F - Diagonal Separation 2 1. 题面梗概 给你一个 N×NN \times NN×N 的网格。你要给它重新染色，使得它满足两个条件： 行约束: 每一行必须是“左边全是白，右边全是黑”。 列约束: 每一列必须是“上边全是白，下边全是黑”。 问：最少需要改动多少个格子的颜色？ 2. 逻辑推导 2.1 分析 从行约束入手，设第 iii 行分界点为 kik_iki​，

E - Laser Takahashi 1. 题面梗概 高桥站在原点 (0,0)(0,0)(0,0)，每一次可以发出一道激光，干掉在同一条射线上的所有怪兽。 给你 NNN 个怪兽的坐标。有 QQQ 个独立询问，每次给你两个怪兽 AAA 和 BBB。高桥先盯着 AAA，然后顺时针转头，直到盯着 BBB 为止。 问这期间一共消灭了多少只怪兽？ 2. 逻辑推导 2.1 分析 第一反应：看到顺时针旋转 +

ZJ2022I - Barbecue 1. 题面梗概 Putata 和 Budada 玩一个撕纸条的游戏。纸条上有个字符串，轮到你时，你必须从开头或结尾撕掉一个字符，然后传给对方。 谁手上的纸条变成回文串，谁就输（撕之前撕之后都一样，只要纸条在你手中变成了回文，就输）。 现给你一个长字符串和 QQQ 次询问，每次询问游戏纸条字符串 [Sl,Sr][S_l, S_r][Sl​,Sr​]，问谁赢。 2

ZJ2022M - BpbBppbpBB 1. 题面梗概 中译中: 在地图中寻找有几个 CCC type，几个 SSS type。 2. 逻辑推导 这题的难点在于，图形可能会"黏连"，所以直接数连通块大概率会导致结果偏少。 既然形状是完全固定的，那每一个 子图 贡献的 黑色像素点总面积 和 内部空洞总个数 都是固定的，我们可以列出下面这个二元一次方程组。 {2C+S=Hole

ZJ2022L - Candy Machine 1. 题面梗概 给定 NNN 个糖果，第 iii 个糖果甜度为 aia_iai​，可以取任意子集的糖果。限制条件是，选取完某个糖果子集 SSS 后，设平均甜度为 XXX，所有甜度 严格大于 XXX 的糖果可以得到。问：最多可以获得多少糖果。 2. 逻辑推导 2.1 切入点 切入点是这个：“平均甜度 XXX”，如果我们想取得更多的糖果，那么最简单的想法