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

单项选择题

1

单选题2 分

若有定义 int a = 7, float x = 2.5, y = 4.7;，则表达式 x + a % 3 * (int) (x + y) % 2 的值是（）

A

$0.000000$

B

$2.750000$

C

$2.500000$

D

$3.500000$

2

单选题2 分

下列属于图像文件格式的（）

A

WMV

B

MPEG

C

JPEG

D

AVI

3

单选题2 分

下面哪个选项是 $11101110010111$ 和 $01011011101011$ 进行逻辑或运算的结果 ( )。

A

$111111\ 1111\ 1101\ 1111$

B

$110111\ 1111\ 1111\ 1101$

C

$111110\ 1111\ 1111\ 1111$

D

$111111\ 1111\ 1111\ 1111$

4

单选题2 分

编译器的作用是 ( )。

A

将源程序重新组合

B

将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）

C

将低级语言翻译成高级语言

D

将一种编程语言翻译成自然语言

5

单选题2 分

设变量 $x$ 为 float 型且已赋值，下列哪条语句能将 $x$ 中的数值保留到小数点后两位，并将第三位四舍五入 ( )。

A

$x = (x * 100 + 0.5) /100.0$

B

$x = (in t) (x * 100 + 0.5) /100.0$

C

$x = (x /100 + 0.5) * 100.0$

D

$x = x * 100 + 0.5/100.0$

6

单选题2 分

由数字 $1, 1, 2, 4, 8, 8$ 组成的不同的 $4$ 位数的个数是 ( )。

A

$104$

B

$98$

C

$100$

D

$102$

7

单选题2 分

排序的算法很多，若按排序的稳定性和不稳定性分类，下面算法中 ( ) 是不稳定排序。

A

冒泡排序

B

直接插入排序

C

快速排序

D

归并排序

8

单选题2 分

G 是一个非连通无向图（没有重边和自环），共有 $28$ 条边，则该图至少有 ( ) 个点。

A

$10$

B

$9$

C

$11$

D

$8$

9

单选题2 分

一些数字可以颠倒过来看，例如 $0$ 、 $1$ 、 $8$ 颠倒过来还是本身， $6$ 颠倒过来是 $9$ ， $9$ 颠倒过来看还是 $6$ ，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如 $106$ 颠倒过来是 $901$ 。假设某个城市的车牌只由 $5$ 位数字组成，每一位都可以取 $0$ 到 $9$ 。请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的 $5$ 位数能被 $3$ 整除 ( )。

A

$40$

B

$25$

C

$30$

D

$20$

10

单选题2 分

一次期末考试，某班有 $15$ 人数学得满分，有 $12$ 人语文得满分，共有 $4$ 人语文、数学都是满分，那么这个班至少有一门满分的同学有多少人 ( )。

A

$21$

B

$20$

C

$22$

D

$23$

11

单选题2 分

设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法，在最坏情况下至少要做多少次比较( )。

A

$n^2$

B

$nlog⁡nn\log n$

C

$2 n$

D

$2 n - 1$

12

单选题2 分

以下哪个结构可以用来存图 ( )。

A

栈

B

二叉树

C

队列

D

邻接矩阵

13

单选题2 分

以下哪些算法不属于贪心算法 ( )。

A

Dijkstra 算法

B

Floyd 算法

C

Prim 算法

D

Kruskal 算法

14

单选题2 分

有一个等比数列，共有奇数项，其中第一项和最后一项分别是 $2$ 和 $118098$ ，中间一项是 $486$ ，请问以下那个数是可能的公比 ( )。

A

$5$

B

$3$

C

$4$

D

$2$

15

单选题2 分

由正实数构成的数字三角形排列如图所示，第一行为数字 $a_{1,1}$ ，第二行的数从左到右依次为 $a_{2,1}$ 、 $a_{2,2}$ ，第 $n$ 行的数为 $a_{n,1}$ 、 $a_{n,2}…a_{n,n}$ 。从 $a_{1,1}$ 开始，每一行的数 $a_{i,j}$ 只有两条边可以分别通向下一行的两个数 $a_{i + 1,j}$ 和 $a_{i + 1,j + 1}$ 。用动态规划算法找出一条从 $a_{1,1}$ 向下通到 $a_{n,1}$ 、 $a_{n,2}…a_{n,n}$ 中的某个路径，使得该路径上的数之和最大。

[图片]

令 $C [i] [j]$ 是从 $a_{1,1}$ 到 $a_{i,j}$ 的路径上的数的最大和，并且 $C [i] [0] = C [0] [j] = 0$ ，则 $C [i] [j] =$ ( )

A

$max(C[i-1][j-1],C[i-1][j])+a_{i,j}$

B

$C [i - 1] [j - 1] + C [i - 1] [j]$

C

$max⁡(C[i−1][j−1],C[i−1][j])+1\max(C[i-1][j-1],C[i-1][j])+ 1$

D

$max(C[i][j-1],C[i-1][j])+a_{i,j}$

阅读程序

16

判断题1 分

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

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; ++i)
       scanf("%d", &a[i]);
   int ans = 1;
   for (int i = 1; i <= n; ++i) {
       if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d\n", ans);
   }
   return 0;
}

第 $16$ 行输出 $an s$ 时， $an s$ 的值一定大于 $i$ 。

A

正确

B

错误

17

判断题1 分

程序输出的 $an s$ 小于等于 $n$ 。

A

正确

B

错误

18

判断题1 分

若将第 $12$ 行的 “<” 改为 “!=” 程序输出的结果不会改变。

A

正确

B

错误

19

判断题1 分

当程序执行到第 $16$ 行时，若 $an s - i > 2$ ，则 $\le a[i]$ 。

A

正确

B

错误

20

单选题3 分

若输入的 $a$ 数组是一个严格单调递增的数列，此程序的时间复杂度是

A

$O(log⁡n)\mathcal{O}(\log n)$

B

$O(n2)\mathcal{O}(n^2)$

C

$O(nlog⁡n)\mathcal{O}(n\log n)$

D

$O(n)\mathcal{O}(n)$

21

单选题4 分

最坏情况下，此程序的时间复杂度为：

A

$O(n2)\mathcal{O}(n^2)$

B

$O(log⁡n)\mathcal{O}(\log n)$

C

$O(n)\mathcal{O}(n)$

D

$O(nlog⁡n)\mathcal{O}(n\log n)$

22

判断题1 分

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

#include <iostream>
using namespace std;
const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}


int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

输入的 $a$ 和 $b$ 的值应在 $[0, n - 1]$ 的范围内

A

正确

B

错误

23

判断题1 分

第 $16$ 行改成 fa[i]=0;，不影响程序运行结果

A

正确

B

错误

24

判断题1 分

若输入的 $a$ 和 $b$ 值均在 $[0, n - 1]$ 的范围内，则对于任意 $0≤i<n0\le i<n$ ，都有 $\le fa[i]< n$ 。

A

正确

B

错误

25

判断题1 分

若输入的 $a$ 和 $b$ 值均在 $[0, n - 1]$ 的范围内，则对于任意 $\le i<n$ ，都有 $1≤cnt[i]≤n1\le cnt[i] \le n$ 。

A

正确

B

错误

26

单选题4 分

当 $n$ 等于 $50$ 时，若 $a$ 、 $b$ 的值都在 $[0, 49]$ 的范围内，且在第 $25$ 行时 $x$ 总是不等于 $y$ ，那么输出为 ( )

A

1276

B

1176

C

1225

D

1250

27

单选题4 分

此程序的时间复杂度是（）

A

$O(n)\mathcal{O}(n)$

B

$O(log⁡n)\mathcal{O}(\log n)$

C

$O(n2)\mathcal{O}(n^2)$

D

$O(nlog⁡n)\mathcal{O}(n\log n)$

28

判断题1 分

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

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen= t.length();
    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j;// t[0..j-1]是s[0..i]的子序列
    }

    for (int i = slen - 1, j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t[j]) --j;
        suf[i]= j; //t[j+1..tlen-1]是s[i..slen-1]的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp= 0; i <= slen; ++i) {
        while (j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t。特别的，如果s = t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 $y - x + 1$ 个字符构成的字符串，若 $x > y$ 则s[x..y]是空串。t[x..y]同理。

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

程序输出时，suf数组满足：对任意 $\le i<slen$ ， $\le suf[i+1]$ 。

A

正确

B

错误

29

判断题2 分

本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t。特别的，如果s = t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 $y - x + 1$ 个字符构成的字符串，若 $x > y$ 则s[x..y]是空串。t[x..y]同理。

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

当 t 是 s 的子序列时，输出一定不为 $0$ 。

A

正确

B

错误

30

判断题2 分

本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t。特别的，如果s = t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 $y - x + 1$ 个字符构成的字符串，若 $x > y$ 则s[x..y]是空串。t[x..y]同理。

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

程序运行到第 $23$ 行时，j - i- 1 一定不小于 $0$

A

正确

B

错误

31

判断题2 分

本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t。特别的，如果s = t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 $y - x + 1$ 个字符构成的字符串，若 $x > y$ 则s[x..y]是空串。t[x..y]同理。

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

当 t 是 s 的子序列时，pre 数组和 suf 数组满足：对任意 $0≤i<slen0\le i<slen$ ， $p r e [i] > s u f [i + 1]$ 。

A

正确

B

错误

32

单选题4 分

本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t。特别的，如果s = t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 $y - x + 1$ 个字符构成的字符串，若 $x > y$ 则s[x..y]是空串。t[x..y]同理。

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

若 tlen = 10，输出为 $0$ ，则 slen 最小为：

A

$10$

B

$12$

C

$0$

D

$1$

33

单选题4 分

本题t是s的子序列的意思是：从s中删去若干个字符，可以得到t。特别的，如果s = t，那么t也是s的子序列；空串是任何串的子序列。例如“acd”是“abcde”的子序列，“acd”是“acd”的子序列，但“adc”不是“abcde”的子序列。

S[x..y]表示s[x]…s[y]共 $y - x + 1$ 个字符构成的字符串，若 $x > y$ 则s[x..y]是空串。t[x..y]同理。

提示：

t[0..pre[i]-1]是s[0..i]的子序列；

t[suf[i]+1..tlen-1]是s[i..slen-1]的子序列。

若 tlen = 10，输出为 $2$ ，则 slen 最小为

A

$0$

B

$10$

C

$12$

D

$1$

完善程序

34

单选题3 分

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

#include<cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int points;
int threshold[maxn],bonus[maxn];

bool find(){
    int target=-1;
    for (int i = 1;i<=n;++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target==-1)
        return false;
    unlock[target]=-1;
    ③
    for (int i=0;i<cnt[target];++i)
        ④
    return true;
}

int main(){
    scanf("%d%d",&n, &points);
    for (int i =1; i<=n;++i){
        cnt [i]=0;
scanf("%d%d",&threshold[i],&bonus[i]);
    }
    for (int i=1;i<=n;++i){
        int m;
        scanf("%d",&m);
        ⑤
        for (int j=0; j<m ;++j){
            int fa;
            scanf("%d", &fa);
            child [fa][cnt[fa]]=i;
            ++cnt[fa];
        }
    }

    int ans = 0;
    while(find())
        ++ans;

    printf("%d\n", ans);
    return 0;
}

（匠人的自我修养）一个匠人决定要学习 $n$ 个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $\leq n \leq 10^3)$ ，以及已有经验值 $(≤107)(\leq 10^7)$ 。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值 $(≤107)(\leq 10^7)$ ，以及学会第 $i$ 个技术后可获得的经验值 $(≤104)(\leq 10^4)$ 。

接下来 $n$ 行。第 $i$ 行的第一个数 $mi(0≤mi<n)m_i(0 \leq m_i < n)$ ，表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号，输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。

请选择 ① 应该填写的代码

A

unlock[i]＜=0

B

unlock[i]＞=0

C

unlock[i]==0

D

unlock[i]==-1

35

单选题3 分

（匠人的自我修养）一个匠人决定要学习 $n$ 个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $\leq n \leq 10^3)$ ，以及已有经验值 $(≤107)(\leq 10^7)$ 。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值 $(≤107)(\leq 10^7)$ ，以及学会第 $i$ 个技术后可获得的经验值 $(≤104)(\leq 10^4)$ 。

接下来 $n$ 行。第 $i$ 行的第一个数 $mi(0≤mi<n)m_i(0 \leq m_i < n)$ ，表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号，输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。

请选择 ② 应该填写的代码

A

threshold[i]＞points

B

threshold[i]＞=points

C

points＞threshold[i]

D

points＞=threshold[i]

36

单选题3 分

（匠人的自我修养）一个匠人决定要学习 $n$ 个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $\leq n \leq 10^3)$ ，以及已有经验值 $(≤107)(\leq 10^7)$ 。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值 $(≤107)(\leq 10^7)$ ，以及学会第 $i$ 个技术后可获得的经验值 $(≤104)(\leq 10^4)$ 。

接下来 $n$ 行。第 $i$ 行的第一个数 $mi(0≤mi<n)m_i(0 \leq m_i < n)$ ，表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号，输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。

请选择 ③ 应该填写的代码

A

target = -1

B

–cnt[target]

C

bonus[target] = 0

D

points += bonus[target]

37

单选题3 分

（匠人的自我修养）一个匠人决定要学习 $n$ 个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $\leq n \leq 10^3)$ ，以及已有经验值 $(≤107)(\leq 10^7)$ 。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值 $(≤107)(\leq 10^7)$ ，以及学会第 $i$ 个技术后可获得的经验值 $(≤104)(\leq 10^4)$ 。

接下来 $n$ 行。第 $i$ 行的第一个数 $mi(0≤mi<n)m_i(0 \leq m_i < n)$ ，表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号，输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。

请选择 ④ 应该填写的代码

A

cnt[child[target][i]] -= 1

B

cnt[child[target][i]] = 0

C

unlock[child[target][i]] -= 1

D

unlock[child[target][i]] = 0

38

单选题3 分

（匠人的自我修养）一个匠人决定要学习 $n$ 个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $\leq n \leq 10^3)$ ，以及已有经验值 $(≤107)(\leq 10^7)$ 。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值 $(≤107)(\leq 10^7)$ ，以及学会第 $i$ 个技术后可获得的经验值 $(≤104)(\leq 10^4)$ 。

接下来 $n$ 行。第 $i$ 行的第一个数 $mi(0≤mi<n)m_i(0 \leq m_i < n)$ ，表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号，输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。

请选择 ⑤ 应该填写的代码

A

unlock[i] = cnt[i]

B

unlock[i] = m

C

unlock[i] = 0

D

unlock[i] =-1

39

单选题3 分

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

#include <cstdio>
#include<algorithm>
using namespace std ;

const int maxn =64;

int n,m;
int a[maxn], b[maxn];
unsigned long long status, trans;
bool win；

int main() {
    scanf(“%d%d”,＆n, ＆m);
    for (int i = 0; i < n; ++i)
        scanf(“%d%d”, ＆a[i], ＆b[i]);
    for (int  i = 0; i < n; ++i)
         for (int j = i + 1; j < n; ++j)
            if (a[i] > a[j]) {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    status = ①;
    trans = 0;
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j < n && ②) {
            ③;
            ++j;
        }
        win = ④;
        ⑤;
    }

    puts(win ? “Win” : “Loss”)；

    return 0;
}

（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余的石子个数大于等于 $a [i]$ 且大于等于 $b [i]$ ，那么她们可以取走 $b [i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了，一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 $\leq n \leq 64)$ ，以及石子个数 $m(≤107)m(\leq 10^7)$ 。

接下来 $n$ 行。第i行有两个正整数 $a [i]$ 和 $b [i]$ 。 $\leq a[i] \leq 10^7, b[i] \leq 64$

如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”

提示：

可以使用动态规划解决这个问题。由于 $b [i]$ 不超过 $64$ ，所以可以使用64位无符号整数去压缩必要的状态。

Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

代码说明：

“~”表示二进制补码运算符，它将每个二进制位的 $0$ 变成 $1$ 、 $1$ 变为 $0$ ；

而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ，反之为 $1$ 。

ull 标识符表示它前面的数字是 unsigned long long 类型。

试补全程序

请选择 ① 应该填写的代码

A

0

B

~0ull

C

~0ull^1

D

1

40

单选题3 分

（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余的石子个数大于等于 $a [i]$ 且大于等于 $b [i]$ ，那么她们可以取走 $b [i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了，一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 $\leq n \leq 64)$ ，以及石子个数 $m(≤107)m(\leq 10^7)$ 。

接下来 $n$ 行。第i行有两个正整数 $a [i]$ 和 $b [i]$ 。 $\leq a[i] \leq 10^7, b[i] \leq 64$

如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”

提示：

可以使用动态规划解决这个问题。由于 $b [i]$ 不超过 $64$ ，所以可以使用64位无符号整数去压缩必要的状态。

Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

代码说明：

“~”表示二进制补码运算符，它将每个二进制位的 $0$ 变成 $1$ 、 $1$ 变为 $0$ ；

而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ，反之为 $1$ 。

ull 标识符表示它前面的数字是 unsigned long long 类型。

试补全程序

请选择 ② 应该填写的代码

A

a[j]< i

B

a[j] ==i

C

a[j] !=i

D

a[j] >i

41

单选题3 分

（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余的石子个数大于等于 $a [i]$ 且大于等于 $b [i]$ ，那么她们可以取走 $b [i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了，一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 $\leq n \leq 64)$ ，以及石子个数 $m(≤107)m(\leq 10^7)$ 。

接下来 $n$ 行。第i行有两个正整数 $a [i]$ 和 $b [i]$ 。 $\leq a[i] \leq 10^7, b[i] \leq 64$

如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”

提示：

可以使用动态规划解决这个问题。由于 $b [i]$ 不超过 $64$ ，所以可以使用64位无符号整数去压缩必要的状态。

Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

代码说明：

“~”表示二进制补码运算符，它将每个二进制位的 $0$ 变成 $1$ 、 $1$ 变为 $0$ ；

而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ，反之为 $1$ 。

ull 标识符表示它前面的数字是 unsigned long long 类型。

试补全程序

请选择 ③ 应该填写的代码

A

trans |= 1ull <<(b[j] - 1)

B

status |=1ull << (b[j]- 1)

C

status +=1ull << (b[j]-1)

D

trans +=1ull<< (b[j]-1)

42

单选题3 分

（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余的石子个数大于等于 $a [i]$ 且大于等于 $b [i]$ ，那么她们可以取走 $b [i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了，一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 $\leq n \leq 64)$ ，以及石子个数 $m(≤107)m(\leq 10^7)$ 。

接下来 $n$ 行。第i行有两个正整数 $a [i]$ 和 $b [i]$ 。 $\leq a[i] \leq 10^7, b[i] \leq 64$

如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”

提示：

可以使用动态规划解决这个问题。由于 $b [i]$ 不超过 $64$ ，所以可以使用64位无符号整数去压缩必要的状态。

Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

代码说明：

“~”表示二进制补码运算符，它将每个二进制位的 $0$ 变成 $1$ 、 $1$ 变为 $0$ ；

而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ，反之为 $1$ 。

ull 标识符表示它前面的数字是 unsigned long long 类型。

试补全程序

请选择 ④ 应该填写的代码

A

~status | trans

B

status ＆ trans

C

status | trans

D

~status ＆ trans

43

单选题3 分

（取石子）Alice 和 Bob 两个人在玩取石子游戏，他们制定了 $n$ 条取石子的规则，第 $i$ 条规则为：如果剩余的石子个数大于等于 $a [i]$ 且大于等于 $b [i]$ ，那么她们可以取走 $b [i]$ 个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了，一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法？

输入第一行有两个正整数，分别为规则个数 $\leq n \leq 64)$ ，以及石子个数 $m(≤107)m(\leq 10^7)$ 。

接下来 $n$ 行。第i行有两个正整数 $a [i]$ 和 $b [i]$ 。 $\leq a[i] \leq 10^7, b[i] \leq 64$

如果先取石子的人必胜，那么输出“Win”，否则输出“Loss”

提示：

可以使用动态规划解决这个问题。由于 $b [i]$ 不超过 $64$ ，所以可以使用64位无符号整数去压缩必要的状态。

Status 是胜负状态的二进制压缩，trans 是状态转移的二进制压缩。

代码说明：

“~”表示二进制补码运算符，它将每个二进制位的 $0$ 变成 $1$ 、 $1$ 变为 $0$ ；

而“^”表示二进制异或运算符，它将两个参与运算的数重的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 $0$ ，反之为 $1$ 。

ull 标识符表示它前面的数字是 unsigned long long 类型。

试补全程序

请选择 ⑤ 应该填写的代码

A

trans = status | trans ^win

B

status = trans >> 1^win

C

trans = status ^trans |win

D

status =status <<1^win

题目预览