在讨论《why WA ?》回复：

应该可以通过了，数据更改了

### 解题思路 题目要求方案数，考虑动态规划。 $f_{i, j}$ 表示在前 $i$ 张牌中有 $j$ 张红牌的符合题目要求的所有合法方案数。 考虑动态转移： - 如果第 $i$ 张牌是红牌，那么前 $i - 1$ 张牌需要有 $j - 1$ 张红牌，即 $f_{i, j} = f_{i - 1, j - 1}$。…

在文章《题解：B4304 [蓝桥杯青少年组省赛 2024] 通关游戏的最少能量值》发表评论：

感谢指正

### 解题思路 观察题目，很容易发现这是一个最近公共祖先（LCA）的问题，但是点的数量为 $10^9$，显然我们无法创建这么多节点。 考虑 LCA 算法的过程，求 $a, b$ 的最近公共祖先时，深度较深的点先往上跳，当两个点深度相同时，再一起往上跳，直到相同为止。 同样本道题可以用此思路，由于我们无法快速算出深度，…

在讨论《关于测试数据前后有空字符》回复：

确实逆天@[Whatwyb](luogu://user/1539915)，多谢提醒，洛谷上非常的题的数据都有空格，还是很难崩的。

### 题意分析 将一个长度 $40$ 的数组 $A$ 拆成两份 $a, b$，设 $s_1, s_2$ 分别表示数组 $a, b$ 的和，求 $s_1 \times s_2$ 的最大值。 我们来考虑一下，什么情况下可以使得 $s_1 \times s_2$ 取得最大值。 设数组 $A$ 的和为 $s$，设数组 $a$…

观察上图，我们设从上到下为第 $1, 2, 3, \dots$ 层： - 第一层：$1$ 个。 - 第二层：$1 + 2$ 个。 - 第三层：$1 + 2 + 3$ 个。 - $\dots$ 我们发现第 $k$ 层的个数应该是 $1 + 2 + 3 + \dots + k$。 设 $k, v, s$ 分别表示当前层数、…

下文中记 $C = 26$，表示字符种类的数量。 ### 暴力解法 $O(Cn^5)$ 枚举将第 $i$ 个字符串的第 $j$ 个字符改为 $c$ 的所有方案，时间复杂度 $O(Cn^2)$，修改并计算总分，$O(n^3)$。 ### 暴力优化 $O(Cn^3\log n)$ 我们可以使用**字符串哈希**来优化判断两…

### 解题思路 由于 $a$ 数组是一个 $1$ 到 $n$ 的一个排列，那么形成的一定会构成几个点的循环，或者是几个单独的点。 从任意点开始，如果能进入一个循环，一定可以将整个循环的宝藏都拿走，因为不限进入传送门的次数。 那么，我们可以用**并查集**来维护点与点之间的关系，以及一个小团体里头点的数量。 由于我们可…

### 解题思路 #### 错解 贪心：每次都移动至当前最近的对应方块上。 反例： $s =$ `abxac` $t =$ `abac` 贪心结果（下标） $0 \rightarrow 1 \rightarrow 0 \rightarrow 4$，答案为 $5$。 正确结果（下标） $0 \rightarrow 1 \…

### 题意分析 有一个 $n$ 个点，$n-1$ 条边的无向图，边权均为 $1$。 每个点属于一个集合，同一个集合的点可以互相传送。 给定 $m$ 个询问，求 $x, y$ 的最短距离。 #### 最短路解法 步骤： 1. 建图。 2. 对于所有询问各跑一次最短路算法。 可选用的最短路算法： - Spfa，单次时间复…

### 解题思路 我们先来考虑第一个问题：假设任务次序已经**确认**，该如何求解所需的最小能量？ 很明显，假设能量 $x$ 可以完成所有任务，那么能量大于 $x$ 时一定可以。假设能量 $y$ 不能完成所有任务，那么小于 $x$ 时一定也不可以。举有单调性，可以使用二分求解。 第二个问题：如何确定任务次序，使得所需能…

### 解题思路 这里我们设置字符向右移动为正，往左移动为负。 第一个字符的移动次数为 $a_1-a_2+a_3-a_4+\dots$。 第二个字符的移动次数为 $-a_2+a_3-a_4+\dots$。 发现涉及大量重复计算，所以我们可以用后缀和来优化求和过程。 时间复杂度 $O(n)$。 ### AC_Code `…

### 解题思路 众所周知 $x \oplus x = 0$，其中 $\oplus$ 表示异或运算。 由题面可知有且仅有一个数出现了奇数次，那么将所有数异或的结果即为该数。 ### AC_Code ```python n, a = input(), list(map(int, input().split())) res…

### 解题思路 我们可以遍历整个地图，当发现农作物 `R` 时，表示我们发现了一块农作物，答案加一，随后将这块农作物及其联通的农作物全部改为杂草 `X`，防止重复计算。 时间复杂度 $O(nm)$。 ### AC_Code ```cpp #include using namespace std; const int…

### 解题思路 类似题链接：[P8647 分巧克力](https://www.luogu.com.cn/problem/P8647)。 原题链接：[B4285 最大值](https://www.luogu.com.cn/problem/B4285)。 --- 容易得知当正方形的边长越大，能切出正方形的数量越少。故具有…

### 解题思路 由于 $(1, 2, 5)$ 和 $(2, 1, 5)$ 是同一种方案，那么为了在选取的过程中避免重复计算，我们可以要求选取的数必须严格单调递增，即 $i using namespace std; int n; bool check(int x) { while (x) { if (x % 10 ==…

### 解题思路 由于本题存在加减乘除四则运算，那么我们要做的第一步就是先处理乘除法运算。 遍历一遍字符串，若运算符为乘除，则需要计算后放入栈中，反之直接放入栈中。 那么当上述步骤完成时，已经将所有乘除操作处理。 此时，符号栈中只有加减符号。加减为同级运算，所以需要从左往右按照顺序计算。 栈是先进后出的结构，所以栈顶存…

### 解题思路 按照题目要求进行模拟即可。 由于整数进行交换两个位置上的数字较为麻烦，所以我们可以选用字符串进行处理。 交换完毕之后，我们可以去找第一个非零位，那么从这个位置上输出即表示去除前导零的结果。 ### AC_Code ```cpp #include using namespace std; int mai…

### 解题思路 考虑暴力，枚举 $1 \sim n$，判断每个数是否合法，复杂度 $O(n\log n)$。 考虑优化，我们可以尝试枚举所有的平方数，再判断转换为八进制后是否一个回文数，时间复杂度 $O(\sqrt n\log \sqrt n)$。 ### AC_Code ```cpp #include #inclu…

### 解题思路 板题链接：[P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) 原题链接：[B4275 活动人数](https://www.luogu.com.cn/problem/B4275) --- 考虑 DP： - $f_{i,1}$ 表示以 $i$ 为…

### 解题思路 考虑暴力，枚举高度 $h_i$，对于每个高度再去枚举其最大宽度，即往左以及往右最远能扩展多远，时间复杂度 $O(n^2)$。 往左最远能扩展多远相当于找左侧第一个小于 $h_i$ 的高度 $h_j$，那么我们可以使用单调栈进行求解，右侧同理，时间复杂度 $O(n)$。 ### AC_Code ```c…

### 解题思路 **40pts** 对于每个询问 $x$，做一遍 `Dijkstra` 即可得出 $x$ 从家出发到学校的最短时间。 时间复杂度 $O((n + m)q\log m)$。 **100pts** 由于每个询问的终点均为学校，那么我们可以考虑以学校为起点做一遍 `Dijkstra`，这样就可以求出从学校到…

### 解题思路 若一个子串能被等价消除，则其中每个字符的出现次数必须全为**偶数**。这是因为每次删除两个相同字符的操作，最终会将所有字符的出现次数减至零，而偶数次是完成这一过程的必要条件。 我们用一个 $26$ 位的二进制数来记录当前各字符出现次数的奇偶性。每一位对应一个小写字母：若某位为 $1$，表示该字母出现了…

### 解题思路 原题链接：[P11960 平均分配](https://www.luogu.com.cn/problem/P11960)。 考虑贪心，策略如下： - 对于每个物品求出小 B 与小 C 出价的差值 $d_i = b_i - c_i$。 - 所有物品按照差值 $d_i$ 从大到小进行排序，小 B 选择 $d…

### 解题思路 原题链接：[P11962 树上漫步](https://www.luogu.com.cn/problem/P11962)。 假设点 $a$ 可以通过偶数步能到达 $b$，那么 $b$ 也一定能够通过偶数步到达 $a$。 那么我们会发现，树中的点一共可以分为两个集合，一个点可以通过偶数步到达集合内的任意点…

### 解题思路 原题链接：[P11963 环线](https://www.luogu.com.cn/problem/P11963)。 本题为 [P1115 最大子段和](https://www.luogu.com.cn/problem/P1115) 的环形版。 --- 答案有两种情况： 1. 最大子段和的起点 $l$…

在讨论《希望取消红名的数据上传及题目提交的验证码，优化体验》回复：

@[MESSIALA](luogu://user/259636) 是的呢~ 这句话也要告诉你自己哦，争取拿到 S2/S1？争取红名！

在讨论《希望取消红名的数据上传及题目提交的验证码，优化体验》回复：

@[MESSIALA](luogu://user/259636) 我也觉得厉害呢！多谢夸奖！

在讨论《希望取消红名的数据上传及题目提交的验证码，优化体验》回复：

@[MESSIALA](luogu://user/259636) 小朋友，不打比赛了，就回归课堂，好好学习哈。