CSP-S 2025 · 提高级第一轮真题

有 $5$ 个红色球和 $5$ 个蓝色球，它们除了颜色之外完全相同。将这 $10$ 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

在 KMP 算法中，对于模式串 P="abacaba"，其 next 数组（next[i] 定义为模式串 P[0...i] 最长公共前后缀的长度，且数组下标从 $0$ 开始）的值是什么？

对一个大小为 $16$（下标 $0$-$15$）的数组上构建满线段树。查询区间 [3, 11] 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？

将字符串 "cat"、"car"、"cart"、"case"、"dog"、"do" 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？

在一个大小为 $13$ 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(\text{key}) = \text{key} \bmod 13$。依次插入关键字 $18$、$26$、$35$、$9$、$68$、$74$。插入 $74$ 后，它最终被放置在哪个索引位置？

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权重等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权重为 $|7-3| = 4$。该图的最小生成树总权重是多少？

如果一棵二叉搜索树的后序遍历序列是 $2, 5, 4, 8, 12, 10, 6$，那么该树的前序遍历是什么？

一个 $0$-$1$ 背包问题，背包容量为 $20$。现有 $5$ 个物品，其重量和价值分别为 $7, 5, 4, 3, 6$ 和 $15, 12, 9, 7, 13$。装入背包的物品能获得的最大总价值是多少？

在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（$LCA$）是结点 $4$。那么下列哪个结点的 $LCA$ 组合是不可能出现的？

递归关系式 $T(n) = 2T(n/2) + O(n^2)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

在一个初始为空的最小堆（min-heap）中，依次插入元素 $20, 12, 15, 8, 10, 5$。然后连续执行两次"删除最小值"（delete-min）操作。请问此时堆顶元素是什么？

$1$ 到 $1000$ 之间，不能被 $2$、$3$、$5$ 中任意一个数整除的整数有多少个？

斐波那契数列的定义为 $F(0)=0$，$F(1)=1$，$F(n) = F(n-1) + F(n-2)$。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的。而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这种巨大差异的根本原因是？

有 $5$ 个独立的、不可抢占的任务 $A_1, A_2, A_3, A_4, A_5$ 需要在一台机器上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3, 4, 2, 5, 1$ 和 $5, 10, 3, 15, 11$。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  bool flag[27];
5  int n;
6  int p[27];
7  int ans = 0;
8  void dfs(int k) {
9      if (k == n + 1){
10          ++ ans;
11          return;
12      }
13      for (int i = 1; i <= n; ++i) {
14          if (flag[i]) continue;
15          if (k > 1 && i == p[k - 1] + 1) continue;
16          p[k] = i;
17          flag[i] = true;
18          dfs(k + 1);
19          flag[i] = false;
20      }
21      return;
22  }
23  int main() {
24      scanf("%d", &n);
25      dfs(1);
26      printf("%d\n", ans);
27      return 0;
28  }

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  #define ll long long
5  int cnt_broken = 0;
6  int cnt_check = 0;
7  int n, k;
8  inline bool check(int h) {
9      printf("now check:%d\n", h);
10      ++cnt_check;
11      if (cnt_broken == 2) {
12          printf("You have no egg!\n");
13          return false;
14      }
15      if (h >= k) {
16          ++cnt_broken;
17          return true;
18      } else {
19          return false;
20      }
21  }
22  inline bool assert_ans(int h) {
23      if (h == k) {
24          printf("You are Right using %d checks\n", cnt_check);
25          return true;
26      } else {
27          printf("Wrong answer!\n");
28          return false;
29      }
30  }
31  inline void guess1(int n) {
32      for (int i = 1; i <= n; ++i) {
33          if (check(i)) {
34              assert_ans(i);
35              return;
36          }
37      }
38  }
39  inline void guess2(int n) {
40      int w = 0;
41      for (w = 1; w * (w + 1) / 2 < n; ++w)
42      ;
43      for (int ti = w, nh = w;; --ti, nh += ti, nh = std::min(nh, n)) {
44          if (check(nh)) {
45              for (int j = nh - ti + 1; j < nh; ++j) {
46                  if (check(j)) {
47                      assert_ans(j);
48                      return;
49                  }
50              }
51              assert_ans(nh);
52              return;
53          }
54      }
55  }
56  int main() {
57      scanf("%d%d", &n, &k);
58      int t;
59      scanf("%d", &t);
60      if (t == 1) {
61          guess1(n);
62      } else {
63          guess2(n);
64      }
65      return 0;
66  }

1  #include <algorithm>
2  #include <cstdio>
3  #include <cstring>
4  #include <vector>
5  #define ll long long
6  int n, m;
7  std::vector<int> k, p;
8  inline int mpow(int x, int k) {
9      int ans = 1;
10      for (; k; k = k >> 1, x = x * x) {
11          if (k & 1)
12          ans = ans * x;
13      }
14      return ans;
15  }
16  std::vector<int> ans1, ans2;
17  int cnt1, cnt2;
18  inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
19      if (l > r) {
20          ++cnt;
21          ans.push_back(v);
22          return;
23      }
24      for (int i = 1; i <= m; ++i) {
25          dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
26      }
27      return;
28  }
29  std::vector<int> cntans1;
30  int main() {
31      scanf("%d%d", &n, &m);
32      k.resize(n + 1);
33      p.resize(n + 1);
34      for (int i = 1; i <= n; ++i) {
35          scanf("%d%d", &k[i], &p[i]);
36      }
37      dfs(ans1, cnt1, 1, n >> 1, 0);
38      dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
39      std::sort(ans1.begin(), ans1.end());
40      int newcnt1 = 1;
41      cntans1.push_back(1);
42      for (int i = 1; i < cnt1; ++i) {
43          if (ans1[i] == ans1[newcnt1 - 1]) {
44              ++cntans1[newcnt1 - 1];
45          } else {
46              ans1[newcnt1++] = ans1[i];
47              cntans1.push_back(1);
48          }
49      }
50      cnt1 = newcnt1;
51      std::sort(ans2.begin(), ans2.end());
52      int las = 0;
53      ll ans = 0;
54      for (int i = cnt2 - 1; i >= 0; --i) {
55          for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
56          ;
57          if (las < cnt1 && ans1[las] + ans2[i] == 0)
58          ans += cntans1[las];
59      }
60      printf("%lld\n", ans);
61      return 0;
62  }

（特殊最短路）给定一个含 $N$ 个点、$M$ 条边的带权无向图，边权非负。起点为 $S$，终点为 $T$。对于一条 $S$ 到 $T$ 的路径，可以在整条路径中，至多选择一条边作为"免费边"：当第一次经过这条被选中的边时，费用视为 $0$；如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从 $S$ 到 $T$ 的最小总费用。

以下代码求解了上述问题。试补全程序。

1  #include <algorithm>
2  #include <iostream>
3  #include <queue>
4  #include <vector>
5  using namespace std;
6 
7  const long long INF = 1e18;
8 
9  struct Edge {
10      int to;
11      int weight;
12  };
13 
14  struct State {
15      long long dist;
16      int u;
17      int used_freebie; // 0 for not used, 1 for used
18      bool operator>(const State &other) const {
19          return dist > other.dist;
20      }
21  };
22 
23  int main() {
24      int n, m, s, t;
25      cin >> n >> m >> s >> t;
26 
27      vector<vector<Edge>> adj(n + 1);
28      for (int i = 0; i < m; ++i) {
29          int u, v, w;
30          cin >> u >> v >> w;
31          adj[u].push_back({v, w});
32          adj[v].push_back({u, w});
33      }
34 
35      vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
36      priority_queue<State, vector<State>, greater<State>> pq;
37 
38      d[s][0] = 0;
39      pq.push({0, s, ①});
40 
41      while (!pq.empty()) {
42          State current = pq.top();
43          pq.pop();
44 
45          long long dist = current.dist;
46          int u = current.u;
47          int used = current.used_freebie;
48 
49          if (dist > ②) {
50              continue;
51          }
52 
53          for (const auto &edge : adj[u]) {
54              int v = edge.to;
55              int w = edge.weight;
56 
57              if (d[u][used] + w < ③) {
58                  ③ = d[u][used] + w;
59                  pq.push({③, v, used});
60              }
61 
62              if (used == 0) {
63                  if (④ < d[v][1]) {
64                      d[v][1] = ④;
65                      pq.push({d[v][1], v, 1});
66                  }
67              }
68          }
69      }
70 
71      cout << ⑤ << endl;
72      return 0;
73  }

工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有 $n$ 条生产线（编号 $0 \sim n-1$），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为 $1$），否则正常收货（记为 $0$）。受售后压力限制，在所有发货批次中，最多只能有 $k$ 次退货（即结果为 $1$ 的次数 $\le k$）。工厂的目标是，设计最少的间接测试轮数 $w$（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标，包含两部分：

i) 确定 $w$ 的最小值，并设计最优测试方案；

ii) 根据测试结果推断存在缺陷的生产线。该程序确定 $w$ 最小值的方法为：

由于不同的生产线故障时，测试应当返回不同的结果，因此 $w$ 轮测试的可能结果数不应少于生产线数量。

test_subset() 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第 $1$ 批次、最高位是第 $w$ 批次）；其实现在此处未给出。

试补全程序。

程序代码

1  #include <algorithm>
2  #include <cstddef>
3  #include <iostream>
4  #include <vector>
5  using namespace std;
6  long long comb(int w, int i) {
7      if (i < 0 || i > w) {
8          return 0;
9      }
10      long long res = 1;
11      for (int t = 1; t <= i; ++t) {
12          res = res * (w - t + 1) / t;
13      }
14      return res;
15  }
16  // 计算长度为 w、1 的个数 ≤ k 的码字总数
17  long long count_patterns(int w, int k) {
18      long long total = 0;
19      for (int t = 0; t <= min(w, k); ++t) {
20          total += comb(w, t);
21      }
22      return total;
23  }
24  // 抽象测试接口
25  int test_subset(const vector<vector<int>> &plan);
26  int solve(int n, int k) {
27      // === 第 1 步：求最小 w ===
28      int w = 1;
29      while (___①___) {
30          ++w;
31      }
32      cout << w << endl;
33      // === 第 2 步：生成测试方案 ===
34      vector<vector<int>> code(n, vector<int>(w, 0));
35      int idx = 0;
36      for (int ones = 0; ones <= k && idx < n; ++ones) {
37          vector<int> bits(w, 0);
38          fill(bits.begin(), bits.begin() + ones, 1);
39          do {
40              for (int b = 0; b < w; ++b) {
41                  code[idx][b] = bits[b];
42              }
43              ++idx;
44              if (idx >= n) {
45                  break;
46              }
47          } while (std::___②___);
48      }
49      vector<vector<int>> plan(w);
50      for (int i = 0; i < w; ++i) {
51          for (int j = 0; j < n; ++j) {
52              if (___③___) {
53                  plan[i].push_back(j);
54              }
55          }
56      }
57      // === 第 3 步：调用测试接口 ===
58      int signature = test_subset(plan);
59      // === 第 4 步：结果解码 ===
60      vector<int> sig_bits(w, 0);
61      for (int i = 0; i < w; ++i) {
62          if (___④___) {
63              sig_bits[i] = 1;
64          }
65      }
66      for (int j = 0; j < n; ++j) {
67          if (___⑤___) return j;
68      }
69  }
70  int main() {
71      int n,k;
72      cin >> n >> k;
73      int ans = solve();
74      cout << ans << endl;
75      return 0;
76  }