题目链接 翻转01 题目描述 给定一个长度为  的 01 字符串和一个整数 。每次操作可以翻转字符串中的任意一个字符（'0' 变为 '1'，'1' 变为 '0'）。 任务是判断是否能通过恰好  次操作，使得字符串变为一个回文字符串。 解题思路 这个问题的核心在于分析将字符串变为回文串所需的翻转次数与给定的操作次数  之间的关系。 1. 计算最小所需翻转次数 要使一个字符串成为回文串，对于所有 （从 0 到 ），必须满足 S[i] == S[n-1-i]。 我们可以遍历字符串的前半部分，比较每一对对称位置的字符 S[i] 和 S[n-1-i]。如果它们不相同，我们必须至少翻转其中一个才能使它们匹...

题目链接 棋盘 题目描述 在一个  的棋盘上，每个格子写有数字 0 或 1。当小球在某个格子上时，如果数字是 0，它会向下移动一格；如果是 1，它会向右移动一格。对于给定的  个查询，每个查询指定一个子矩阵范围和一个起始点，要求计算小球从该起始点出发，在子矩阵内滚动，最终会从哪个格子滚出子矩阵。 解题思路 对于每个查询，一个朴素的方法是根据规则一步步模拟小球的移动，直到它越出子矩阵边界。对于一个  的棋盘，单次模拟最坏情况下可能需要  步。考虑到查询数量  可能很大（高达 ）， 的总复杂度可能会超时。 为了优化这个过程，我们可以注意到小球的移动路径是完全确定的。从任何一个格子  出发，它的下一...

题目链接 小红的项链 题目描述 在一个由  个珠子组成的环形项链上，有 3 个红色珠子，其余为白色。任意相邻两个珠子的距离为 1。小红希望通过最少的相邻珠子交换次数，使得任意两个红色珠子之间的最小距离不小于 。 任务是计算所需的最小交换次数。如果目标无法达成，则输出 -1。 解题思路 这个问题的核心在于，通过移动珠子来重新分配它们之间的“空位”，使得所有空位长度都大于等于 ，并且总的移动成本最低。 1. 可行性判断 首先，为了使 3 个红珠子之间的距离都至少为 ，项链的总长度  必须至少为 。如果 ，则无论如何都无法满足条件，应输出 -1。 2. 最小交换次数的核心逻辑 移动一个珠子一格，会使...

题目链接 小红玩纸牌 题目描述 给定一副数量庞大的扑克牌，包含四种花色（'S', 'H', 'D', 'C'）和不同的数值。小红每次可以从中取出 5 张牌，如果这 5 张牌构成“同花顺”，则获得 1 分，然后将这 5 张牌丢弃。 “同花顺”是指 5 张牌花色相同，且数值是连续的（例如：5H, 6H, 7H, 8H, 9H）。 任务是计算小红最多可以获得多少分。 解题思路 这个问题的核心在于，如何选择组成的同花顺，才能使得总的得分最高。因为取出的牌会被丢弃，所以一个选择可能会影响后续的选择。例如，一张 5H 既可以用于组成 1H-5H 的同花顺，也可以用于 2H-6H 等等。 由于不同花色的牌之...

题目链接 小红的好数组 题目描述 小红定义一个数组为“好数组”，当且仅当该数组中有且仅有一个元素与其他所有元素不同。例如，[2, 2, 5, 2, 2] 是一个好数组。 给定一个数组，每次操作可以使数组中的任意一个元素加 1 或减 1。目标是计算将原数组变为“好数组”所需的最少操作次数。 解题思路 一个“好数组”由两部分组成： 个值相同的“多数元素”和一个值不同的“唯一元素”。我们的目标是确定原数组中的哪些元素应该变成“多数元素”，哪个元素应该变成“唯一元素”，以及它们的最终值应该是多少，从而使总操作次数（即值的变化总量）最小。 为了最小化操作成本，一个关键的洞见是：要被塑造成“多数元素”的 ...

题目链接 小红的子串权值和 题目描述 给定一个长度为  的 01 字符串。一个字符串的“权值”被定义为其中极长连续相同字符段的数量。例如，字符串 "1100111" 的权值为 3，因为它由 "11"、"00" 和 "111" 三个连续段构成。 任务是计算该 01 字符串所有子串的权值之和。 解题思路 一个直接但效率不高的思路是枚举所有  个子串，然后对每个子串计算其权值，最后将所有权值相加。这种方法的总时间复杂度为 ，对于典型的  值（例如 ）来说太慢了。 我们可以采用一种更高效的“贡献法”来解决此问题。我们将权值...

题目链接 小红的区间删除 题目描述 给定一个数组，小红可以执行最多一次操作：选择数组中两个值相等的元素，并将这两个元素之间的所有元素（不包括这两个元素本身）删除。 目标是计算出通过此操作最多可以删除多少个元素。 解题思路 题目的核心是找到一对值相等的元素，其在数组中的索引分别为  和 （假设 ），使得它们之间的元素数量  最大化。 为了最大化  对于一个特定的值，我们应该选择该值在数组中第一次出现的索引作为 ，以及最后一次出现的索引作为 。然而，一个更简洁的思路是，我们只需要记录每个元素第一次出现的索引。 我们可以使用一个哈希表（在 C++ 中是 std::map，Java 中是 HashMa...

题目链接 PEEK154 小红的二分图构造 题目描述 给定  个节点的度数序列  (, )，要求构造一个含  个节点的二分图，使得第  个节点的度数恰好为 。 如果无法构造，输出 -1。否则，输出图的边数和所有边。构造的图可以包含重边，但不能有自环。 解题思路 这是一个构造性问题。解决问题的关键在于理解二分图的度数性质，并将问题分解为两个主要步骤：划分和连接。 1. 核心性质与问题转化  握手定理: 任何图中，所有节点的度数之和等于边数的两倍。因此，如果给定的度数之和  是奇数，则不可能构成任何图，直接输出 -1。 二分图性质: 在一个二分图的两个点集  和  中，  中所有节点的度数之和必须...

题目链接 该问题似乎是特定竞赛的题目，暂无公开链接 题目描述 给定一个初始值  和一个由  个正整数组成的数组 。定义一次操作如下：  选择数组  中的若干个元素（至少一个），记元素之和为 。 将  更新为 。  求解有多少种不同的操作方案，使得恰好经过  次操作后 。由于答案可能很大，请将答案对  取模后输出。 记第  次选取元素的下标构成的集合为 ，两个方案被视为不同的，当且仅当存在  使得两个方案第  次选取元素的下标构成的集合不同。 解题思路 这是一个多阶段决策的计数问题。由于操作次数  非常大，而状态空间（模  的余数）相对较小，这强烈地暗示了需要使用矩阵快速幂来进行优化。 动态规划...

题目链接 PEEK153 渝 题目描述 给定一个由数字  和  组成的三角形，一共有  行，第  行有  个数字。我们使用  表示第  行第  列的数字。 从顶点  出发，每次可以移动到左下方  或右下方 ，直到到达第  行。这样形成一条长度为  的路径，路径经过的数字拼接成一个字符串。 请求出有多少条路径，其对应的字符串是回文串。答案需要对  取模。 解题思路 本题要求我们统计满足回文条件的路径数量。回文串的性质是 s[i] == s[n-i+1]，这意味着路径上第  行的数字必须与第  行的数字相同。这个首尾对应的要求，是使用“双端动态规划”或“相遇 DP”（Meet-in-the-mid...

题目链接 PEEK151 斐波那契公约数 题目描述 给定经典的斐波那契数列 ，其定义如下：  现给定两个正整数  与 （），请你计算  并对  取模后输出结果。 解题思路 本题要求计算两个斐波那契数  和  的最大公约数（GCD）。由于  和  可能非常大，直接计算  和  是不可行的。 1. 关键性质 解决本题的核心在于利用斐波那契数列的一个重要数论性质：  这个定理指出，两个斐波那契数的最大公约数，等于它们下标的最大公约数所对应的那个斐波那契数。 这个优美的性质将问题极大地简化了。我们不再需要处理两个庞大的斐波那契数，而是可以先计算出下标的 ，然后再求对应的斐波那契数。 2. 问题转化 根...

题目链接 波斐契那数列 题目描述 定义数列  满足：  给定 ，请求出  的值。由于结果可能很大，请对  取模。 解题思路 这是一个典型的线性递推关系求解问题。由于  的范围可以达到 ，使用简单的  递推或递归会超时。对于这类问题，标准的高效解法是矩阵快速幂 (Matrix Exponentiation)。 算法步骤   建立状态向量: 递推关系  依赖于前三项中的两项。为了能够从第  步的状态推导出第  步的状态，我们需要维护一个包含足够历史信息的状态向量。选择一个  的向量是合适的，因为它包含了计算  所需的所有项：    构建转移矩阵: 我们的目标是找到一个  的转移矩阵 ，使得：  根...

题目链接 【模板】矩阵快速幂 题目描述 给定一个  的整数方阵  以及一个非负整数 ，请计算矩阵 。当  时，约定  为  单位矩阵 。所有计算结果对  取模。 解题思路 本题要求计算一个矩阵的  次幂。如果  非常大，直接进行  次矩阵乘法（）会超时。这是一个典型的可以使用快速幂 (Binary Exponentiation) 思想来解决的问题。 常规的快速幂用于计算一个数的幂（例如 ），其核心思想是将指数  进行二进制拆分，从而将时间复杂度从  优化到 。同样的思想也适用于矩阵乘法，因为矩阵乘法满足结合律（即 ），这是使用快速幂算法的前提。 算法步骤   定义矩阵乘法: 首先，我们需要一个...

题目链接 PEEK149 斐波那契数列 题目描述 经典的斐波那契数列  定义如下：  给定一个非常大的整数 ，计算  在模  意义下的值。 解题思路 当  的值非常大时（例如 ），直接使用循环递推计算  的方法（时间复杂度为 ）将会超时。这是一个典型的可以使用矩阵快速幂进行优化的线性递推问题。 1. 构造递推矩阵 斐波那契数列的核心递推关系是 。为了将其转化为矩阵形式，我们需要一个状态向量。我们选择向量 。我们的目标是找到一个  的转移矩阵 ，使得：  根据递推公式，我们可以写出：     将这个线性方程组写成矩阵形式，我们得到：  这个  就是我们需要的转移矩阵，我们称之为 。 2. 矩阵快...