题目链接 数位差与数值和的构造 题目描述 给定一个整数 ，请找到两个非负整数  和 ，满足以下两个条件：    的数字和与  的数字和之差的绝对值不超过 1。  题目保证解总是存在的，若有多组解，输出任意一组即可。 解题思路 这是一个构造性问题。我们需要将一个数  拆分为两个数  和 ，同时满足数值和与数字和两方面的约束。 1. 核心构造思想 要确保  这个条件成立，最直接的方法是按位构造。也就是说，我们将  的每一位数字  都拆分成两个数字  和 ，使得 。如果  的所有位都遵循这个规则，那么将  和  构成的数  和  相加，结果必然是 。 例如，如果 ，我们可以将其看作 。  对于百位的...

题目描述 给定一个长度为  的数列  和一个整数 。对于所有长度为  的子区间（滑动窗口），你需要求出该子区间内“后缀最大值”位置的个数。 一个下标  是数列  的后缀最大值，当且仅当：对于所有的 ，都有 ，其中  表示  的元素个数。 解题思路 本题要求对所有长度为  的滑动窗口，计算其中后缀最大值的数量。一个朴素的解法是遍历每个窗口，再对窗口内的元素进行判断，总时间复杂度为 ，会超时。 我们可以采用更高效的思路。首先分析一个元素  在何时会成为一个后缀最大值。根据定义， 是某个窗口中的后缀最大值，当且仅当在该窗口内， 的右侧没有比它更严格大的元素。 这个性质让我们联想到 “下一个严格更大元...

题目链接 能量辐射 题目描述 有  个能量发射站排成一行，每个发射站  都有一个不相同的高度  和一个能量值 。每个站会同时向左和向右发射能量，能量会被两侧最近的且比它高的发射站接收。请计算接收能量最多的发射站总共接收了多少能量。 解题思路 本题的核心是，对于每个发射站 ，我们需要找到它左侧第一个比它高的发射站（记为 ）和右侧第一个比它高的发射站（记为 ）。 和  就是分别接收来自  的左向和右向能量的站。 1. 朴素解法 一个直接的想法是，对每个发射站 ，都向左和向右进行线性扫描，以找到  和 。这种方法对于每个  都需要  的时间，总时间复杂度为 。对于  的数据规模，该方法会超时。 2....

题目链接 灌注水箱 题目描述 有一个水箱，从左到右有  个挡板，第  个挡板的高度为 。水从最左侧以每秒 1 个单位体积的速度注入。水在一个区域内的水位是均匀的。当一个区域的水位超过其右侧挡板的高度时，水会溢出到下一个区域。求每个挡板被溢过的最早时刻。 解题思路 直接模拟每一秒的水流过程显然会超时。这是一个动态规划问题，可以通过数据结构进行优化。 1. 核心模型：盆地填充 我们可以将注水过程看作是填充一系列“盆地”。每个挡板  都是其左侧一个盆地的右边界。这个盆地的左边界，则是由左侧第一个高度大于或等于  的挡板  决定的。如果不存在这样的挡板，我们可以认为最左侧有一个无限高的 0 号挡板。 ...

题目链接 最小的最小未出现自然数 题目描述 给定一个长度为  的整数序列  和一个整数 。对于所有满足  的 ，需要计算 。 最终，需要求出这些  值中的最小值。 【名词解释】 最小未出现的自然数（mex）： 指的是不包含在集合  中的最小非负整数。 解题思路 本题要求计算所有长度为  的滑动窗口的  值，并找出这些  值中的最小值。 一个朴素的解法是遍历每一个滑动窗口，对窗口内的元素计算  值，然后取所有结果的最小值。对于每个窗口，计算  的时间复杂度约为 。总共有  个窗口，因此总时间复杂度为 ，对于给定的数据范围会超时。 我们可以转换问题的角度。设最终答案为 ，即所有窗口的  值的最小值...

题目链接 数列后缀极大位置统计 题目描述 有一个初始为空的数列 。需要进行  次操作，每次操作在  的末尾添加一个正整数。每次操作结束后，需要找到当前数列  中所有后缀最大值的下标（从 1 开始），并输出这些下标的按位异或和。 一个下标  是后缀最大值，当且仅当  大于其后的所有元素，即对于所有 ，。 解题思路 本题要求在动态添加元素的过程中，高效地维护一个关于后缀最大值下标的统计量（异或和）。 1. 朴素思想与优化方向 一个简单的想法是，每次添加元素后，都从后往前重新扫描整个数组，找到所有的后缀最大值并计算异或和。设当前数组长度为 ，此操作需要  时间。 次操作的总时间复杂度将是 ，对于  ...

题目链接 我在仰望~ 题目描述 有  只奶牛站成一排，第  只奶牛的身高是 。 每只奶牛都在向右看。对于奶牛 ，如果存在一只奶牛  满足  且 ，则称奶牛  可以仰望奶牛 。 需要求出每只奶牛  右侧第一个身高比它高的奶牛  的编号。如果不存在这样的奶牛，则输出 。 解题思路 本题的实质是求解每个元素的“下一个更大元素”（Next Greater Element）。对于数组中的每个元素，我们需要找到它右边第一个比它大的元素。 一个朴素的解法是使用双重循环：对于每个奶牛 ，向右遍历直到找到第一个身高  的奶牛 。这种方法的时间复杂度为 ，在  较大时会超时，因此需要更高效的算法。 这个问题可以使...

题目链接 直方图中最大矩形面积 题目描述 给定一个由  个宽度为  的相邻矩形组成的直方图，第  个矩形的高度为 。你需要计算这个直方图中可以构成的最大矩形的面积。 解题思路 这是一个经典的算法问题。核心思想是，对于每个矩形条 ，如果我们将其作为最终最大矩形的高，那么我们需要找到这个矩形可以向左和向右延伸的最大宽度。这个宽度由其左右两侧第一个比它矮的矩形条所决定。 一个朴素的解法是遍历每个矩形条 ，然后分别向左和向右扫描，找到第一个高度小于  的边界，从而确定宽度并计算面积。这种方法的时间复杂度为 ，对于较大的  会超时。 更高效的解法是使用单调栈，可以在  的时间内解决此问题。我们维护一个单...

题目链接 Sliding Window 题目描述 给定一个大小为  的数组和一个大小为  的滑动窗口。窗口从数组的最左侧移动到最右侧，每次向右移动一个位置。你需要输出在每个窗口位置时，窗口内的最小值和最大值。 解题思路 本题是求解“滑动窗口最大/最小值”的经典问题。如果采用朴素的暴力解法，即对每个窗口都遍历一遍来寻找最值，时间复杂度将达到 ，在  和  较大时会超时。 解决这个问题的最优方法是使用单调队列 (Monotonic Deque)，它可以将时间复杂度优化到 。 单调队列是一种特殊的双端队列，其核心思想是：在将新元素加入队列时，通过维护队列的单调性，确保队首元素始终是当前有效窗口内的最...

题目链接 【模板】Anti-Nim游戏 题目描述 给定  堆石子，数量分别为 。两位玩家轮流操作，Alice 先手。 操作规则如下：  每次任选一堆石子，取走正整数个。 拿到最后一个石子的一方判负。  如果双方均采用最优策略，判断先手是否必胜。 解题思路 本题是 Anti-Nim 游戏，也称为反 Nim 游戏或 Misere Play Nim。它的规则与标准 Nim 游戏几乎完全相同，唯一的区别在于胜负的判定：在 Anti-Nim 游戏中，取走最后一个石子的玩家失败，而不是胜利。 虽然规则只有微小差别，但其最优策略与标准 Nim 游戏有所不同，需要分情况讨论。标准 Nim 游戏的胜负手由所有石...

题目链接 【模板】Nim游戏 题目描述 有  堆石子，第  堆有  个。Alice 和 Bob 两位玩家轮流行动，Alice 先手。每人每次可以从任意一堆中取走任意正整数个石子（也可以取完）。取走最后一颗石子的玩家获胜。假设双方都采取最优策略，判断先手能否必胜。 解题思路 本题是组合博弈论中最经典的模型——Nim 游戏。所有公平组合博弈（Impartial Games）的问题都可以通过 Sprague-Grundy 定理转化为 Nim 游戏。 对于 Nim 游戏本身，有一个简洁而优美的结论来判断胜负： 一个 Nim 游戏的局面是必败态，当且仅当所有石子堆数量的异或和 (XOR sum) 等于 ...

题目链接 【模板】扩展巴什博弈 题目描述 有一堆石子，共  个。Alice 和 Bob 两位玩家轮流行动，Alice 先手。每人每次可以从堆中取走  个石子，其中 。如果轮到某位玩家时，剩余石子数小于 ，则该玩家无法操作，判负。取走最后一个石子的一方获胜。假设双方都采取最优策略，判断先手能否必胜。 解题思路 本题是巴什博弈的扩展形式。标准的巴什博弈允许取  个石子，而本题允许取  个。解题的核心思想仍然是寻找游戏状态的周期性，并划分出周期内的“必胜态”与“必败态”。   寻找状态周期 通过博弈论的归纳分析可以证明，此类取石子游戏的胜负状态是以  为周期循环的。也就是说，一个有  个石子的局面，...

题目链接 最多取半的巴什博弈 题目描述 给定  个石子，Alice 和 Bob 轮流操作，Alice 先手。 每次操作，设当前石子总数为 ：  若 ，则当前玩家立即输掉游戏。 当前玩家必须从石堆中取走  个石子，其中  满足 。  假设双方都采取最优策略，判断谁会获胜。 解题思路 这是一个经典的公平组合游戏，其胜负状态可以通过寻找必胜态（N-position）和必败态（P-position）来解决。  必败态 (P-position)：处于该状态的玩家，无论如何操作，其后继状态都将是必胜态。 必胜态 (N-position)：处于该状态的玩家，至少存在一种操作，使其后继状态是必败态。  根据规...

题目链接 不连续的巴什博弈 题目描述 Alice 和 Bob 进行一个博弈游戏。初始有  个石子。给定一个包含  个正整数的集合 。 双方轮流操作，Alice 先手。每次操作，玩家从集合  中选择一个元素 ，且  不超过当前石子数。然后从石堆中取走  个石子。 如果轮到某位玩家时，对于集合  中的所有元素 ，都有  大于当前石子数，那么该玩家无法操作，判负。 假设双方都采取最优策略，判断谁会获胜。 解题思路 这是一个经典的公平组合游戏，其胜负状态可以通过 Sprague-Grundy 定理来解决。该定理为每个游戏状态分配一个称为 Grundy 数（或 SG 值）的非负整数。  必败态 (P-p...