个人著作权声明：严禁任何未经本人（刘承奥，常用笔名/网名：蔡德仁 CommonAnts LCA liu_cheng_ao）书面授权者在梦熊联盟，或者任何虚假宣传或不实营销炒作或不正当竞争行为严重的 OI 机构的课程内或交流平台（包括但不限于品牌集训线下讨论，交流群，OJ，公众号，视频号等）上引用、传播、讨论此内容，以及本人于2024年5月及之后发布的所有内容，包括声明为公开的内容在内。
本文在 LibreOJ 最快更新！
所谓 「思考题研讨」，是一种在大学中亦有记载的算法学习方式。每个思考题是一系列相关的具体算法数学问题，围绕一个技巧/数学概念/动机等小套路展开，用于补足编程题不能表达的内容。毕竟编程题只能表达编程内容。每个思考题应当包括至少一道 OI 题或一个经典数学概念。
思考题的通常用法是几个同学小组讨论做法，之后再讲解或者看题解。当然，如果没有同学的话单人学习也是可以的。
同学们偶尔想到的那些不太实用/偏/怪/卡常/重复造轮子的灵感非常适合造思考题研讨！
笔者这一年来（截至 2025 年 11 月）协同助教和网友已经造了思考题 80 余道。以下展示一些笔者认为较为不错的思考题作为例子，欢迎大家讨论！
笔者造的和征集的思考题中优质的都会在之后的教材编写、公开资源推荐等中陆续公开。也欢迎各位投稿的同学自行公开传播自己造的思考题。
目前只造了 NOIP+ 和 NOI 难度的思考题，不过该形式在入门和普及学习简单编程基础和数学知识也是有用的，欢迎各位集思广益。
有奖征集思考题：【欢迎投稿】有奖征集 OI 小知识点，技巧和思考题，包括“广为人知”但大纲未收录的内容！
思考题题例（题解之后公布）
- 以下例题中题号 AP 是面向 NOIP+ 难度；题号 A 是面向 NOI 难度。注意因为思考题默认是要多人研讨的，会比同阶段 OJ 题更难。
- [bonus] 是开放性或者困难的问题，给水平特别高的同学进阶讨论。
A101 大鱼吃小鱼
有一排 $n$ 条鱼，每条鱼有一个体型值（正整数）$a_i$，一条鱼可以吃掉相邻的鱼，如果被吃的鱼体型小于等于自己。吃完后自己的体型会加上被吃的鱼的体型。鱼之间位置的先后顺序不变。
问题1. [ARC189D]每条鱼最多可以吃到多大的体型？
问题2. [P9530]单点修改 $a_i$，区间查询 $[l,r]$ 内有多少条鱼可以吃完区间内其它所有鱼。（只有这个问题有修改和查询）
问题3. 如果我们有一种道具，鱼每用一次道具可以吃掉任意一条相邻的鱼，无视体型，请你对于每条鱼求出，它吃完所有其它鱼最少需要多少个道具。
问题4. 如果我们把吃鱼的规则改为只能吃右边（编号更大）和自己相邻的鱼（道具不受影响），问题2和3的结果会有什么变化？（你不能先操控别的鱼吃鱼，再用道具吃它）
问题5. 如果我们允许小鱼吃大鱼，也就是定义常数 $k(k\ge 0)$，将题目条件改为“一条鱼可以吃掉相邻的鱼，如果被吃的鱼体型小于等于自己的体型加 $k$”，问题3的结果会有什么变化？
问题6 [JS2024/U477940]：如果我们去掉问题5中 $(k\ge 0)$ 的限制，问题5的结果会有什么变化？
问题7. 如果我们把问题5和6中的条件从差值改成比例，也就是定义常数 $c(c\gt 0)$，将题目条件改为“一条鱼可以吃掉相邻的鱼，如果被吃的鱼体型小于等于自己的体型乘 $c$”，问题5和6的结果会有什么变化？
问题8.[bonus] 尝试找到一个有意思的问题并改编一个 OI 题目。例如：如果我们把鱼放到树上，定义每条鱼占据一个树上连通块，两条鱼相邻当且仅当占据的连通块相邻，初始每条鱼占据一个点，被吃的鱼的连通块会被吃它的鱼占据，会发生什么？
A102 循环博弈
有 $n$ 个人在玩游戏，有一堆初始总数为 $m$ 的石子，从第 $1$ 个人开始轮流取（第 $n$ 个人后再次轮到第 $1$ 个），每次每个人需要拿走至少 $1$ 个至多 $k$ 个石子。如果轮到一个人时石子没有了，游戏结束。定义游戏的结果为游戏结束时轮到的人的编号。
现在有一个 $n$ 行 $n$ 列的矩阵 $A$，其中 $A_{i,j}$ 表示如果游戏结果为 $i$，第 $j$ 个人会获得 $A_{i,j}$ 的收益。保证 $A$ 每一列的元素互不相等，不妨设 $A$ 的每一列都是 $1$ 到 $n$ 的排列。
每个人都想最大化自己在游戏结束后的收益，他们也知道所有人都这么想。
问题1. 讨论里所有人都最大化自己的收益在实际游戏中会怎么决策，说明每个人有确定的决策。
（并不是所有博弈都有符合直觉的确定的最优策略。例如，在一些多人游戏中经常发生某个人已经必败了但他可以选择其它人谁赢。这时你不能仅凭每个人都最大化自己收益来确定他的选择。想想这个题为什么没有类似情况。）
问题2. 给出一个关于 $n,m,k$ 的多项式时间的算法求出最优策略。
定义 $f(x,y)$ 表示轮到第 $x$ 个人且石子还剩 $y$ 个时，所有人都采取最优策略的情况下游戏的结果。
问题3. 证明 $f$ 关于石子个数存在周期。换言之，存在正整数 $T$ 使得不满足 $f(x,y)=f(x,y+T)$ 的正整数 $(x,y)$ 只有有限多对。
问题4. 考察 $n\le 3$ 时 $f$ 的情况。例如考虑：不满足周期的最大数对的上界是多少？最小正周期的上界是多少？如何构造？$f(1,\cdot)$ 和 $f(2,\cdot)$ 两列值有什么关系？（将 $k$ 视为参数）
在此基础上提出一个尽可能高效的算法计算 $n\le 3$ 时的这个问题。
问题5. 现在取消对 $n$ 的限制，考察 $f$ 的最小正周期和非周期部分的上界，并给出使之渐进尽量大的构造。（将 $n,k$ 视为参数）
这个问题比较困难，所以我们给出一些提示。另外，不要忘记打表观察也是一种方法。
混循环数列不容易处理，我们考虑纯循环，也就是说，令 $g(x,y)$ 是一个函数对任意整数 $y$ 和 $1\le x\le n$ 都满足 $g(x,y)=g(x,y+T)$ 且存在 $M$ 使得 $\forall y \gt M, g(x,y)=f(x,y)$。研究 $g$ 也可以得到循环节的性质。
例如：记 $g_x$ 表示数列，$g_x[y]=g(x,y)$（下标 $y$ 是包括负数在内的全体整数）。考虑：
问题5.1. $g_x$ 和 $g_{(x \bmod n)+1}$ 两个数列之间有什么递推关系？
问题5.2. 根据 5.1 的递推关系，如何直观刻画 $g_x$ 更方便？
问题5.3. 我们不妨设 5.1 的递推关系为 $g_x=P(g_{(x \bmod n)+1})$，那么我们知道 $P^n(g_x)=g_x$，也就是 $P^n=I$ 作用是保持不变，尝试通过 $P^n$ 的这一性质来研究周期的性质。
问题5.4. 我们不妨设原本的序列也有规则相同（但定义域不同）的递推 $f_x=P(f_{(x \bmod n)+1})$，尝试通过 $P$ 反复迭代过程中 $f$ 的变化过程研究非周期部分的上界。
问题6. 找到原问题的一个真正的多项式时间算法，也就是关于输入长度的多项式，即使 $m,k$ 是高精度的。给出你算法的时间复杂度上界。
问题7.[bonus] 研究这个问题的一些特殊情况或拓展情况，并尝试出题。例如：如果我们规定矩阵 $A$ 的值是 $A_{i,j}=(i+j-2)\bmod n+1$ 会发生什么？如果 $k=\infty$ 会发生什么？如果 $A$ 的一列内有多个相同数字，会对最优策略的概念产生什么影响？
A103 全局平衡
你有 $n$ 个数 $a_1,a_2,\dots ,a_n$。现在你要构造出一棵 $n$ 个叶子的有根二叉树，把这些数分别填入每个叶子。定义一个叶子走到根的代价等于它填的数加上到根距离。（树没有边权）
你希望让所有叶子走到根的最大代价尽可能小，并求出这个最小值。
问题1. 假如这些数是 $n/x$ 个 $x$ 和 $n-n/x$ 个 $1$（$x$ 是一个参数），你能求出问题答案大致的大小吗？
问题2. 输入这 $n$ 个数，请你设计算法并写一个程序求解这个问题。
问题3.
我们知道在二叉搜索树（有根有序二叉树）上，每个子树对应中序遍历的一个区间。
现在，你有 $n$ 个点和 $m$ 个区间约束 $[l_i,r_i],1\le l_i\le r_i\le n$。你要构造一个二叉搜索树，使得在树的中序遍历上，每个约束区间 $[l_i,r_i]$ 都恰好对应某一棵子树里的所有点。
问题3.1：输入 $m$ 个区间，输出是否存在这样的二叉搜索树。
问题3.2：输入 $m$ 个区间，构造一棵深度尽量小的满足条件的二叉搜索树。
问题4.
我们知道在一些数据结构问题中，经常出现这么一种“树套树”的情况：我们有很多个二叉搜索树，当我们查找到上层的二叉搜索树的叶子时，我们需要转到这个叶子关联的下层二叉搜索树，继续递归查找。或者反过来，从一个叶子不断向上跳，当跳到根时，根可能关联了一个上层二叉搜索树的叶子，我们需要转到那个叶子继续向上跳。
例如，在树链剖分中，如果我们给每个链开一个二叉查找树维护链上的所有点，查询一个点在原树上到根路径的过程就可以描述为不断在当前链对应的二叉搜索树上向上跳，到搜索树根之后再跳到当前链的链顶在原树上的父节点。这个点属于另一条链，然后我们继续在它的链搜索树上往上跳。循环往复直到跳到原树根节点所在的链的搜索树根。
现在给定一个有根树的树链剖分方式，所有 $n$ 个树上的点被分成若干个祖先到子孙方向的链。请你找出一种二叉查找树形状的设置方法，使得在最坏情况下查询一个点在原树上到根路径的过程向上跳的步数尽可能少。你可以以此分析一下，假如树链剖分方式分别采用重链剖分和长链剖分，跳的步数复杂度是多少？
（在重链剖分时，这个算法在OI中被称为“全局平衡二叉树”）
问题5.
现在我们看这样一个问题：
你和小明玩猜数游戏。有一张纸上面写了一些实数（设为数集 $S$）。一开始，小明选一个在集合 $S$ 里的数记在心里。然后每次你可以做两种询问： - 询问一个整数 $x$，小明回答他的数和 $x$ 的大小关系。 - 询问一个实数 $x$，小明回答他的数是否等于 $x$。
请你设计一个足够优的策略使得最坏情况下询问次数尽可能少（渐进足够少即可），找出你表示这个询问次数需要从 $S$ 中提取的关键信息/参数。并且给出最坏情况下询问次数的估计。
问题6.
在问题5的基础上，你和小明从猜数升级到了猜点。
有一个平面上的点集 $S$（不妨设为用两维实数坐标表示）。
一开始，小明选一个在集合 $S$ 里的点记在心里。然后每次你可以做两种询问： - 询问一个网格直线 $x$，小明回答他的数在直线 $x$ 的哪一侧，或者恰好在直线上。（指水平或垂直且坐标为整数的直线） - 询问一个任意直线 $x$，小明回答他的点是否在这条直线上。
请你设计一个足够优的策略使得最坏情况下询问次数尽可能少（渐进足够少即可），找出你表示这个询问次数需要从 $S$ 中提取的关键信息/参数。并且给出最坏情况下询问次数的估计。当然，这个问题可以对两维分别做一次问题5，你能做到更优吗？
A032 中位数和第 k 小
（本问题中的中位数，在数字个数为偶数 $n$ 时指从小到大排名第 $\lceil n/2\rceil$ 的数，类似概念均如此取整，以保证中位数一定在输入之中。否则对于字符串之类可以排序但不能平均的对象无法定义中位数。）
问题1. 小明得到了一个程序，它可以输入一个长为 $n$ 的数组，然后在 $O(n)$ 时间内计算出这个数组内中位数的下标并返回。小明可以任意次调用这个程序，现在他想设计一个算法，输入 $n$ 个数和整数 $k$，在 $O(n)$ 时间内输出其中从小到大排第 $k$ 小的数，能做到吗？
如果把计算中位数改成随机取一个数，会对你的程序效率产生什么影响？是否存在一个特定输入总能“卡掉”该算法？
问题2. 小明构思了两个程序，程序1输入一个长为 $n$ 的数组，然后在 $O(n)$ 时间内计算出这个数组内中位数的下标。程序2输入一个长为 $n$ 的数组，在 $O(n)$ 时间内输出其中从小到大排第 $\lceil rn\rceil$ 小的数的下标，其中常数 $r$ 是一个区间 $(0,1)$ 内的固定的比例参数。
如果小明已经有了程序1，如何利用程序1设计出程序2？
如果小明已经有了程序2，如何利用程序2设计出程序1？
你的办法的时间的常数系数和 $r$ 有什么关系？
问题3. 小明突发奇想，他把 $n$（$n$ 很大）个数分成了 $n/999$ 组，每组 $999$ 个数。然后他计算出了每组内部的中位数（这可以在 $O(n)$ 时间内暴力完成，毕竟 $999$ 只是个常数），又计算出了这 $n/999$ 个中位数 $m_1,m_2,\dots ,m_{n/999}$ 的中位数 $M$。请问这个“中位数的中位数”$M$ 在最开始的数组中最大和最小的排名范围大致是多少？（不必考虑多个数相等的情况，可以认为是取了更优的一个）
如果“计算 $n/999$ 个数的中位数”这一步递归计算，时间复杂度是多少？（提示：为了可以递归，不妨把整个问题理解为求第 $k$ 小，而不只是中位数）
问题4. [median of medians] 根据问题3设计一个在最坏情况下渐进复杂度低的中位数算法，并思考有多个输入数相等时的运行情况。当然，这可以用于问题1和问题2。
问题5. 现在你有 $n$ 个，每个长为 $m$ 的递增序列，你想要选出所有序列合在一起的第 $m$ 小元素。请你给出一个时间复杂度尽可能小的做法。（不考虑读入时间。）
问题6. 请你解决 https://uoj.ac/contest/91/problem/891
问题7.[bonus] 你有一个 $n\times n$ 的递增矩阵（$a[i][j]\lt a[i+1][j]$ 且 $a[i][j]\lt a[i][j+1]$），你想要选出矩阵的第 $n$ 小元素。请你给出一个时间复杂度尽可能小的做法。（不考虑读入时间。）
拓展阅读.[bonus] https://www.cnblogs.com/zkyJuruo/p/18428124
A029 无删除双指针
你在一个 $n\times n$ 的网格上，初始在左上角 $(1,1)$，设 $(x,y)$ 表示从上往下第 $x$ 行从左往右第 $y$ 列的格子。这个网格中每个格子都是黑白两种颜色之一，并且白格的左、上方都是白格，黑格的右、下方都是黑格。你可以且只能看到你当前所在的格子的颜色（当然你可以思考和记录之前看到的东西）。你想搞清楚整个网格每个格子的颜色。
问题1.1. 如果你可以向四个方向的相邻格走，请你给出一个步数上界尽可能少的算法。
问题1.2. 如果你只能向左右下三个方向的相邻格走，请你给出一个步数上界尽可能少的算法。
问题1.3. 现在网格的地面倾斜了，左上方高右下方低。因此，你只能向右或者向下的相邻格走。当然只有这样是不可能探索整个网格的。所以你拿来了一条绳子，它被固定在你经过的每个格子里，这样，你就可以顺着绳子攀爬，收回最后一格绳子同时返回绳子的上一格。（也就是说任何时候绳子都是一条从 $(1,1)$ 沿着你之前走的路径向右向下到达你当前位置的折线）
问：如果你想要到达对角线（$x+y=n$）上的每个格子 $(x,y)$ 一次，总共至少要走多少步？
问题1.4. 在上一问的基础上，现在保证网格只有对角线附近未知，$(x,y)$ 所有满足 $x+y\le n-10$ 的都是白格，所有满足 $x+y\ge n+10$ 的都是黑格。请你给出一个步数上界尽可能少的算法。把 $10$ 改为 $k$（仍然保证 $k$ 远小于 $n$），估计步数。
问题1.5. 在上一问的基础上，取消对角线的保证，请你给出一个步数上界尽可能少的算法。
问题2. [baka's trick]你有一排 $n$ 个物品和常数 $W,V$，第 $i$ 个物品的重量为 $w_i$，权值为 $v_i$。称一个下标区间是合法的当且仅当区间内可以选出一个总重量 $\le W$ 且总权值 $\ge V$ 的子集。容易证明如果一个区间合法则包含它的区间都合法，请你求所有极小的合法区间。$1\le n\le 10^4,1\le w_i,W\le 10^4,1\le v_i,V\le 10^9$
问题3. 有 $n$ 个点 $m$ 条边的无向图，点编号 $1\dots n$，边编号 $1\dots m$。请你求出所有极大无环区间，无环区间的定义是只考虑编号在该区间内的边不会形成环。（不要使用 LCT 乃至动态图连通性等复杂数据结构直接维护。）
问题4. 请你解决 https://uoj.ac/problem/693
A027 数对/图的zig-zag构造
问题1. 构造一个 $n$ 阶排列，使得每一对相邻数的差恰好取遍 $1,2,\dots ,n-1$。
有一个 $n$ 个点的有向完全图 $G$，它的边有 $n(n-1)$ 条。在很多构造问题中，我们需要做这样一件事：把这 $n(n-1)$ 条边分成 $n$ 个大小为 $n-1$ 的集合，且每个集合的结构都相同，且足够简单。
一个自然的想法是，先找一个边集 $E$，使得 $n$ 个集合恰好是这个边集的旋转。具体定义如下：
把图中所有点标号为 $0,1,\dots ,n-1$。我们对于边集 $E$ 和整数 $x$ 定义加法：$E+x=\{(u+x\pmod n,v+x \pmod n):\forall(u,v)\in E\}$。也就相当于把图中的 $n$ 个点排成一圈并旋转这个边集。
问题2. 如果一个边集 $E$ 满足 $E+0,E+1,\dots ,E+n-1$ 恰好不重不漏地划分了图里的所有边，$E$ 的性质是什么？（充要条件？）
问题3. 最简单，性质最好的大小为 $n-1$ 的边集应该是哈密顿路径。构造一个满足上述条件的边集 $E$ 使得 $E$ 中的边组成一条有向哈密顿路径。
无向图也有类似的构造。有一个 $n$ 个点的无向完全图 $G$，它的边有 $\frac{n(n-1)}{2}$ 条。在很多构造问题中，我们需要做这样一件事：把这 $n(n-1)$ 条边根据 $n$ 的奇偶性分成 $n$ 个大小为 $\frac{n-1}{2}$ 的集合或者 $n-1$ 个大小为 $\frac{n}{2}$ 的集合，且每个集合的结构都相同，且足够简单。
问题4.1. 最简单，性质最好的大小为 $\frac{n-1}{2}$ 或者 $\frac{n}{2}$ 的无向边集应该是最大匹配。当 $n$ 为奇数时，构造一个边集 $E$ 满足 $E+0,E+1,\dots ,E+n-1$ 恰好不重不漏地划分了图里的所有边，使得 $E$ 是最大匹配。
问题4.2 当 $n$ 为偶数时存在一个边集 $E$ 满足 $E+0,E+1,\dots ,E+n-1$ 恰好不重不漏地划分了图里的所有边，使得 $E$ 是最大匹配吗？如果不能，尝试微调“旋转”的定义使得我们仍能将所有边划分成一组性质良好的最大匹配。（可以结合下面的实际应用思考）
现在我们来看实际应用。注意，“二元组互不相等”形式的约束通常可以图论建模。
问题5. 【QOJ5528】给定一个无向完全图，请你将它的所有边排成一个序列使得这个序列中每相邻 $n-1$ 条边都形成一棵生成树。（实际上，可以排成环形序列。）
问题6. 【P9837】https://www.luogu.com.cn/problem/P9837
问题7. [CF2081F]构造一个 $2n\times 2n$ 的拉丁方（每一行、每一列都是 $2n$ 的排列）满足每一对关于整个矩阵水平或垂直平分线轴对称的位置和都为 $2n+1$ - $a[i][j] = a[2n-i+1][2n-j+1] = 2n+1 - a[2n-i+1][j] = 2n+1 - a[i][2n-j+1]$ - 横着看相邻两个位置组成的有序对（共有 $2n \times (2n-1)$ 个对）全都互不相同 - 竖着看的有序对也互不相同
问题8.[bonus] 这个模式[pattern]可以称为zig-zag。你是否能想到类似的问题和拓展？
更多例题. 【P5419】
A036 我放弃了均摊数据结构
问题1. 小明听说 std::vector 能够维护一个数组，支持在末尾添加、删除元素和随意访问任意下标的元素。为了随意（也称随机）访问，std::vector 将元素存储在一段连续的内存中。
但是，计算机每次只允许申请固定长度的连续内存。我们认为申请一段固定长度的连续内存，无论长度多少都是 $O(1)$ 的。（仅申请，后续修改另外算时间。）
因此 std::vector 的实现方式是，有一个容量值 $C$，添加新元素时一旦超出容量，就将 $C$ 变为原来的 $2$ 倍，申请一段新的长为 $C$ 的内存，并把原来的元素复制过去，释放原来的内存。这个步骤称为重构。
小明想到了几个问题：
问题1.1. 证明 std::vector 在 $n$ 次操作的总时间复杂度是 $O(n)$ 的。
问题1.2. 小明发现如果添加很多元素之后删掉大部分元素，vector 内的的元素个数会远远小于容量，这很浪费内存。因此小明希望在元素太少时也重构，使得 $C$ 总是不超过当前元素个数的渐进线性。
小明仿照上述方法，规定在元素个数小于 $1/2 C$ 的时候就将 $C$ 变为原来的 $1/2$，申请一段新的长为 $C$ 的内存，并把原来的元素复制过去，释放原来的内存。
这种情况下，小明的 vector 在 $n$ 次操作的总时间复杂度是多少？
问题1.3. 做一些修改，实现问题1.2.中小明的想法，并且保证 $n$ 次操作的总时间复杂度是 $O(n)$ 的。
问题1.4. 小明发现虽然 $n$ 次操作的总时间复杂度是 $O(n)$ 的，但单次操作消耗的最大时间也是 $O(n)$ 的。小明希望减小单次操作的时间上界。有什么办法做到这一点吗？
提示：能否把重构均匀分配到之前的很多次操作里逐步进行，而不是在内存超过 $C$ 那一步一下子全部重构？
问题2. 小明听说路径压缩的并查集能够维护一些元素所属的集合并支持：1. 添加一个单点 2. 查询一个点所属集合 3. 合并两个点所在集合，但单次操作最坏是 $O(n)$ 的。
问题2.1. 现在有一棵 $O(n)$ 个点的并查集树（也就是说所有点都属于同一个集合，直接或间接连到同一个根），对每个点依次进行一次查询操作，没有合并操作。证明路径压缩的并查集在这种情况下的总时间复杂度是 $O(n)$ 的，无论查询顺序如何。
问题2.2. 小明发现某个并查集问题的操作有特殊性质：一共 $n$ 次操作，操作被分为 $k$ 轮：每一轮先进行 $a_i$ 次修改（操作3），再进行 $a_i$ 次查询（操作2），$2\sum a_i = n$。小明想要用路径压缩的并查集做这个问题，使得总时间复杂度仍然不超过 $O(n\log n)$ 的同时，每次询问的最坏时间复杂度（从读入这个询问到输出答案）都是不超过 $O(k)$ 的。
问题2.3. [经典问题，离线动态图连通性][P5787; LOJ121]有一个图，支持加边，删边，查询两点是否连通。一个经典做法是线段树分治，每条边的存在时间是若干个区间，这些区间共有 $O(n)$ 个。将这些区间放在一个以时间为下标的线段树上，对线段树进行遍历，进入/退出每个节点时执行/撤销这个线段树节点上区间对应的边（的连通性合并操作）。遍历到叶子时执行了的恰好就是这个时刻存在的所有边。
为了保证撤销的复杂度正确，一般用单次复杂度有保证的数据结构维护连通性，例如按秩合并的并查集。用路径压缩的并查集能不能解决这个问题？
问题2.4. 你能利用这种方式改进上述问题的时间复杂度吗？ （参考答案-拓展阅读. https://www.luogu.me/article/asttym3k ）
AP006 前 k 小问题和最小扩展过程
问题1. 有两个长为 $n$ 的整数数列，问两个数列中各选一个数的所有方案中，第 $k$ 小的和是多少，$1\le k\le n^2$。请你设计出一个尽量高效的算法。
问题2. 有三个长为 $n$ 的整数数列，问三个数列中各选一个数的所有方案中，第 $k$ 小的和是多少，$1\le k\le n^3$。请你设计出一个尽量高效的算法。
提示：以下这个问题是困难的：
给定 $n$ 个值域较大（位数上界为 $\omega(\log n)$）的整数，问其中是否有三个数的和是 $0$。对于这个问题，人类目前没有找到任何时间复杂度在 $O(n^{1.999999})$ 的算法，也就是目前该问题时间复杂度的多项式次数不小于 $2$。这个问题被称为 3SUM。
假如你有一个问题2的算法，你可能可以利用它设计出一个 3SUM 的算法，从而说明问题2的算法很难低于某个时间复杂度。
如果我们能说明在 $k$ 无约束的情况下问题是困难的，我们就知道了为什么总是考虑 $k$ 较小时求前 $k$ 小/前 $k$ 大，并且时间复杂度和 $k$ 有关。
问题3. 上次课程中已经给出了一个 $O(n+k\log k)$ 的问题2的算法，请你尝试总结该算法的适用范围和条件。你可以添加/删除条件看是否还能做。并解决这个问题：有 $n$ 个整数，请你求出前 $k$ 小的子集和。
问题4. [HDU5757]有 $n$ 个整数，每个整数被染成了黑白两种颜色，请你求出有偶数个黑色元素的子集中，前 $k$ 大的子集和分别是多少。
问题5. 有 $n$ 个整数，请你求出所有大小恰好为 $m$ 的子集中，前 $k$ 小的子集和。
问题6. [P2541]有 $n$ 个数列，每个数列长为 $m$，问每个数列中各选一个数的所有方案中，前 $k$ 小的和分别是多少。
问题7. 有 $n$ 个数列，每个数列长为 $m$，问每个数列中恰好各选 $c_i$ 个数的所有方案中，前 $k$ 小的和分别是多少。
并解决[P6646]。
问题8.[bonus] 根据以上问题，你能否改编或设计出一个需要用到类似方法的问题？
拓展阅读.[bonus] 一种不是保证从小到大扩展，而是类似迭代加深搜索的二分做法：https://www.luogu.com.cn/article/8lob9dt3
AP026 树上复杂度分析练习
问题1.1. 有一棵 $n$ 个点的有根树，每个点的权值等于自身的子树大小减去最大的孩子子树大小。所有点的权值和的上界估计是多少？
问题1.2. 有一棵 $n$ 个点的有根树，每个点的权值等于自身的子树大小减去前 $k$ 大的孩子子树大小。所有点的权值和的上界估计是多少？
问题2.1. 有 $n$ 个集合，每个集合初始大小为 $1$。你每次可以合并两个集合，设两个集合大小分别为 $a,b$，合并代价为 $\min(a,b)$，合并成一个大小为 $a+b$ 的新集合。所有集合最终合并成一个。分别估计最优合并顺序和最劣合并顺序对应的总代价。
问题2.2. 有 $n$ 个集合，每个集合初始大小为 $1$。你每次可以合并两个集合，设两个集合大小分别为 $a,b$，合并代价为 $a+b$，合并成一个大小为 $a+b$ 的新集合。所有集合最终合并成一个。分别估计最优合并顺序和最劣合并顺序对应的总代价。
问题3. 有 $n$ 棵字典树，且它们的点数总和为 $O(n)$，树的深度均不超过 $d$。合并两棵树的代价与两棵树交集的点数成正比，合并得到的为两个树的并集。所有树最终合并成一个，估计合并总代价的上界。如果把“点数总和为 $O(n)$”的限制加强成“字符串总长（所有叶子深度和）为 $O(n)$”，会有变化吗？
问题4. 有一棵 $n$ 个点的无根树，初始情况下每个点的颜色都是 $0$。$n$ 次操作，第 $i$ 次操作在树上选一条路径将路径上的点染成颜色 $i$。问：在操作过程中和结束后曾经出现过的不同的极大同色连通块种类数上界是多少？
问题5.1. 有 $n$ 个集合以及常数 $m$，每个集合初始大小为 $1$。你每次可以合并两个集合，设两个集合大小分别为 $a,b$，合并代价为 $O(a\cdot b)$，合并成一个大小为 $a+b$ 的新集合。所有集合最终合并成一个。分别估计最优合并顺序和最劣合并顺序对应的总代价。
问题5.2. 有 $n$ 个集合以及常数 $m$，每个集合初始大小为 $1$。你每次可以合并两个集合，设两个集合大小分别为 $a,b$，合并代价为 $O(\min(a,m)\cdot \min(b,m))$，合并成一个大小为 $\min(a+b,m)$ 的新集合。所有集合最终合并成一个。分别估计最优合并顺序和最劣合并顺序对应的总代价。
AP027 带权并查集练习
带权并查集：在并查集数据结构中，每个集合对应一棵有根树。我们可以在并查集树上维护每个点到根的信息，方法是维护每个点到并查集父亲的边信息，并在路径压缩时进行信息合并。
从集合的角度，可以认为带权并查集的权值是支持给某个集合整体加一个相同的值。
带权并查集通常用于维护原问题每个集合（连通块）内任取一点到其他点路径都足够使用的信息，例如二分图染色等。
带权并查集经常因为维护信息不能改变连边顺序，导致无法使用按秩合并。从给整个集合加操作的角度，这等价于操作的可逆性。
问题1.1. [P1198]一个数列，要求支持向末尾插入一个数以及查询末尾 $L$ 个数的最大值，强制在线。请你用带权并查集解决这个问题。
问题1.2. 证明你在上个问题中的时间复杂度，并给出一个达到渐进上界的数据构造。（卡满你的算法时间）
问题2. [P2024] [NOI2001] 食物链。解决这个问题。另外，你做这个问题的并查集能同时使用路径压缩和按秩合并（启发式合并）达到 $O(n\alpha (n))$ 的时间复杂度吗？
问题3. [LOJ508弱化版] 你有一个 $n$ 个点的无向图和一个常数 $m$，有两种操作：添加一条连接 $(u,v)$ 权值 $w$ 的边，以及询问是否存在 $u$ 到 $v$ 的路径（可以是非简单路径）长度 $=x\pmod m$。
问题4. 类似离线 Tarjan LCA 算法的扩展，带权并查集可以用于计算树上路径信息。请你做这个问题：给定一棵 $n$ 个点的树，每个节点上有一个权值 $w_i$，请你求出给定的 $q$ 条路径形成的序列的最大子段和（$n,q\le 10^6, w_i\le 10^9$）。
鄂公网安备 42010202000505 号