2020年 CSP-S 第一轮（提高级）

单项选择题

1

单选题2 分

请选出以下最大的数（）

A

$550)_{10}$

B

$777)_8$

C

$22F)_{16}$

D

$2^{10}$

2

单选题2 分

操作系统的功能是（）

A

负责外设与主机之间的信息交换

B

控制和管理计算机系统的各种硬件和软件资源的使用

C

负责诊断机器的故障

D

将源程序编译成目标程序

3

单选题2 分

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

A

30G

B

90G

C

150G

D

450G

4

单选题2 分

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

A

b

B

d

C

c

D

a

5

单选题2 分

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

A

$x^2 \mod 11$

B

$\mod 11$

C

$\mod 11$

D

$11\lfloor x/2 \rfloor \mod 11$ ，其中 $⌊x/2⌋\lfloor x / 2 \rfloor$ 表示 $x /2$ 下取整

6

单选题2 分

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

A

霍夫曼编码问题

B

0-1 背包问题

C

最小生成树问题

D

单源最短路径问题

7

单选题2 分

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

A

$Θ(n+e)\Theta(n+e)$

B

$Θ(n2)\Theta(n^2)$

C

$Θ(e2)\Theta(e^2)$

D

$Θ(n)\Theta(n)$

8

单选题2 分

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

A

144

B

100

C

48

D

122

9

单选题2 分

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

A

栈

B

二叉树

C

哈希表

D

队列

10

单选题2 分

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

A

$30 < n < 40$

B

$40 < n < 50$

C

$50 < n < 60$

D

$20 < n < 30$

11

单选题2 分

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

A

14

B

16

C

15

D

13

12

单选题2 分

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

A

$ab c * + d -$

B

$- + * ab c d$

C

$ab c d * \pm$

D

$ab c + * d -$

13

单选题2 分

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

A

60

B

86

C

64

D

72

14

单选题2 分

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

A

$n)\Theta((m+n^2)\ \log\ n)$

B

$Θ(mn+n3)\Theta(mn+n^3)$

C

$n)\Theta((m+n)\ \log\ n)$

D

$Θ(n2)\Theta(n^2)$

15

单选题2 分

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

A

欧拉（Leonhard Euler）

B

冯·诺依曼（John von Neumann）

C

克劳德·香农（Claude Shannon）

D

图灵（Alan Turing）

阅读程序

16

判断题1 分

阅读程序代码（共 16-21 题共用）

#include <iostream>
using namespace std;

int n;
int d[1000];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }
    int ans = -1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i] < d[j])
                ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
    cout << ans;
    return 0;
}

假设输入的 n 和 d[i] 都是不超过 $10000$ 的正整数。

判断：n 必须小于 $1000$ ，否则程序可能会发生错误。（）

A

正确

B

错误

17

判断题1 分

假设输入的 n 和 d[i] 都是不超过 $10000$ 的正整数。

判断：输出一定大于等于 0。（）

A

正确

B

错误

18

判断题1 分

假设输入的 n 和 d[i] 都是不超过 $10000$ 的正整数。

判断：若将第 13 行的 j = 0 改为 j = i + 1 ，程序输出可能会改变。（）

A

正确

B

错误

19

判断题1 分

假设输入的 n 和 d[i] 都是不超过 $10000$ 的正整数。

判断：将第 14 行的 d[i] < d[j] 改为d[i] != d[j] ，程序输出不会改变。（）

A

错误

B

正确

20

单选题3 分

假设输入的 n 和 d[i] 都是不超过 $10000$ 的正整数。

若输入的 n 为 100，且输出为 127，则输入的 d[i] 中不可能有（）

A

127

B

126

C

128

D

125

21

单选题3 分

假设输入的 n 和 d[i] 都是不超过 $10000$ 的正整数。

若输出的数大于 0，则下面说法正确的是（）

A

若输出为偶数，则输入的 d[i] 中最多有两个偶数

B

若输出为奇数，则输入的 d[i] 中至少有两个奇数

C

若输出为偶数，则输入的 d[i] 中至少有两个偶数

D

若输出为奇数，则输入的 d[i] 中最多有两个奇数

22

判断题1 分

阅读程序代码（共 22-27 题共用）

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 1, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假设输入的 n，k 和 d[i] 都是不超过 $10000$ 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数。

判断：第 9 行的 x 的数值范围是 $L + 1$ 到 $R$ ，即 $[L + 1, R]$ 。（）

A

正确

B

错误

23

判断题1 分

假设输入的 n，k 和 d[i] 都是不超过 $10000$ 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数。

判断：将第 19 行的 d[a] 改为 d[b] ，程序不会发生运行错误。（）

A

正确

B

错误

24

单选题2 分

假设输入的 n，k 和 d[i] 都是不超过 $10000$ 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数。

当输入的 d[i] 是严格单调递增序列时，第 17 行的 swap 的平均执行次数是（）

注：本题正确答案应为 $n)\Theta(\log^2\ n)$ ，试题中没有这一选项，比赛时认为选择任一选项均对。在此大家请选择 $n)\Theta(\log\ n)$ 选项作为替代。

A

$n)\Theta(n\ \log\ n)$

B

$Θ(n)\Theta(n)$

C

$n)\Theta(\log\ n)$

D

$Θ(n2)\Theta(n^2)$

25

单选题2 分

假设输入的 n，k 和 d[i] 都是不超过 $10000$ 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数。

当输入的 d[i] 是严格单调递减序列时，第 17 行的 swap 平均执行次数是（）

A

$Θ(n2)\Theta(n^2)$

B

$Θ(n)\Theta(n)$

C

$n)\Theta(n\ \log\ n)$

D

$n)\Theta(\log\ n)$

26

单选题2 分

假设输入的 n，k 和 d[i] 都是不超过 $10000$ 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数。

若输入的 d[i] 为 i，此程序：

①平均的时间复杂度

②最坏情况下的时间复杂度

分别是（）

A

$Θ(n)\Theta(n)$ ， $Θ(n2)\Theta(n^2)$

B

$Θ(n)\Theta(n)$ ， $n)\Theta(n\ \log\ n)$

C

$n)\Theta(n\ \log\ n)$ ， $Θ(n2)\Theta(n^2)$

D

$n)\Theta(n \ \log\ n)$ ， $n)\Theta(n \ \log\ n)$

27

单选题2 分

假设输入的 n，k 和 d[i] 都是不超过 $10000$ 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数。

若输入的 d[i] 都为同一个数，此程序的平均时间复杂度是（）

A

$Θ(n)\Theta(n)$

B

$Θ(log⁡n)\Theta(\log n)$

C

$n)\Theta(n\ \log\ n)$

D

$Θ(n2)\Theta(n^2)$

28

判断题1 分

阅读程序代码（共 28-33 题共用）

#include <iostream>
#include <queue>
using namespace std;

const int maxl = 2000000000;

class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
public:
    int find(string x) {
        for (int i = 0; i < cnt; i++)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];

class Queue {
    string q[maxl];
    int head, tail;
public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x; }
} q[2];

string st0, st1;
int m;

string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}

string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}

bool check(string st, int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}

int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
         !(q[0].empty() && q[1].empty());
         p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
              (check(LtoR(st, m, len - 1), p, step) ||
               check(RtoL(st, 0, m), p, step)))
                  ||
            (p == 1 &&
              (check(LtoR(st, 0, m), p, step) ||
               check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

判断：输出可能为 0。（）

A

正确

B

错误

29

判断题1 分

判断：若输入的两个字符串长度均为 101 时，则 m=0 时的输出与 m=100 时的输出是一样的。（）

A

正确

B

错误

30

判断题1 分

判断：若两个字符串的长度均为 $n$ ，则最坏情况下，此程序的时间复杂度为 $Θ(n!)\Theta(n!)$ 。（）

A

正确

B

错误

31

单选题2 分

若输入的第一个字符串长度由 $100$ 个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的 $m$ 为 $0$ ，则输出为（）。

A

49

B

50

C

100

D

-1

32

单选题4 分

已知当输入为

时，输出为 $4$ 。

当输入为

时，输出为 $14$ 。

当输入为

时，输出为 $28$ 。

请问，当输入为

输出为（）。

A

56

B

84

C

102

D

68

33

单选题4 分

若两个字符串的长度均为 $n$ ，且 $0 < m < n - 1$ ，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（）。提示：考虑输入与输出有多少对字符前后顺序不一样。

A

若 n、m 均为奇数，则输出可能小于 0

B

若 n、m 均为偶数，则输出可能小于 0

C

若 n 为偶数、m 为奇数，则输出可能小于 0

D

若 n 为奇数、m 为偶数，则输出可能小于 0

完善程序

34

单选题3 分

阅读程序代码（共 34-38 题共用）

#include <cstdio>
using namespace std;

const int maxn = 1005;

int n, B, w[maxn], v[maxn];

int gcd(int u, int v) {
    if (v == 0)
        return u;
    return gcd(v, u % v);
}

void print(int w, int v) {
    int d = gcd(w, v);
    w = w / d;
    v = v / d;
    if (v == 1)
        printf("%d\\n", w);
    else
        printf("%d/%d\\n", w, v);
}

void swap(int &x, int &y) {
    int t = x; x = y; y = t;
}

int main() {
    scanf("%d %d", &n, &B);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    for (int i = 1; i < n; i ++)
        for (int j = 1; j < n; j ++)
            if ( ① ) {
                swap(w[j], w[j + 1]);
                swap(v[j], v[j + 1]);
            }
    int curV, curW;
    if ( ② ) {
        ③
    } else {
        print(B * w[1], v[1]);
        return 0;
    }

    for (int i = 2; i <= n; i ++)
        if (curV + v[i] <= B) {
            curV += v[i];
            curW += w[i];
        } else {
            print( ④ );
            return 0;
        }
    print( ⑤ );
    return 0;
}

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

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

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $α(0<α<1)\alpha(0 < \alpha < 1)$ ，并将一块价值是 $w$ ，体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $αw\alpha w$ ，体积是 $αv\alpha v$ ，另一块的价值是 $(1−α)w(1-\alpha)w$ ，体积是 $(1−α)v(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$ 。

输入的数据范围为： $\le n \le 1000$ ， $\le B \le 10^5$ ， $\le w_i,v_i \le 100$ 。

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

试补全程序。

①处应填（）

A

w[j] / v[j] < w[j + 1] / v[j + 1]

B

w[j] / v[j] > w[j + 1] / v[j + 1]

C

v[j] * w[j + 1] < v[j + 1] * w[j]

D

w[j] * v[j + 1] < w[j + 1] * v[j]

35

单选题3 分

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

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

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $α(0<α<1)\alpha(0 < \alpha < 1)$ ，并将一块价值是 $w$ ，体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $αw\alpha w$ ，体积是 $αv\alpha v$ ，另一块的价值是 $(1−α)w(1-\alpha)w$ ，体积是 $(1−α)v(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$ 。

输入的数据范围为： $\le n \le 1000$ ， $\le B \le 10^5$ ， $\le w_i,v_i \le 100$ 。

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

试补全程序。

②处应填（）

A

w[1] <= B

B

v[1] <= B

C

w[1] >= B

D

v[1] >= B

36

单选题3 分

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

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

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $α(0<α<1)\alpha(0 < \alpha < 1)$ ，并将一块价值是 $w$ ，体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $αw\alpha w$ ，体积是 $αv\alpha v$ ，另一块的价值是 $(1−α)w(1-\alpha)w$ ，体积是 $(1−α)v(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$ 。

输入的数据范围为： $\le n \le 1000$ ， $\le B \le 10^5$ ， $\le w_i,v_i \le 100$ 。

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

试补全程序。

③处应填（）

A

curV = 0; curW = 0;

B

print(v[1], w[1]); return 0;

C

print(w[1], v[1]); return 0;

D

curV = v[1]; curW = w[1];

37

单选题3 分

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

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

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $α(0<α<1)\alpha(0 < \alpha < 1)$ ，并将一块价值是 $w$ ，体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $αw\alpha w$ ，体积是 $αv\alpha v$ ，另一块的价值是 $(1−α)w(1-\alpha)w$ ，体积是 $(1−α)v(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$ 。

输入的数据范围为： $\le n \le 1000$ ， $\le B \le 10^5$ ， $\le w_i,v_i \le 100$ 。

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

试补全程序。

④处应填（）

A

curW * v[i] + curV * w[i], v[i]

B

(curW - w[i]) * v[i] + (B - curV) * w[i], v[i]

C

curW + v[i], w[i]

D

curW * v[i] + (B - curV) * w[i], v[i]

38

单选题3 分

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

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

为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个 $α(0<α<1)\alpha(0 < \alpha < 1)$ ，并将一块价值是 $w$ ，体积为 $v$ 的蛋糕切割成两块，其中一块的价值是 $αw\alpha w$ ，体积是 $αv\alpha v$ ，另一块的价值是 $(1−α)w(1-\alpha)w$ ，体积是 $(1−α)v(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$ 。

输入的数据范围为： $\le n \le 1000$ ， $\le B \le 10^5$ ， $\le w_i,v_i \le 100$ 。

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

试补全程序。

⑤处应填（）

A

curW, curV

B

curW, 1

C

curV, curW

D

curV, 1

39

单选题3 分

阅读程序代码（共 39-43 题共用）

#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];

int w(int x)
{
    int s = x;
    while (x)
    {
        ①;
        s++;
    }
    return s;
}

void to_max(LL &x, LL y)
{
    if (x < y)
        x = y;
}

int main()
{
    int n;
    LL ans = 0;
    cin >> n;
    for (int x = 0; x <= MS; x++)
        for (int y = 0; y <= MS; y++)
            Max[x][y] = -INF;
    for (int i = 1; i <= n; i++)
    {
        LL a;
        cin >> a;
        int x = ②, y = a & MS;
        LL v = ③;
        for (int z = 0; z <= MS; z++)
            to_max(v, ④);
        for (int z = 0; z <= MS; z++)
            ⑤;
        to_max(ans, v);
    }
    cout << ans << endl;
    return 0;
}

（最优子序列）取 m = 16，给出长度为 n 的整数序列 $a1,a2,…,an(0≤ai≤2m)a_1,a_2,\dots,a_n(0 \le a_i \le 2^m)$ 。对于一个二进制数 $x$ ，定义其分值 $w (x)$ 为 $x + p o p c n t (x)$ ，其中 $p o p c n t (x)$ 表示 $x$ 二进制表示中 1 的个数。对于一个子序列 $b1,b2,…,bkb_1,b_2,\ldots,b_k$ ，定义其子序列分值 $S$ 为 $w(b1⨁b2)+w(b2⨁b3)+w(b3⨁b4)+…w(bk−1⨁bk)w(b_1\bigoplus b_2)+w(b_2 \bigoplus b_3) + w(b_3 \bigoplus b_4) + \dots w(b_{k-1} \bigoplus b_k)$ 。其中 $⨁\bigoplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 。求一个子序列似的其子序列的分值最大，输出这个最大值。

输入第一行包含一个整数 $\le n \le 40000)$ 。接下来一行包含 $n$ 个整数 $a1,a2,…,ana_1,a_2,\dots,a_n$ 。

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

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

试补全程序。

①处应填（）

A

x >>= 1

B

x ^= x & (x ^ (x + 1))

C

x -= x | -x

D

x ^= x & (x ^ (x - 1))

40

单选题3 分

（最优子序列）取 m = 16，给出长度为 n 的整数序列 $a1,a2,…,an(0≤ai≤2m)a_1,a_2,\dots,a_n(0 \le a_i \le 2^m)$ 。对于一个二进制数 $x$ ，定义其分值 $w (x)$ 为 $x + p o p c n t (x)$ ，其中 $p o p c n t (x)$ 表示 $x$ 二进制表示中 1 的个数。对于一个子序列 $b1,b2,…,bkb_1,b_2,\ldots,b_k$ ，定义其子序列分值 $S$ 为 $w(b1⨁b2)+w(b2⨁b3)+w(b3⨁b4)+…w(bk−1⨁bk)w(b_1\bigoplus b_2)+w(b_2 \bigoplus b_3) + w(b_3 \bigoplus b_4) + \dots w(b_{k-1} \bigoplus b_k)$ 。其中 $⨁\bigoplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 。求一个子序列似的其子序列的分值最大，输出这个最大值。

输入第一行包含一个整数 $\le n \le 40000)$ 。接下来一行包含 $n$ 个整数 $a1,a2,…,ana_1,a_2,\dots,a_n$ 。

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

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

试补全程序。

②处应填（）

A

(a & MS) << B

B

a >> B

C

a & (1 << B)

D

a & (MS << B)

41

单选题3 分

（最优子序列）取 m = 16，给出长度为 n 的整数序列 $a1,a2,…,an(0≤ai≤2m)a_1,a_2,\dots,a_n(0 \le a_i \le 2^m)$ 。对于一个二进制数 $x$ ，定义其分值 $w (x)$ 为 $x + p o p c n t (x)$ ，其中 $p o p c n t (x)$ 表示 $x$ 二进制表示中 1 的个数。对于一个子序列 $b1,b2,…,bkb_1,b_2,\ldots,b_k$ ，定义其子序列分值 $S$ 为 $w(b1⨁b2)+w(b2⨁b3)+w(b3⨁b4)+…w(bk−1⨁bk)w(b_1\bigoplus b_2)+w(b_2 \bigoplus b_3) + w(b_3 \bigoplus b_4) + \dots w(b_{k-1} \bigoplus b_k)$ 。其中 $⨁\bigoplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 。求一个子序列似的其子序列的分值最大，输出这个最大值。

输入第一行包含一个整数 $\le n \le 40000)$ 。接下来一行包含 $n$ 个整数 $a1,a2,…,ana_1,a_2,\dots,a_n$ 。

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

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

试补全程序。

③处应填（）

A

0

B

-INF

C

Max[y][x]

D

Max[x][y]

42

单选题3 分

（最优子序列）取 m = 16，给出长度为 n 的整数序列 $a1,a2,…,an(0≤ai≤2m)a_1,a_2,\dots,a_n(0 \le a_i \le 2^m)$ 。对于一个二进制数 $x$ ，定义其分值 $w (x)$ 为 $x + p o p c n t (x)$ ，其中 $p o p c n t (x)$ 表示 $x$ 二进制表示中 1 的个数。对于一个子序列 $b1,b2,…,bkb_1,b_2,\ldots,b_k$ ，定义其子序列分值 $S$ 为 $w(b1⨁b2)+w(b2⨁b3)+w(b3⨁b4)+…w(bk−1⨁bk)w(b_1\bigoplus b_2)+w(b_2 \bigoplus b_3) + w(b_3 \bigoplus b_4) + \dots w(b_{k-1} \bigoplus b_k)$ 。其中 $⨁\bigoplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 。求一个子序列似的其子序列的分值最大，输出这个最大值。

输入第一行包含一个整数 $\le n \le 40000)$ 。接下来一行包含 $n$ 个整数 $a1,a2,…,ana_1,a_2,\dots,a_n$ 。

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

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

试补全程序。

④处应填（）

A

Max[x][z] + w(y ^ z)

B

Max[x][z] + w(a ^ z)

C

Max[x][z] + w(x ^ (z << B))

D

Max[x][z] + w(x ^ z)

43

单选题3 分

（最优子序列）取 m = 16，给出长度为 n 的整数序列 $a1,a2,…,an(0≤ai≤2m)a_1,a_2,\dots,a_n(0 \le a_i \le 2^m)$ 。对于一个二进制数 $x$ ，定义其分值 $w (x)$ 为 $x + p o p c n t (x)$ ，其中 $p o p c n t (x)$ 表示 $x$ 二进制表示中 1 的个数。对于一个子序列 $b1,b2,…,bkb_1,b_2,\ldots,b_k$ ，定义其子序列分值 $S$ 为 $w(b1⨁b2)+w(b2⨁b3)+w(b3⨁b4)+…w(bk−1⨁bk)w(b_1\bigoplus b_2)+w(b_2 \bigoplus b_3) + w(b_3 \bigoplus b_4) + \dots w(b_{k-1} \bigoplus b_k)$ 。其中 $⨁\bigoplus$ 表示按位异或。对于空子序列，规定其子序列分值为 $0$ 。求一个子序列似的其子序列的分值最大，输出这个最大值。

输入第一行包含一个整数 $\le n \le 40000)$ 。接下来一行包含 $n$ 个整数 $a1,a2,…,ana_1,a_2,\dots,a_n$ 。

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

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

试补全程序。

⑤处应填（）

A

to_max(Max[y][z], v + w(a ^ (z << B)))

B

to_max(Max[z][y], v + w((x ^ z) << B))

C

to_max(Max[z][y], v + w(a ^ (z << B)))

D

to_max(Max[x][z], v + w(y ^ z))

题目预览