CSP-S 2020 · 提高级A卷第一轮真题

请选择以下最大的数（ ）

操作系统的功能是（ ）。

现有一段 $8$ 分钟的视频文件，它的播放速度是每秒 $24$ 帧图像，每帧图像是一幅分辨率为 $2048\times1024$ 像素的 $32$ 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。

今有一空栈 $S$，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行：进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈底元素为（ ）。

将 $(2,7,10,18)$ 分别存储到某个地址区间为 $0\sim10$ 的哈希表中，如果哈希函数 $h(x)=$（ ），将不会产生冲突，其中 $a\bmod b$ 表示 $a$ 除以 $b$ 的余数。

下列哪些问题不能用贪心法精确求解？（ ）

具有 $n$ 个顶点、$e$ 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，$24$ 个顶点的二分图至多有（ ）条边。

广度优先搜索时，一定需要用到的数据结构是（ ）。

一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 $n$ 在以下哪个区间？已知 $n<60$。（ ）

小明想通过走楼梯来锻炼身体，假设从第 $1$ 层走到第 $2$ 层消耗 $10$ 卡热量，接着从第 $2$ 层走到第 $3$ 层消耗 $20$ 卡热量，从第 $3$ 层走到第 $4$ 层消耗 $30$ 卡热量，依此类推，从第 $k$ 层走到第 $k+1$ 层消耗 $10k$ 卡热量（$k>1$）。如果小明想从 $1$ 层开始，通过连续向上爬楼梯消耗 $1000$ 卡热量，至少要爬到第几层楼？（ ）

表达式 a*(b+c)-d 的后缀表达形式为（ ）。

从一个 $4\times4$ 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。

对一个 $n$ 个顶点、$m$ 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。

1948 年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

1  #include <iostream>
2  using namespace std;
3 
4  int n;
5  int d[1000];
6 
7  int main() {
8      cin >> n;
9      for (int i = 0; i < n; ++i)
10          cin >> d[i];
11      int ans = -1;
12      for (int i = 0; i < n; ++i)
13          for (int j = 0; j < n; ++j)
14              if (d[i] < d[j])
15                  ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
16      cout << ans;
17      return 0;
18  }

假设输入的 $n$ 和 d[i] 都是不超过 $10000$ 的正整数，完成下面的判断题和单选题。

1  #include <iostream>
2  #include <cstdlib>
3  using namespace std;
4 
5  int n;
6  int d[10000];
7 
8  int find(int L, int R, int k) {
9      int x = rand() % (R - L + 1) + L;
10      swap(d[L], d[x]);
11      int a = L + 1, b = R;
12      while (a < b) {
13          while (a < b && d[a] < d[L])
14              ++a;
15          while (a < b && d[b] >= d[L])
16              --b;
17          swap(d[a], d[b]);
18      }
19      if (d[a] < d[L])
20          ++a;
21      if (a - L == k)
22          return d[L];
23      if (a - L < k)
24          return find(a, R, k - (a - L));
25      return find(L + 1, a - 1, k);
26  }
27 
28  int main() {
29      int k;
30      cin >> n;
31      cin >> k;
32      for (int i = 0; i < n; ++i)
33          cin >> d[i];
34      cout << find(0, n - 1, k);
35      return 0;
36  }

假设输入的 $n$、$k$ 和 d[i] 都是不超过 $10000$ 的正整数，且 $k$ 不超过 $n$，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题。

1  #include <iostream>
2  #include <queue>
3  using namespace std;
4 
5  const int maxl = 2000000000;
6 
7  class Map {
8      struct item {
9          string key; int value;
10      } d[maxl];
11      int cnt;
12      public:
13      int find(string x) {
14          for (int i = 0; i < cnt; ++i)
15              if (d[i].key == x)
16                  return d[i].value;
17          return -1;
18      }
19      static int end() { return -1; }
20      void insert(string k, int v) {
21          d[cnt].key = k; d[cnt++].value = v;
22      }
23  } s[2];
24 
25  class Queue {
26      string q[maxl];
27      int head, tail;
28      public:
29      void pop() { ++head; }
30      string front() { return q[head + 1]; }
31      bool empty() { return head == tail; }
32      void push(string x) { q[++tail] = x; }
33  } q[2];
34 
35  string st0, st1;
36  int m;
37 
38  string LtoR(string s, int L, int R) {
39      string t = s;
40      char tmp = t[L];
41      for (int i = L; i < R; ++i)
42          t[i] = t[i + 1];
43      t[R] = tmp;
44      return t;
45  }
46 
47  string RtoL(string s, int L, int R) {
48      string t = s;
49      char tmp = t[R];
50      for (int i = R; i > L; --i)
51          t[i] = t[i - 1];
52      t[L] = tmp;
53      return t;
54  }
55 
56  bool check(string st, int p, int step) {
57      if (s[p].find(st) != s[p].end())
58          return false;
59      ++step;
60      if (s[p ^ 1].find(st) == s[p].end()) {
61          s[p].insert(st, step);
62          q[p].push(st);
63          return false;
64      }
65      cout << s[p ^ 1].find(st) + step << endl;
66      return true;
67  }
68 
69  int main() {
70      cin >> st0 >> st1;
71      int len = st0.length();
72      if (len != st1.length()) {
73          cout << -1 << endl;
74          return 0;
75      }
76      if (st0 == st1) {
77          cout << 0 << endl;
78          return 0;
79      }
80      cin >> m;
81      s[0].insert(st0, 0); s[1].insert(st1, 0);
82      q[0].push(st0); q[1].push(st1);
83      for (int p = 0;
84          !(q[0].empty() && q[1].empty());
85          p ^= 1) {
86          string st = q[p].front(); q[p].pop();
87          int step = s[p].find(st);
88          if ((p == 0 &&
89              (check(LtoR(st, m, len - 1), p, step) ||
90              check(RtoL(st, 0, m), p, step)))
91              ||
92              (p == 1 &&
93              (check(LtoR(st, 0, m), p, step) ||
94              check(RtoL(st, m, len - 1), p, step))))
95              return 0;
96      }
97      cout << -1 << endl;
98      return 0;
99  }

完成下面的判断题和单选题。

（分数背包）小 S 有 $n$ 块蛋糕，编号从 $1$ 到 $n$。第 $i$ 块蛋糕的价值是 $w_i$，体积是 $v_i$。他有一个大小为 $B$ 的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过 $B$。

他打算选择一些蛋糕装入盒子，他希望盒里装的蛋糕的价值之和尽量大。

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $\alpha$（$0<\alpha<1$），并将一块价值是 $w$、体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $\alpha w$、体积是 $\alpha v$，另一块的价值是 $(1-\alpha)w$、体积是 $(1-\alpha)v$。他可以重复无限次切割操作。

现要求编程输出最大可能的价值，以分数的形式输出。

比如 $n=3$，$B=8$，三块蛋糕的价值分别是 $4$、$4$、$2$，体积分别是 $5$、$3$、$2$。那么最优的方案就是将体积为 $5$ 的蛋糕切成两份，一份体积是 $3$，价值是 $2.4$，另一份体积是 $2$，价值是 $1.6$，然后把体积是 $3$ 的那部分和后两块蛋糕打包装盒子。最优的价值之和是 $8.4$，故程序输出 $42/5$。

输入的数据范围为：$1\le n\le1000$，$1\le B\le10^5$，$1\le w_i,v_i\le100$。

提示：将所有的蛋糕按照性价比 $w_i/v_i$ 从大到小排序后进行贪心选择。

试补全程序。

1  #include <cstdio>
2  using namespace std;
3 
4  const int maxn = 1005;
5 
6  int n, B, w[maxn], v[maxn];
7 
8  int gcd(int u, int v) {
9      if (v == 0)
10          return u;
11      return gcd(v, u % v);
12  }
13 
14  void print(int w, int v) {
15      int d = gcd(w, v);
16      w = w / d;
17      v = v / d;
18      if (v == 1)
19          printf("%d\n", w);
20      else
21          printf("%d/%d\n", w, v);
22  }
23 
24  void swap(int &x, int &y) {
25      int t = x; x = y; y = t;
26  }
27 
28  int main() {
29      scanf("%d %d", &n, &B);
30      for (int i = 1; i <= n; i ++) {
31          scanf("%d%d", &w[i], &v[i]);
32      }
33      for (int i = 1; i < n; i ++)
34          for (int j = 1; j < n; j ++)
35              if (①) {
36                  swap(w[j], w[j + 1]);
37                  swap(v[j], v[j + 1]);
38              }
39      int curV, curW;
40      if (②) {
41          ③
42      } else {
43          print(B * w[1], v[1]);
44          return 0;
45      }
46 
47      for (int i = 2; i <= n; i ++)
48          if (curV + v[i] <= B) {
49              curV += v[i];
50              curW += w[i];
51          } else {
52              print(④);
53              return 0;
54          }
55      print(⑤);
56      return 0;
57  }

（最优子序列）取 $m=16$，给出长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$（$0\le a_i<2^m$）。对于一个二进制数 $x$，定义其分值 $w(x)$ 为 $x+\operatorname{popcnt}(x)$，其中 $\operatorname{popcnt}(x)$ 表示 $x$ 二进制表示中 $1$ 的个数。对于一个子序列 $b_1,b_2,\ldots,b_k$，定义其子序列分值 $S$ 为 $w(b_1\oplus b_2)+w(b_2\oplus b_3)+\cdots+w(b_{k-1}\oplus b_k)$。其中 $\oplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$。求一个子序列使得其子序列分值最大，输出这个最大值。

输入第一行包含一个整数 $n$（$1\le n\le40000$）。接下来一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

提示：考虑优化朴素的动态规划算法，将前 $m/2$ 位和后 $m/2$ 位分开计算。

Max[x][y] 表示当前的子序列下一个位置的高 $8$ 位是 $x$、最后一个位置的低 $8$ 位是 $y$ 时的最大价值。

试补全程序。

1  #include <iostream>
2 
3  using namespace std;
4 
5  typedef long long LL;
6 
7  const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
8  const LL INF = 1000000000000000LL;
9  LL Max[MS + 4][MS + 4];
10 
11  int w(int x)
12  {
13      int s = x;
14      while (x)
15      {
16          ①;
17          s++;
18      }
19      return s;
20  }
21 
22  void to_max(LL &x, LL y)
23  {
24      if (x < y)
25          x = y;
26  }
27 
28  int main()
29  {
30      int n;
31      LL ans = 0;
32      cin >> n;
33      for (int x = 0; x <= MS; x++)
34          for (int y = 0; y <= MS; y++)
35              Max[x][y] = -INF;
36      for (int i = 1; i <= n; i++)
37      {
38          LL a;
39          cin >> a;
40          int x = ②, y = a & MS;
41          LL v = ③;
42          for (int z = 0; z <= MS; z++)
43              to_max(v, ④);
44          for (int z = 0; z <= MS; z++)
45              ⑤;
46          to_max(ans, v);
47      }
48      cout << ans << endl;
49      return 0;
50  }