一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 阅读下面程序片段：

   vector<pair<int,int> > a = {{1, 4}, {2, 5}, {3, 6}};
   for (auto p : a) p.first += p.second;
   for (auto &p : a) {
       p.second += p.first;
       if (p.second & 1) ++p.first;
   }
   int code = 0, sum = 0;
   for (auto p : a) {
       code = code * 10 + p.first;
       sum += p.first * p.second;
   }
   cout << code << " " << sum << "\n";
   

   输出结果为（）{{ select(1) }}

• 123 56
• 234 67
• 6810 167
• 234 56

2. 设 mask = 0b111010。执行如下枚举：

   int cnt = 0, first = -1, third = -1, good = 0;
   for (int s = mask; s; s = (s - 1) & mask) {
       ++cnt;
       if (cnt == 1) first = s;
       if (cnt == 3) third = s;
       if ((s & 0b1010) == 0b1010) ++good;
   }
   

   cnt、first、third、good 的值分别为（）{{ select(2) }}

• 15, 58, 50, 4
• 16, 58, 50, 4
• 15, 58, 56, 8
• 31, 58, 50, 4

3. 函数如下：

   long long qpow(long long a, long long b, long long mod) {
       long long ans = 1;
       int loop = 0, mul = 0;
       while (b) {
           if (b & 1) ans = ans * a % mod, ++mul;
           a = a * a % mod;
           b >>= 1;
           ++loop;
       }
       cout << ans << " " << loop << " " << mul << "\n";
       return ans;
   }
   

   调用 qpow(11, 23, 97) 时，输出为（）{{ select(3) }}

• 44 4 5
• 35 5 4
• 44 5 4
• 11 5 4

4. 有 8 个元素，初始每个元素各自成集合。并查集使用路径压缩与按集合大小合并，若大小相等则把第二个根接到第一个根。依次执行：

   merge(1,2), merge(3,4), merge(2,3), merge(5,6),
   merge(7,8), merge(6,8), merge(4,8), merge(1,5)
   

   成功合并次数、失败合并次数、最后点 8 所在集合大小分别为（）{{ select(4) }}

• 6, 2, 8
• 7, 1, 4
• 8, 0, 8
• 7, 1, 8

5. 无向图有 6 个点，边按输入顺序如下：

   1: 1-2(3)
   2: 1-3(1)
   3: 2-3(2)
   4: 2-4(4)
   5: 3-4(4)
   6: 3-5(6)
   7: 4-5(5)
   8: 4-6(7)
   9: 5-6(2)
   10: 2-6(8)
   

   Kruskal 算法按边权升序、边权相同按输入编号升序处理。该图最小生成树权值和、是否唯一、严格大于最小生成树权值的次小生成树权值分别为（）{{ select(5) }}

• 14，唯一，15
• 14，不唯一，15
• 15，不唯一，16
• 14，不唯一，14

6. 数组 $a[1..10]=\{9,3,7,1,6,2,8,5,4,10\}$。用稀疏表查询区间最小值，分别查询 $[2,9]$ 和 $[5,10]$。两次查询使用的 $k=\lfloor\log_2(len)\rfloor$ 以及两个最小值之和分别为（）{{ select(6) }}

• k 为 2 和 2，和为 3
• k 为 3 和 2，和为 3
• k 为 3 和 2，和为 5
• k 为 3 和 3，和为 3

7. 一棵以 1 为根的带权树有边：

   1-2(3), 1-3(2), 2-4(5), 2-5(1),
   3-6(4), 6-7(6), 6-8(2), 5-9(7)
   

   则 LCA(9,7)、点 9 到点 7 的距离、点 9 的第 3 级祖先分别为（）{{ select(7) }}

• 1, 22, 1
• 2, 23, 1
• 1, 23, 1
• 1, 23, 2

8. 有向无环图边及权值为：

   1->2(2), 1->3(2), 2->4(3), 3->4(3),
   2->5(4), 4->5(1), 3->6(5), 5->6(2)
   

   从点 1 到点 6 的不同路径总数、最长路径权值、最长路径条数分别为（）{{ select(8) }}

• 3, 8, 2
• 4, 7, 1
• 4, 8, 3
• 5, 8, 3

9. 字符串 abacaba 的回文子串总数与不同回文子串个数分别为（）{{ select(9) }}

• 12, 7
• 12, 6
• 10, 7
• 9, 6

10. 独立掷两次公平六面骰，令 $Z$ 为两次点数差的绝对值，令事件 $A$ 表示两次点数中至少有一次不小于 5。则 $36E(Z)$ 与 $36P(A)$ 分别为（）{{ select(10) }}

• 35, 20
• 70, 16
• 35, 16
• 70, 20

11. 数列满足 $a_0=1,a_1=2,a_n=2a_{n-1}+a_{n-2}$。则 $a_7$ 与 $a_7\bmod 13$ 分别为（）{{ select(11) }}

• 169, 0
• 408, 5
• 408, 6
• 985, 10

12. 在一个 $30\times40$ 的网格中做 BFS，状态需要记录当前位置、已经获得的钥匙集合、步数奇偶性、是否已经使用一次性传送门。若钥匙总数为 $k$，本题中 $k=4$，钥匙集合用二进制掩码表示。最多可能有的状态数以及渐进复杂度最接近（）{{ select(12) }}

• 19200, O(nm)
• 38400, O(nm2^k)
• 76800, O(nm)
• 76800, O(nm2^k)

13. 在模 17 意义下，5 的逆元，以及同时满足

    5x ≡ 3 (mod 17)
    x ≡ 2 (mod 3)
    

    的最小非负整数 x 分别为（）{{ select(13) }}

• 7, 21
• 7, 38
• 10, 38
• 7, 4

14. $840$ 的欧拉函数值 $\varphi(840)$，以及 $1..840$ 中与 $840$ 不互质的整数个数分别为（）{{ select(14) }}

• 192, 192
• 240, 600
• 192, 648
• 288, 552

15. 对一个有 $n$ 个点、$m$ 条无向边的图做 BFS，状态为 $(点编号, parity)$，其中 $parity$ 只有 0 和 1 两种取值。若显式构造扩展图，则扩展图的点数、按有向边计的边数、BFS 复杂度最接近（）{{ select(15) }}

• 2n, 4m, O(n+m)
• 2n, 2m, O(n+m)
• n, 4m, O(nm)
• 2n, 4m, O(2^n)

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填对，错误填错；除特殊说明外，判断题1.5分，选择题3分，标注分值题按标注计分，共计40分）

(1)

#include <bits/stdc++.h>
using namespace std;
struct Edge { int u, v, w, id; bool used; };
int fa[30];
vector<pair<int,int> > tree[30];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool unite(int u, int v) {
    int ru = find(u), rv = find(v);
    if (ru == rv) return false;
    fa[rv] = ru;
    return true;
}
int pathMax(int u, int target, int parent) {
    if (u == target) return 0;
    for (auto e : tree[u]) {
        int v = e.first, w = e.second;
        if (v == parent) continue;
        int t = pathMax(v, target, u);
        if (t != -1) return max(t, w);
    }
    return -1;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> e(m);
    for (int i = 0; i < m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].id = i + 1;
        e[i].used = false;
    }
    for (int i = 1; i <= n; ++i) fa[i] = i;
    sort(e.begin(), e.end(), [](const Edge &a, const Edge &b) {
        if (a.w != b.w) return a.w < b.w;
        return a.id < b.id;
    });
    int total = 0, code = 0;
    vector<int> chosen;
    for (auto &ed : e) {
        if (unite(ed.u, ed.v)) {
            ed.used = true;
            total += ed.w;
            code = code * 10 + ed.id;
            chosen.push_back(ed.id);
            tree[ed.u].push_back({ed.v, ed.w});
            tree[ed.v].push_back({ed.u, ed.w});
        }
    }
    bool unique = true;
    int best = 1e9;
    for (auto ed : e) if (!ed.used) {
        int mx = pathMax(ed.u, ed.v, 0);
        int delta = ed.w - mx;
        if (delta == 0) unique = false;
        if (delta > 0) best = min(best, delta);
    }
    cout << total << " " << chosen.size() << " " << code << "\n";
    cout << (unique ? "YES" : "NO") << " " << best << " " << total + best << "\n";
    return 0;
}

给定输入：

6 10
1 2 3
1 3 1
2 3 2
2 4 4
3 4 4
3 5 6
4 5 5
4 6 7
5 6 2
2 6 8

16. 第 58-63 行通过枚举非树边，判断是否存在另一棵同权值最小生成树。（）{{ select(16) }}

• 对
• 错

17. 若某条非树边 ed 满足 ed.w == pathMax(ed.u, ed.v, 0)，则最小生成树一定不唯一。（）{{ select(17) }}

• 对
• 错

18. 对给定输入，编号 5 的边 3-4(4) 使 unique 变为 false。（2分）（）{{ select(18) }}

• 对
• 错

19. 对给定输入，程序输出为（3分）（）{{ select(19) }}

• 14 5 23947
  NO 1 15
  

• 14 5 23947
  YES 1 15
  

• 15 5 23947
  NO 0 15
  

• 14 4 2394
  NO 1 15
  

20. 若从输入中删除编号 5 的边 3 4 4，其他边不变，则第二行输出变为（3分）（）{{ select(20) }}

• YES 1 15
• NO 1 15
• YES 2 16
• NO 0 14

21. 设 n 为点数、m 为边数，该程序的总时间复杂度最接近（3分）（）{{ select(21) }}

• O(m log m + mn)
• O(m log n)
• O(n^2 log m)
• O(2^m)

(2)

#include <bits/stdc++.h>
using namespace std;
struct Edge { int v, w; };
const int MAXN = 1005;
int n, sub[MAXN];
long long down[MAXN], ans[MAXN];
vector<Edge> g[MAXN];
void dfs1(int u, int fa) {
    sub[u] = 1;
    down[u] = 0;
    for (auto e : g[u]) {
        int v = e.v, w = e.w;
        if (v == fa) continue;
        dfs1(v, u);
        sub[u] += sub[v];
        down[u] += down[v] + 1LL * sub[v] * w;
    }
}
void dfs2(int u, int fa) {
    for (auto e : g[u]) {
        int v = e.v, w = e.w;
        if (v == fa) continue;
        ans[v] = ans[u] + 1LL * (n - 2 * sub[v]) * w;
        dfs2(v, u);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs1(1, 0);
    ans[1] = down[1];
    dfs2(1, 0);
    int best = 1;
    long long code = 0;
    for (int i = 1; i <= n; ++i) {
        if (ans[i] < ans[best]) best = i;
        code += 1LL * i * ans[i];
    }
    cout << down[1] << " " << ans[4] << " " << ans[7] << "\n";
    cout << best << " " << ans[best] << " " << code << "\n";
    return 0;
}

给定输入：

7
1 2 3
1 3 2
2 4 4
2 5 1
3 6 5
6 7 2

22. down[1] 等于点 1 到所有点的加权距离之和。（）{{ select(22) }}

• 对
• 错

23. 第 26 行换根到儿子 v 时，v 子树内的点距离减少 w，其余点距离增加 w。（）{{ select(23) }}

• 对
• 错

24. 若所有边权同时乘以 2，则 best 一定不变，且所有 ans[i] 同时乘以 2。（2分）（）{{ select(24) }}

• 对
• 错

25. 对给定输入，程序输出为（3分）（）{{ select(25) }}

• 32 55 59
  1 32 1331
  

• 32 55 57
  1 32 1317
  

• 35 55 59
  2 35 1331
  

• 32 54 59
  1 32 1331
  

26. 若仅把边 3 6 5 的权值改为 1，则新的 ans[7] 为（3分）（）{{ select(26) }}

• 31
• 35
• 39
• 43

27. 该程序的总时间复杂度为（2分）（）{{ select(27) }}

• O(n)
• O(n log n)
• O(n^2)
• O(2^n)

(3)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<pair<int,int> > seg;
    vector<int> xs;
    for (int i = 0; i < n; ++i) {
        int l, r, lc, rc;
        cin >> l >> r >> lc >> rc;
        int L = l + (lc ? 0 : 1);
        int R = r + (rc ? 1 : 0);
        if (L < R) {
            seg.push_back({L, R});
            xs.push_back(L);
            xs.push_back(R);
        }
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    vector<int> diff(xs.size() + 1, 0);
    for (auto p : seg) {
        int L = lower_bound(xs.begin(), xs.end(), p.first) - xs.begin();
        int R = lower_bound(xs.begin(), xs.end(), p.second) - xs.begin();
        ++diff[L];
        --diff[R];
    }
    long long covered = 0, maxLen = 0;
    int cur = 0, maxLayer = 0, maxParts = 0;
    for (int i = 0; i + 1 < (int)xs.size(); ++i) {
        cur += diff[i];
        int len = xs[i + 1] - xs[i];
        if (cur > 0) covered += len;
        if (cur > maxLayer) {
            maxLayer = cur;
            maxLen = len;
            maxParts = 1;
        } else if (cur == maxLayer) {
            maxLen += len;
            ++maxParts;
        }
    }
    cout << covered << " " << maxLayer << " " << maxLen << "\n";
    cout << xs.front() << " " << xs.back() << " " << maxParts << "\n";
    return 0;
}

每个输入区间为整数区间，lc=1 表示左端点闭合，rc=1 表示右端点闭合。程序把区间归一化为左闭右开区间 [L,R) 后统计整数点覆盖情况；maxParts 统计达到最大覆盖层数的压缩小段数量，而不是合并后的连续区间块数。本题给定输入保证至少存在一个非空归一化区间。给定输入：

5
1 5 1 0
2 7 1 1
4 6 0 1
6 9 1 0
8 10 0 1

28. 输入 4 6 0 1 会被归一化为 [5,7)。（）{{ select(28) }}

• 对
• 错

29. 对给定输入，半开段 [6,7) 上的覆盖层数为 3。（）{{ select(29) }}

• 对
• 错

30. 第 31-43 行中，cur += diff[i] 必须在统计 [xs[i], xs[i+1]) 之前执行。（2分）（）{{ select(30) }}

• 对
• 错

31. 对给定输入，程序输出为（3分）（）{{ select(31) }}

• 10 3 1
  1 11 1
  

• 10 2 5
  1 11 3
  

• 9 3 1
  1 10 1
  

• 10 3 2
  1 11 2
  

32. 若仅将第三个区间 4 6 0 1 改为 4 6 1 1，则第一行输出变为（5分）（）{{ select(32) }}

• 10 3 1
• 10 3 2
• 11 3 2
• 10 4 1

三、完善程序（单选题，每小题 3 分，共计 30 分）

(1)（路径长度与最大边权累计）

给定一棵 n 个点的带权树和 q 次询问。每次询问两个点 u,v，要求累计它们的路径长度，并累计路径上最大边权，最后输出累计的结果。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int LOG = 20;
struct Edge { int to, w; };
int n, q, dep[MAXN], up[MAXN][LOG], mx[MAXN][LOG];
long long distRoot[MAXN];
vector<Edge> g[MAXN];
void dfs(int u, int fa, int wToFa) {
    up[u][0] = fa;
    mx[u][0] = wToFa;
    dep[u] = dep[fa] + 1;
    for (int j = 1; j < LOG; ++j) {
        up[u][j] = ____①____;
        mx[u][j] = ____②____;
    }
    for (auto e : g[u]) {
        if (e.to == fa) continue;
        distRoot[e.to] = distRoot[u] + e.w;
        dfs(e.to, u, e.w);
    }
}
pair<int,int> lcaAndMax(int a, int b) {
    int best = 0;
    if (dep[a] < dep[b]) swap(a, b);
    int d = dep[a] - dep[b];
    for (int j = 0; j < LOG; ++j) {
        if (____③____) {
            best = max(best, mx[a][j]);
            a = up[a][j];
        }
    }
    if (a == b) return {a, best};
    for (int j = LOG - 1; j >= 0; --j) {
        if (____④____) {
            best = max(best, max(mx[a][j], mx[b][j]));
            a = up[a][j];
            b = up[b][j];
        }
    }
    best = max(best, max(mx[a][0], mx[b][0]));
    return {up[a][0], best};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, 0, 0);
    long long totalDist = 0, totalMax = 0;
    while (q--) {
        int u, v;
        cin >> u >> v;
        auto t = lcaAndMax(u, v);
        totalDist += ____⑤____;
        totalMax += t.second;
    }
    cout << totalDist << " " << totalMax << "\n";
    return 0;
}

33. ① 处应填（）{{ select(33) }}

• up[up[u][j - 1]][j - 1]
• up[u][j - 1] + (1 << j)
• fa + j
• up[fa][j]

34. ② 处应填（）{{ select(34) }}

• mx[u][j - 1] + mx[up[u][j - 1]][j - 1]
• max(mx[u][j - 1], mx[up[u][j - 1]][j - 1])
• mx[fa][j]
• wToFa

35. ③ 处应填（）{{ select(35) }}

• dep[a] == dep[b]
• d & (1 << j)
• up[a][j] == up[b][j]
• mx[a][j] > best

36. ④ 处应填（）{{ select(36) }}

• up[a][j] == up[b][j]
• mx[a][j] != mx[b][j]
• dep[up[a][j]] < dep[up[b][j]]
• up[a][j] != up[b][j]

37. ⑤ 处应填（）{{ select(37) }}

• distRoot[u] + distRoot[v] - 2 * distRoot[t.first]
• distRoot[u] - distRoot[v]
• distRoot[t.second]
• dep[u] + dep[v] - dep[t.first]

(2)（DAG最长路径与条数）

给定一个有向无环图，每条边有非负权值，且保证点 1 可以到达点 $n$。求从点 1 到点 $n$ 的最长路径长度、达到该长度的路径条数，以及在这些最长路径中使用边数的最小值。路径条数对 $1000000007$ 取模。

#include <bits/stdc++.h>
using namespace std;
const long long NEG = -(1LL << 60);
const long long MOD = 1000000007;
const int INF = 1e9;
struct Edge { int to, w; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<Edge> > g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        ++indeg[v];
    }
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (____①____) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (auto e : g[u]) {
            if (____②____) q.push(e.to);
        }
    }
    if (____③____) {
        cout << "CYCLE\n";
        return 0;
    }
    vector<long long> dp(n + 1, NEG), ways(n + 1, 0);
    vector<int> cntEdge(n + 1, INF);
    dp[1] = 0;
    ways[1] = 1;
    cntEdge[1] = 0;
    for (int u : order) {
        if (dp[u] == NEG) continue;
        for (auto e : g[u]) {
            long long cand = dp[u] + e.w;
            int edges = cntEdge[u] + 1;
            if (____④____) {
                dp[e.to] = cand;
                ways[e.to] = ways[u];
                cntEdge[e.to] = edges;
            } else if (____⑤____) {
                ways[e.to] = (ways[e.to] + ways[u]) % MOD;
                cntEdge[e.to] = min(cntEdge[e.to], edges);
            }
        }
    }
    cout << dp[n] << " " << ways[n] << " " << cntEdge[n] << "\n";
    return 0;
}

38. ① 处应填（）{{ select(38) }}

• indeg[i] == 0
• indeg[i] == 1
• g[i].empty()
• i == n

39. ② 处应填（）{{ select(39) }}

• indeg[e.to] == 0
• --indeg[e.to] == 0
• indeg[u]-- == 0
• ++indeg[e.to] == 1

40. ③ 处应填（）{{ select(40) }}

• order.empty()
• m == 0
• (int)order.size() != n
• dp[n] == NEG

41. ④ 处应填（）{{ select(41) }}

• cand > dp[e.to]
• cand < dp[e.to]
• ways[e.to] == 0
• edges < cntEdge[e.to]

42. ⑤ 处应填（）{{ select(42) }}

• cand > dp[e.to]
• cand == dp[e.to]
• dp[u] == NEG
• ways[u] == 0