CSP 历年真题精讲 · 第 2 期

2019 年 CSP-S 提高级复赛（Day 1）

考试时间：2019 年 11 月 17 日 · 满分 400 · 时长 3.5 小时

题一：格雷码（code）

【题目描述】

格雷码是一个长度为 的二进制串序列 ，满足：

• 的第一个串是长度为 的全 0 串；
• 相邻两个串恰好只有一位不同；
• 第一个串和最后一个串也恰好只有一位不同。

例如 ，。

给定 和 （），输出 中的第 个串（从 0 开始编号）。

【输入格式】

一行两个整数 。

【输出格式】

一个长度为 的二进制串。

【样例】

输入：3 5
输出：111

【解题思路】

构造法 1 —— 镜像拼接：观察 的前 4 个串去掉首位，正好是 ；后 4 个串去掉首位，是 的镜像翻转再加 1 位前缀 1。

递归构造：设 已知，则

其中 是把 的顺序翻转。递推即可。

构造法 2 —— 数学公式：第 个格雷码等于 （ 与自身右移一位后的异或），结果就是第 个串的二进制。

这是最常用的 解法，利用了格雷码与二进制数之间的对应关系。

【参考代码（C++）】

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    long long g = k ^ (k >> 1);          // 格雷码公式
    string s;
    for (int i = n - 1; i >= 0; i--)    // 输出 n 位二进制
        s += ((g >> i) & 1) ? '1' : '0';
    cout << s << endl;
    return 0;
}

【参考代码（递归构造）】

#include <bits/stdc++.h>
using namespace std;

string gray(int n) {
    if (n == 1) return "01";            // G(1) = {0,1}
    string prev = gray(n - 1);
    string rev = prev;
    reverse(rev.begin(), rev.end());
    string res = "0" + prev + "1" + rev;
    return res;
}

int main() {
    long long n, k;
    cin >> n >> k;
    cout << gray(n)[k] << endl;          // 输出第 k 个串（直接下标）
    return 0;
}

【知识点】

• 格雷码的递归构造（镜像翻转）
• 格雷码 ↔ 二进制的公式转换：
• 位运算技巧（异或、右移）
• 边界： 可达 64，需要 long long

题二：括号树（brackets）

【题目描述】

给定一棵节点数为 的树，根节点为 1，每个节点上有一个字符 ( 或 )。

路径 的"权值"定义为：路径上所有字符依次拼接得到的串中，合法括号子串（形如 ()、(())、(()()) 等）的个数。

求所有以节点 1 为起点的路径（路径上每个节点都被走到）的权值之和，答案对 取模。

【输入格式】

• 第一行整数 ；
• 第二行长度为 的字符串，第 个字符表示节点 的括号；
• 接下来 行，每行两个整数 表示一条树边。

【输出格式】

一个整数：所有以根为起点的路径的权值之和 。

【样例】

输入：
5
(()()
1 2
2 3
3 4
4 5

输出：46

【解题思路】

经典题，关键观察：

1. 栈匹配：DFS 维护一个栈，记录从根到当前节点路径上未匹配的左括号所在深度。
2. 当遇到 ) 时：若栈不为空，说明可以与栈顶的 ( 匹配——形成一个新的合法括号对，新增的合法子串数 = 栈的大小（每个栈中剩余的 ( 都能与这个 ) 配对出新的子串）。
3. 遇到 ( 时：入栈。
4. 回溯时：要把刚刚入栈 / 出栈的元素恢复。

核心递推：

• 设 = 从根到 的路径上合法括号子串总数；
• 进入节点 时，先继承父节点的栈与累计答案；
• 若节点 的字符是 ) 且栈非空，弹出栈顶；新增贡献 = 栈中剩余元素数；
• 把新增贡献累加到 ；
• 子节点的 值 = 父节点 值 + 自己新增贡献。

【参考代码（C++）】

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 5e5 + 5;

int n;
char ch[MAXN];
vector<int> g[MAXN];
int stk[MAXN], top_;                    // 模拟栈：存深度下标
long long ans = 0;

void dfs(int u, int fa, long long pre) {
    long long cur = pre;
    if (ch[u] == '(') {
        stk[++top_] = u;                // 入栈
    } else {                            // ch[u] == ')'
        if (top_ > 0) {
            top_--;                     // 出栈：匹配一个 '('
            cur = (cur + top_) % MOD;   // 栈中剩余的 '(' 都贡献新子串
        }
    }
    ans = (ans + cur) % MOD;
    for (int v : g[u])
        if (v != fa) dfs(v, u, cur);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> ch[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    top_ = 0;
    dfs(1, 0, 0);
    cout << ans % MOD << endl;
    return 0;
}

【复杂度】

【知识点】

• DFS + 手动栈：括号匹配的状态维护
• 树形 DP：从父节点向子节点递推
• 模运算（long long 防止乘法溢出）
• 关键技巧：) 与栈顶 ( 匹配时，新增贡献 = 栈剩余元素数

题三：树上的数（tree）

【题目描述】

给定一棵 个节点的树，每个节点有一个数字 。你可以进行任意次操作，每次选一条边并翻转该边两端节点上的数字（即交换）。求最终能否通过若干次操作使整棵树上的数字严格单调递增（按节点编号顺序）。

【输入格式】

• 第一行整数 ；
• 第二行 个整数 ；
• 接下来 行，每行两个整数 。

【输出格式】

若能则输出 Yes，否则输出 No。

【样例】

输入：
4
1 3 2 4
1 2
2 3
2 4

输出：Yes

【解题思路】

此题是 CSP-S 2019 中最难的一题，思路分三步：

第 1 步：找到"必须固定"的节点

排序后数组 ，每个 对应一个目标值 （ 是 在原数组中的秩）。

如果存在某个值 ，它出现在 中多个不同的连通块里，那么这些块之间没有边连通，这些块里的 永远无法归位，判定 No。

做法：对每个值 ，把所有 的节点提取出来，看它们是否在同一连通块。

第 2 步：构造调整方案

排序后，整棵树按节点序号形成一个新树。每个连通块（颜色相同的目标值）可以视为一个"超级节点"——但实际上我们只需证明：

如果第 1 步通过了，就一定能通过翻转边达成目标。

构造方法：

1. 把节点按目标值排序后遍历。
2. 维护一个集合 S = 当前"已固定"的节点集合。
3. 对每个目标值 ，把 的节点加入 S，然后判断 S 是否连通——这对应调整路径是否存在的判定。

第 3 步：路径上数字的归属

每个节点的"原始值"需要找到自己归属的目标位置。每次翻转边时，沿着这条边做一次交换——这相当于把"两个节点的当前值"互换。

最终条件：

对每个节点 ，设它的目标值是 。从 到所有 的节点必须都在同一连通块。

【参考代码（C++）骨架】

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
int n;
int a[MAXN], b[MAXN], p[MAXN];
vector<int> g[MAXN];
int fa[MAXN], dep[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

// Step 1: 对每个值 v，验证 a_i=v 的节点是否在同一连通块
bool check1() {
    // 按值分组
    map<int, vector<int>> pos;
    for (int i = 1; i <= n; i++) pos[a[i]].push_back(i);
    for (auto& kv : pos) {
        vector<int>& v = kv.second;
        if (v.size() <= 1) continue;
        // 检查 v[0], v[1], ... 是否在同一连通块
        // 用并查集或 LCA 判定
    }
    return true;
}

// Step 2: 按目标值遍历，构造调整序列
bool check2() {
    // 用并查集维护"已固定"集合 S 的连通性
    // 详见官方题解
    return true;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cout << (check1() && check2() ? "Yes" : "No") << endl;
    return 0;
}

完整代码较长，可参考洛谷 P5659 / CCF 官方题解。

【知识点】

• 树形问题转化为图论问题
• 连通块判定：用并查集或 LCA
• 排序 + 目标位置映射（秩）
• 构造性证明（不是单纯判定）
• 关键观察：等值节点必须同块

题四：树的重心（centroid）

【题目描述】

一棵 个节点的树（节点 1 为根）有若干次"重心操作"：每次选一条边 （ 是 的父节点），把以 为根的子树整体删掉。

给定一个长度为 的操作序列，每个元素是某条边的编号，依次执行后，最终剩下的树（可能只剩一个节点）称为"结果树"。

要求输出最终剩下的节点数。

【输入格式】

• 第一行整数 ；
• 接下来 行，每行三个整数 ，第 行代表编号为 的边（ 仅用于建树时辅助）；
• 最后一行 个整数，表示操作序列中各条边的编号（按顺序）。

【输出格式】

一个整数：最终剩下的节点数。

【样例】

输入：
5
1 2 1
1 3 1
2 4 1
2 5 1
3 4

输出：2

【解题思路】

核心观察：每次删除的是一条边对应的那棵子树，删完后父节点那一侧保留。

关键性质：被删的子树，永远不可能再恢复（操作不可逆）。所以最终剩下的节点 = 初始节点数 - 所有被删除过的子树节点数之和（去重）。

思路 A：倒序并查集

1. 先把所有操作标记为"被删除"，然后倒序遍历操作序列，每一步把对应边连回去。
2. 维护每个连通块的节点数。
3. 初始时所有节点都"被删"，倒序恢复时合并连通块，最终连通块大小就是剩余节点数。

思路 B：直接 DFS 模拟

用 cut[i] 标记边 是否被删除，DFS 时若进入被删除的子树就直接返回。

但更高效的是 思路 A，时间复杂度 。

【参考代码（思路 A：倒序并查集）】

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 5;

int n;
int U[MAXN], V[MAXN];           // 第 i 条边的两端
vector<int> g[MAXN];
int fa[MAXN];
long long sz[MAXN];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        U[i] = u; V[i] = v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // 读取操作序列
    vector<int> ops(n - 2);
    for (int i = 0; i < n - 2; i++) cin >> ops[i];

    // 初始化并查集：每个节点独立
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = 1;
    }

    // 标记被删边
    vector<bool> cut(n, true);   // cut[i] 表示第 i 条边是否被删除
    for (int eid : ops) cut[eid] = true;

    // 倒序恢复
    for (int i = (int)ops.size() - 1; i >= 0; i--) {
        int eid = ops[i];
        cut[eid] = false;
        unite(U[eid], V[eid]);
    }

    // 找包含节点 1 的连通块大小
    cout << sz[find(1)] << endl;
    return 0;
}

边界： 次操作中，每条边至多出现一次（也可能不出现）。并查集的 sz 维护的是每个连通块的节点数。

【复杂度】

【知识点】

• 倒序并查集：解决"删除再恢复"问题的经典套路
• 树的离线处理
• 子树删除 = 边删除（无向边只保留一端）
• 路径压缩 + 按秩合并

本期小结

下期预告：2020 CSP-J 入门级复赛 4 题（优秀的拆分 / 直播获奖 / 表达式 / 方格取数），敬请期待。