死亡回放
【8:30】 开！看 T1，发现 T1 相当可做，这个 nice 串就像一个螺旋的序列。
数据范围不大，于是考虑 dfs & 分治。写写写……
【9:01 - 9:05】 写完了，过样例。手搓 hack，全过了。
【9:06】 看 T2，好像很简单。用了一个 vector 把点分别连边，图上跑了一个 dfs。
【9:34 - 9:47】 写完了。样例一过了，二没过。断点测试，没调出来……
尝试乱搞，突然发现自己忘记清空 vis 数组了。。。
然后样例全过了。
【9:48】 时间浪费的太多了，来不及造 hack 了，赶快开 T3。
【9:49 - 10:17】 T3看起来是组合数学，不是我是 xxs 啊，数学太差了，不会处理逆元。
尝试使用杨辉三角，可是没过样例……
【10:28 - 10:45】 调啊调啊调啊……崩溃了 qwq，什么桂题T^T。
【10:46 - 11:12】 放弃正解，打！暴！力！
【11:13 - 11:35】 完辣，样例没过……疯狂乱搞，拼尽全力仍无法战胜
【11:36 - 12:00】 留给 ytx 的时间不多了……完了模考要坠机了，T4 好难，像个树形 dp。
dp 部分好写，但是输入的是个字符串啊！怎么建树呢？想着想着要交卷了。。。
赶紧骗个分，输出 impossible 试试……
估分：
实际：
考试总结
考的啥呀……暴露出了几个个主要的问题：
- 时间分配不合理，如果有一些题不会，原本可以放弃然后主攻自己会的题目的。像 T2，很明显思路不是假的，但是可以考虑记忆化，再加上数据结构优化就能 A 掉的。
- 不够仔细，很多原本一遍能过的题目耽搁了好久。而且 T2 是可以拿到 70 的，但是没有去造 hack 核实，导致 T2 莫名其妙地挂了，模考又挂打分了……
题目题解
T1 nice串
签到题，考虑把区间分成左右两个部分，然后继续细分、再分……具体来说，通过递归地分割字符串，判断每个子串是否符合特定条件，从而确定需要修改的最小次数。设目标字符为 ch，则递归过程中，会分别处理两种情况：
- 左部分是目标字符 ch，右部分是目标字符 ch+1。
- 右部分是目标字符 ch，左部分是目标字符 ch+1。
所以，解法是计算从 l 到 r 区间内，需要修改为字符 c 的字符数；再对每个子串递归地检查是否符合递归定义，并计算最小修改次数。
Code
inline void dfs(int l, int r, int cnt, char ch) {
// 基本终止条件：当区间缩小到一个字符时
if (l == r) {
if (s[l] != ch) cnt++; // 如果当前字符与期望的字符不同，则需要修改
ans = min(ans, cnt); // 更新最小修改次数
return ;
}
int mid = (l + r) >> 1; // 计算中点
// 递归处理两种分割方式，递归处理左部分和右部分
dfs(l, mid, cnt + get(mid + 1, r, ch), ch + 1); // 左半部分为 ch，右半部分为 ch+1
dfs(mid + 1, r, cnt + get(l, mid, ch), ch + 1); // 右半部分为 ch，左半部分为 ch+1
}
int get(int l, int r, char c) {
int cnt = 0;
for (int i = l; i <= r; i++) {
if (s[i] != c) cnt++;
}
return cnt;
}
T2 通明(加强版)
纯水，但就是写挂了。。。
介绍下蒟蒻的思路：
先构建一个有向图，每个节点代表一个形态，如果形态 i 可以转换到 j （即 a[i]<a[j] 且 |i-j|\le w ），则在图中添加一条 i 到 j 的边。然后，使用 dfs 遍历所有可能的路径，找出最长的路径长度，这个长度减去1就是最多变换次数。
于是，这个蒟蒻写了这么一个代码。
// 记得清空清空清空清空清空清空清空清空清空清空！
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, w;
int a[N], vis[N], ans = INT_MIN;
vector<int> g[N];
inline void dfs(int x, int cnt);
int main()
{
freopen("bright.in", "r", stdin);
freopen("bright.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> w;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i + w - 1 <= n; i++) {
for (int j = i + 1; j <= i + w - 1; j++) {
if (a[i] > a[j]) g[j].push_back(i);
else if (a[i] < a[j]) g[i].push_back(j);
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = 1;
dfs(i, 1);
vis[i] = 0;
}
}
cout << ans;
return 0;
}
inline void dfs(int x, int cnt) {
vis[x] = 1;
ans = max(ans, cnt);
for (auto y : g[x]) {
if (vis[y]) continue;
dfs(y, cnt + 1);
vis[y] = 0;
}
}
但是寄了，又 WA 又 TLE 又 RE……难绷（
这个蒟蒻总结了好久，才发现了死因：
建图逻辑是错的!
我只处理了每个位置 i 之后的 w-1 个位置，但题目允许 |i-j| ≤ w，即 j 可以是 i 前后各 w 的位置。
而且这个数据范围肯定会 TLE，需要用数据结构优化。
不妨换种思路：找到最长的递增子序列，其中每个元素的位置差不超过窗口大小 w。这样可以用 dp 解决。
我们将形态按智力值排序，这样可以按顺序处理每个形态，确保每次处理的形态智力值不小于之前的形态。注意：要避免重复的情况，所以要加特判。
Code
for (int i = 1; i <= n; i++) {
for (int j = i - 1; j >= 1; j--) {
if (abs(a[i].y - a[j].y) <= w && a[i].x > a[j].x) dp[a[i].y] = max(dp[a[j].y] + 1, dp[a[i].y]);
}
}
这样还是会 T，考虑用线段树维护位置范围内的最大 dp 值，这样可以在 O(\log n) 时间内查询和更新最大值，从而将总体复杂度优化到 O(n \log n)，代码不放了。
T3 成绩排名
我对此题的评价：根本不可做。。。
还是看看官方题解吧，比我讲的好：
================================================================
好吧蔡老师说我写的敷衍，于是补一下：
我们需要计算每个学生在是否获得强化书的情况下，成绩排名保持不变的总情况数。
每次强化有两种情况：
-
未获得书：统计不影响排名的同学数量 m，计算组合数 C(n-m, k)。
-
获得书：需恰好“抵消”自己的提升，统计必须分配书的同学数量 d，计算组合数 C(n-m-1, k-1-d)。
暴力计算组合数会超时，我们不妨使用预处理阶乘和逆元阶乘的 O(1) 组合数查询。
下面详细讲一下逆元：
在模运算中，除法需转换为乘法逆元。代码采用线性递推法预处理逆元：
逆元公式：
inv[i] = (mod - mod / i) × inv[mod % i] % mod
该公式基于模的数学性质在质数模 mod=1e9+7 下成立，可在 O(n) 时间预处理。
递归实现：
ll get(ll x) {
if (inv[x]) return inv[x]; // 记忆化
if (x == 1) return inv[x] = 1;
return inv[x] = (mod - mod/x) * get(mod%x) % mod;
}
递归求解逆元并缓存结果，预处理 inv[1..N]，随后构建逆元阶乘数组 invfac[i]。
阶乘预处理：
• fac[i] = i! % mod
• invfac[i] = inv[i!] % mod
那么组合数公式 C(n, m) = \frac{n!}{m!(n-m)!} 就变为：
C(n, k) = fac[n] * invfac[k] * invfac[n-k] % mod
Code
for (int i = 0; i < n; i++) {
ll x = a[i];
int m = upper_bound(b, b + n, x) - upper_bound(b, b + n, x / t);
ll ans = C(n - m, k);
m = upper_bound(b, b + n, x * t) - upper_bound(b, b + n, x);
ans = (ans + C(n - m - 1, k - 1 - m)) % mod;
cout << ans << '\n';
}
T4 圣诞树装饰
树形 dp 的过程比较好想，我认为难点在于建树和状态转移方程。下面是蔡大大为我们讲的笔记：
/*
dp[i][j]:第i个节点为根的树,里面j个装饰保持平衡,需要调整的次数
当i叶子节点没有装饰的时候
dp[i][0] = 0;
dp[i][1] = 1;
当i叶子节点有装饰的时候
dp[i][1] = 0;
dp[i][0] = 1;
对于其中一个树来讲
dp[i][w] 第i颗树有w个装饰
dp[i*2][w/2]
dp[i*2+1][w - w/2]
差值不超过1
v = dp[i*2][w/2] + dp[i*2+1][w-w/2];
v = min(v, dp[i*2][w-w/2] + dp[i*2+1][w/2])
dp[1][W] / 2;
*/
====================================================
好吧蔡老师说我写的敷衍，于是补一下：
我们需要调整圣诞树上装饰品的位置，使得每个非叶子节点的左右子树装饰品数量差不超过1。调整的目标是找到最少的移动次数。若无法满足条件，输出 impossible。
我们的核心思路是 dp + 记忆化搜索
- 状态定义
dp_{x\,w} 表示以节点 x 为根的子树中放置 w 个装饰品时，所需的最小调整次数。 - 状态转移
- 非叶子节点
递归计算左右子树的分配方案。若 w 为偶数，左右子树各分配 w/2；若 w 为奇数，有两种分配方式（左子树多 1 或右子树多 $1$），取较小值。 - 叶子节点
若 w > 1，无法满足条件（返回极大值）；否则调整次数为 abs(原装饰数 - w)。
- 非叶子节点
- 最终答案：根节点的 dp[1][总装饰数] / 2，因为每个移动操作会被两个叶子节点各计数一次。
讲解一下代码吧：
- 树结构解析：根据输入字符串构建二叉树，记录父子关系和叶子节点的初始装饰状态。
- 自底向上统计：计算每个节点的初始装饰数 sz[x]。
- 记忆化搜索：递归处理每个节点的分配情况，避免重复计算。
- 使用栈结构（
node[]数组）跟踪父节点，构建二叉树。
int n = 0, f = 0;
for (int i = 1; i <= len; i++) {
if (s[i] == '(') { // 新建节点
n++;
if (f) { // 链接父子节点
if (son[node[f]][0]) son[node[f]][1] = n;
else son[node[f]][0] = n;
fa[n] = node[f];
}
node[++f] = n; // 记录当前节点
}
if (s[i] == 'B') sz[n] = 1; // 叶子节点标记装饰
if (s[i] == ')') f--; // 返回父节点
}
- 非叶子节点递归处理子问题，叶子节点直接计算结果。
int dfs(int x, int w) {
if (dp[x].count(w)) return dp[x][w];
int v;
if (son[x][0]) { // 非叶子节点
v = dfs(son[x][0], w/2) + dfs(son[x][1], w - w/2);
if (w & 1) { // 奇数时两种分配方式取最小
v = min(v, dfs(son[x][0], w - w/2) + dfs(son[x][1], w/2));
}
v = min(v, n + 1); // 防止溢出
} else { // 叶子节点
if (w > 1) v = n + 1; // 无法满足
else v = abs(sz[x] - w); // 调整次数
}
return dp[x][w] = v;
}
- 主函数逻辑
// 统计初始装饰总数
for (int i = n; i; i--) sz[fa[i]] += sz[i];
// 计算根节点的调整次数
dfs(1, sz[1]);
if (dp[1][sz[1]] > n) cout << "impossible\n";
else cout << dp[1][sz[1]] / 2 << '\n';