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

在 Linux 系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（ ）

假设一个长度为 $n$ 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ）

在 C++ 中，以下哪个函数调用会造成栈溢出？（ ）

在一场比赛中，有 $10$ 名选手参加，前三名将获得金、银、铜牌。若不允许并列，且每名选手只能获得一枚奖牌，则不同的颁奖方式共有多少种？

下面哪个数据结构最适合实现先进先出（FIFO）的功能？

已知 $f(1) = 1$，且对于 $n \ge 2$ 有 $f(n) = f(n - 1) + f(\lfloor n/2 \rfloor)$，则 $f(4)$ 的值为（ ）。

假设有一个包含 $n$ 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？（ ）

对数组进行二分查找的过程中，以下哪个条件必须满足？（ ）

考虑一个自然数 $n$ 以及一个模数 $m$，你需要计算 $n$ 的逆元（即 $n$ 在模 $m$ 意义下的乘法逆元）。下列哪种算法最为适合？

在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 $n$ 个键值对，表的装载因子为 $a$（$0 < a \le 1$）。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为？

假设有一棵 $h$ 层的完全二叉树，该树最多包含多少个结点？

设有一个有 $10$ 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为 $4$ 的环？

对于一个整数 $n$，定义 $f(n)$ 为 $n$ 的各位数字之和。问使 $f(f(x)) = 10$ 的最小自然数 $x$ 是多少？

设有一个长度为 $n$ 的 $01$ 字符串，其中有 $k$ 个 $1$。每次操作可以交换相邻两个字符。在最坏情况下将这 $k$ 个 $1$ 移到字符串最右边所需要的交换次数是多少？

如图是一张包含 $7$ 个顶点的有向图。如果要删除其中一些边，使得从节点 $1$ 到节点 $7$ 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？

1  #include <iostream>
2  using namespace std;
3 
4  const int N = 1000;
5  int c[N];
6 
7  int logic(int x, int y) {
8      return (x & y) ^ ((x ^ y) | (~x & y));
9  }
10  void generate(int a, int b, int *c) {
11      for (int i = 0; i < b; i++) {
12          c[i] = logic(a, i) % (b + 1);
13      }
14  }
15  void recursion(int depth, int *arr, int size) {
16      if (depth <= 0 || size <= 1) return;
17      int pivot = arr[0];
18      int i = 0, j = size - 1;
19      while (i <= j) {
20          while (arr[i] < pivot) i++;
21          while (arr[j] > pivot) j--;
22          if (i <= j) {
23              int temp = arr[i];
24              arr[i] = arr[j];
25              arr[j] = temp;
26              i++; j--;
27          }
28      }
29      recursion(depth - 1, arr, j + 1);
30      recursion(depth - 1, arr + i, size - i);
31  }
32 
33  int main() {
34      int a, b, d;
35      cin >> a >> b >> d;
36      generate(a, b, c);
37      recursion(d, c, b);
38      for (int i = 0; i < b; ++i) cout << c[i] << " ";
39      cout << endl;
40  }

1   #include <iostream>
2  #include <string>
3  using namespace std;
4 
5  const int P = 998244353, N = 1e4+10, M = 20;
6  int n, m;
7  string s;
8  int dp[1<<M];
9 
10  int solve() {
11      dp[0] = 1;
12      for (int i = 0; i < n; ++i) {
13          for (int j = (1<<(m-1))-1; j >= 0; --j) {
14              int k = (j<<1)|(s[i]-'0');
15              if (j != 0 || s[i] == '1')
16                  dp[k] = (dp[k] + dp[j]) % P;
17          }
18      }
19      int ans = 0;
20      for (int i = 0; i < (1<<m); ++i) {
21          ans = (ans + 1ll * i * dp[i]) % P;
22      }
23      return ans;
24  }
25  int solve2() {
26      int ans = 0;
27      for (int i = 0; i < (1<<n); ++i) {
28          int cnt = 0;
29          int num = 0;
30          for (int j = 0; j < n; ++j) {
31              if (i & (1<<j)) {
32                  num = num * 2 + (s[j]-'0');
33                  cnt++;
34              }
35          }
36          if (cnt <= m) (ans += num) %= P;
37      }
38      return ans;
39  }
40 
41  int main() {
42      cin >> n >> m;
43      cin >> s;
44      if (n <= 20) {
45          cout << solve2() << endl;
46      }
47      cout << solve() << endl;
48      return 0;
49  }

1   #include <iostream>
2  #include <cstring>
3  #include <algorithm>
4  using namespace std;
5 
6  const int maxn = 1000000+5;
7  const int P1 = 998244353, P2 = 1000000007;
8  const int B1 = 2, B2 = 31;
9  const int K1 = 0, K2 = 13;
10 
11  typedef long long ll;
12 
13  int n;
14  bool p[maxn];
15  int p1[maxn], p2[maxn];
16 
17  struct H {
18      int h1, h2, l;
19      H(bool b = false) {
20          h1 = b + K1;
21          h2 = b + K2;
22          l = 1;
23      }
24      H operator + (const H & h) const {
25          H hh;
26          hh.l = l + h.l;
27          hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
28          hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
29          return hh;
30      }
31      bool operator == (const H & h) const {
32          return l == h.l && h1 == h.h1 && h2 == h.h2;
33      }
34      bool operator < (const H & h) const {
35          if (l != h.l) return l < h.l;
36          else if (h1 != h.h1) return h1 < h.h1;
37          else return h2 < h.h2;
38      }
39  } h[maxn];
40 
41  void init() {
42      memset(p, 1, sizeof(p));
43      p[0] = p[1] = false;
44      p1[0] = p2[0] = 1;
45      for (int i = 1; i <= n; ++i) {
46          p1[i] = (1ll * B1 * p1[i-1]) % P1;
47          p2[i] = (1ll * B2 * p2[i-1]) % P2;
48          if (!p[i]) continue;
49          for (int j = 2 * i; j <= n; j += i) {
50              p[j] = false;
51          }
52      }
53  }
54 
55  int solve() {
56      for (int i = n; i; --i) {
57          h[i] = H(p[i]);
58          if (2 * i + 1 <= n) {
59              h[i] = h[2 * i] + h[i] + h[2 * i + 1];
60          } else if (2 * i <= n) {
61              h[i] = h[2 * i] + h[i];
62          }
63      }
64      cout << h[1].h1 << endl;
65      sort(h + 1, h + n + 1);
66      int m = unique(h + 1, h + n + 1) - (h + 1);
67      return m;
68  }
69 
70  int main() {
71      cin >> n;
72      init();
73      cout << solve() << endl;
74  }

（序列合并）问题：有两个长度为 $N$ 的单调不降序列 $A$ 和 $B$，序列的每个元素都是小于 $10^9$ 的非负整数。在 $A$ 和 $B$ 中各取一个数相加可以得到 $N^2$ 个和，求其中第 $K$ 小的和。上述参数满足 $N \le 10^5$ 和 $1 \le K \le N^2$。

1  #include <iostream>
2  using namespace std;
3 
4  const int maxn = 100005;
5 
6  int n;
7  long long k;
8  int a[maxn], b[maxn];
9 
10  int* upper_bound(int *a, int *an, int ai) {
11      int l = 0, r = ①;
12      while (l < r) {
13          int mid = (l+r)>>1;
14          if (②) {
15              r = mid;
16          } else {
17              l = mid + 1;
18          }
19      }
20      return ③;
21  }
22 
23  long long get_rank(int sum) {
24      long long rank = 0;
25      for (int i = 0; i < n; ++i) {
26          rank += upper_bound(b, b+n, sum - a[i]) - b;
27      }
28      return rank;
29  }
30 
31  int solve() {
32      int l = 0, r = ④;
33      while (l < r) {
34          int mid = ((long long)l+r)>>1;
35          if (⑤) {
36              l = mid + 1;
37          } else {
38              r = mid;
39          }
40      }
41      return l;
42  }
43 
44  int main() {
45      cin >> n >> k;
46      for (int i = 0; i < n; ++i) cin >> a[i];
47      for (int i = 0; i < n; ++i) cin >> b[i];
48      cout << solve() << endl;
49  }

（次短路）已知一个有 $n$ 个点、$m$ 条边的有向图 $G$，并且给定图中的两个点 $s$ 和 $t$，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 -1；如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。

1  #include <cstdio>
2  #include <queue>
3  #include <utility>
4  #include <cstring>
5  using namespace std;
6 
7  const int maxn = 2e5+10, maxm = 1e6+10, inf = 522133279;
8 
9  int n, m, s, t;
10  int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
11  int dis[maxn<<1], *dis2;
12  int pre[maxn<<1], *pre2;
13  bool vis[maxn<<1];
14 
15  void add(int a, int b, int c) {
16      ++tot;
17      nxt[tot] = head[a];
18      to[tot] = b;
19      w[tot] = c;
20      head[a] = tot;
21  }
22 
23  bool upd(int a, int b, int d, priority_queue<pair<int, int>> &q) {
24      if (d >= dis[b]) return false;
25      if (b < n) ①;
26      q.push(②);
27      dis[b] = d;
28      pre[b] = a;
29      return true;
30  }
31 
32  void solve() {
33      priority_queue<pair<int, int> > q;
34      q.push(make_pair(0, s));
35      memset(dis, ③, sizeof(dis));
36      memset(pre, -1, sizeof(pre));
37      dis2 = dis+n;
38      pre2 = pre+n;
39      dis[s] = 0;
40      while (!q.empty()) {
41          int aa = q.top().second; q.pop();
42          if (vis[aa]) continue;
43          vis[aa] = true;
44          int a = aa % n;
45          for (int e = head[a]; e; e = nxt[e]) {
46              int b = to[e], c = w[e];
47              if (aa < n) {
48                  if (!upd(a, b, dis[a]+c, q))
49                      ④;
50              } else {
51                  upd(n+a, n+b, dis2[a]+c, q);
52              }
53          }
54      }
55  }
56 
57  void out(int a) {
58      if (a != s) {
59          if (a < n) out(pre[a]);
60          else out(⑤);
61      }
62      printf("%d%c", a%n+1, " \n"[a == n+t]);
63  }
64 
65  int main() {
66      scanf("%d%d%d%d", &n, &m, &s, &t);
67      s--, t--;
68      for (int i = 0; i < m; ++i) {
69          int a, b, c;
70          scanf("%d%d%d", &a, &b, &c);
71          add(a-1, b-1, c);
72      }
73      solve();
74      if (dis2[t] == inf) puts("-1");
75      else {
76          printf("%d\n", dis2[t]);
77          out(n+t);
78      }
79  }