夏令营7.25总结

今天照例还是模考。

时间线

我发现写时间线要考试的时候自己记录，容易忘也很烦，以后模考的话时间线就不写了吧。

题目

T1

当遇到一道题目，如果有两个思路，一个简单但是正确性不确定，另一个较难但是确定正确，就可以通过写对拍等方式验证猜想。

思路是给一个数组中的每个元素分配一个“分数”，然后计算所有分数的总和。分数的分配规则基于元素与其相邻元素的大小关系：

• 较大的元素应该获得较高的分数
• 相等的元素应该获得相同的分数
• 最终每个元素的分数是其从左侧和右侧两个方向计算出的分数的最大值
• 计算出的最大值即为答案。

T2

考虑贪心。

• 匹配K的每一位，尽可能保持前缀相同（以保证M最小），仅在必要时调整某一位为更大的数字，并将剩余数字按升序排列（确保后续位最小）。
  回溯：
• 一位无法匹配K时，回溯到前一位寻找更大的数字，避免 “卡死” 在无效路径上。
  数字排列的化：
• 定某一位使用更大的数字后，剩余数字按升序排列，直接保证后续位最小，无需再比较。

T3

要使总不满意度最小，关键是让 A 中分给学生的 N-1 个元素与 B 的 N-1 个元素 “最优匹配”（即每个 B[j] 匹配最接近的 A[i]）。由于 A 和 B 都是数字，排序后按顺序匹配是最优策略（这是贪心算法的经典结论：两个数组排序后一一对应，差值之和最小）。

T4

分两种情况处理：

• 若整个字符串已经是回文串（指针相遇仍未找到不匹配）：
  此时需要插入一个字符使其仍为回文串。最简单的方式是在中间位置插入一个与中心字符相同的字符（如 “ee” 插入 “y” 变成 “eye”）。
• 若存在不匹配的s[i]和s[j]：
  尝试两种插入方案：
  • 在 i 位置左侧插入 s[j]（使 s[j] 与右侧的 s[j] 对称）。
  • 在 j 位置右侧插入 s[i]（使 s[i] 与左侧的 s[i] 对称）。
    检查两种方案是否能形成回文串，若能则输出其中一个；若都不能，则输出 NA。

T5

1. 棋子位置的约束分析

设：

• r[i]表示第i行是否反转（1=反转，0=不反转）。
• c[j]表示第j列是否反转（1=反转，0=不反转）。

棋子(A_i, B_i)最终为白色的条件：
初始格子为白色，反转次数为偶数（0或2次）时仍为白色，即：
r[A_i]+c[B_i]≡0(mod2) → c[B_i]=r[A_i]（因为0+0=0，1+1=2≡0）。

这意味着：列的反转状态由其所在行的反转状态决定，两者必须相同。

2. 连通分量划分

通过棋子的约束关系，行和列形成“连通分量”：

• 若棋子(a, b)存在，则行a与列 b 必须同状态（r[a]=c[b]）。
• 由此可构建一张 bipartite 图（行和列作为节点，棋子为边），连通分量内的行和列的反转状态必须一致（要么全反转，要么全不反转）。

代码通过 DFS 遍历 划分连通分量，记录每个分量包含的行数（x[tot]）和列数（y[tot]）。

3. 动态规划（DP）求解最优反转方案

设最终选择反转的行总数为i（0≤i≤H），则：

• 未反转的行数为H-i。
• 根据约束，反转的列数 j 由连通分量的选择决定（需满足 0≤j≤W）。

黑色格子数量的计算公式（推导见下文）：
黑色格子数=i×(W-j)+j×(H-i)

为最大化该值，需通过 DP 计算每个可能的i对应的最小和最大j（j需在[0, W]内）：

• f[i]：选择i行反转时，最多能反转的列数。
• g[i]：选择i行反转时，最少能反转的列数。