CSP考试题库 - 第8页

第141题

（矩阵变换）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：数字 0 变成矩阵，数字 1 变成矩阵。最初该矩阵只有一个元素 0，变幻 n 次后，矩阵会变成什么样？

例如，矩阵最初为：[0]；矩阵变幻一次后：；矩阵变幻 2 次后：。

输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如 (11)2<<2=(1100)2。

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

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;
int res[max_size][max_size];
void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}
int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

② 处应填（）

A. x - step, y - step B. x, y - step C. x - step, y D. x, y

第142题

（矩阵变换）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：数字 0 变成矩阵，数字 1 变成矩阵。最初该矩阵只有一个元素 0，变幻 n 次后，矩阵会变成什么样？

例如，矩阵最初为：[0]；矩阵变幻一次后：；矩阵变幻 2 次后：。

输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如 (11)2<<2=(1100)2。

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

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;
int res[max_size][max_size];
void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}
int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

③ 处应填（）

A. x - step, y - step B. x + step, y + step C. x - step, y D. x, y - step

第143题

（矩阵变换）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：数字 0 变成矩阵，数字 1 变成矩阵。最初该矩阵只有一个元素 0，变幻 n 次后，矩阵会变成什么样？

例如，矩阵最初为：[0]；矩阵变幻一次后：；矩阵变幻 2 次后：。

输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如 (11)2<<2=(1100)2。

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

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;
int res[max_size][max_size];
void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}
int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

④ 处应填（）

A. n - 1, n % 2 B. n, 0 C. n, n % 2 D. n - 1, 0

第144题

（矩阵变换）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：数字 0 变成矩阵，数字 1 变成矩阵。最初该矩阵只有一个元素 0，变幻 n 次后，矩阵会变成什么样？

例如，矩阵最初为：[0]；矩阵变幻一次后：；矩阵变幻 2 次后：。

输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如 (11)2<<2=(1100)2。

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

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;
int res[max_size][max_size];
void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}
int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

⑤处应填（）

A. 1 << (n + 1) B. 1 << n C. n + 1 D. 1 << (n - 1)

第145题

（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，对 n 对 10000 以内的整数，从小到大排序。

例如有三对整数（3，4）、（2，4）、（3，3），那么排序之后应该是（2，4）、（3，3）、（3，4）。

输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关键字。

数据范围≤n≤107,1≤a[i],b[i]≤104。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord_____ 存储第二关键字排序的结果，数组 res_____ 存储双关键字排序的结果。

试补全程序

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;
int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < maxs; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);
    return 0;
}

② 处应填（）

A. ord[--cnt[b[i]]]=a[i] B. ord[--cnt[a[i]]]=b[i] C. ord[--cnt[a[i]]] = i D. ord[--cnt[b[i]]] = i

第146题

（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，对 n 对 10000 以内的整数，从小到大排序。

例如有三对整数（3，4）、（2，4）、（3，3），那么排序之后应该是（2，4）、（3，3）、（3，4）。

输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关键字。

数据范围≤n≤107,1≤a[i],b[i]≤104。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord_____ 存储第二关键字排序的结果，数组 res_____ 存储双关键字排序的结果。

试补全程序

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;
int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < maxs; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);
    return 0;
}

③ 处应填（）

A. ++cnt[i] B. ++cnt[b[i]] C. ++cnt[a[i]] D. ++cnt[a[i] * maxs + b[i]]

第147题

（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，对 n 对 10000 以内的整数，从小到大排序。

例如有三对整数（3，4）、（2，4）、（3，3），那么排序之后应该是（2，4）、（3，3）、（3，4）。

输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关键字。

数据范围≤n≤107,1≤a[i],b[i]≤104。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord_____ 存储第二关键字排序的结果，数组 res_____ 存储双关键字排序的结果。

试补全程序

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;
int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < maxs; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);
    return 0;
}

④ 处应填（）

A. res[--cnt[a[ord[i]]]] = ord[i] B. res[--cnt[b[ord[i]]]] = ord[i] C. res[--cnt[a[i]] = ord[i] D. res[--cnt[b[i]] = ord[i]

第148题

（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，对 n 对 10000 以内的整数，从小到大排序。

例如有三对整数（3，4）、（2，4）、（3，3），那么排序之后应该是（2，4）、（3，3）、（3，4）。

输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关键字。

数据范围≤n≤107,1≤a[i],b[i]≤104。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord_____ 存储第二关键字排序的结果，数组 res_____ 存储双关键字排序的结果。

试补全程序

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;
int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < maxs; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);
    return 0;
}

⑤处应填（）

A. a[i],b[i] B. a[res[i]],b[res[i]] C. a[order[res[i]]],b[order[res[i]]] D. a[res[order[i]]],a[res[order[i]]]

第149题

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

输入第一行有两个数，分别为新技术个数 n(1≤n≤103)，以及已有经验值(≤107)。

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

接下来 n 行。第 i 行的第一个数 mi(0≤mi

下面的程序已 O(n2)的时间复杂完成这个问题，试补全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
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
", ans);
    return 0;
}

② 处应填（）

A. threshold[i]＞points B. threshold[i]＞=points C. points＞threshold[i] D. points＞=threshold[i]

第150题

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

输入第一行有两个数，分别为新技术个数 n(1≤n≤103)，以及已有经验值(≤107)。

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

接下来 n 行。第 i 行的第一个数 mi(0≤mi

下面的程序已 O(n2)的时间复杂完成这个问题，试补全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
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
", ans);
    return 0;
}

③ 处应填（）

A. target = -1 B. --cnt[target] C. bonus[target] = 0 D. points += bonus[target]

第151题

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

输入第一行有两个数，分别为新技术个数 n(1≤n≤103)，以及已有经验值(≤107)。

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

接下来 n 行。第 i 行的第一个数 mi(0≤mi

下面的程序已 O(n2)的时间复杂完成这个问题，试补全程序。

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

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
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
", ans);
    return 0;
}

④ 处应填（）

A. cnt[child[target][i]] -= 1 B. cnt[child[target][i]] = 0 C. unlock[child[target][i]] -= 1 D. unlock[child[target][i]] = 0

第152题

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

输入第一行有两个数，分别为新技术个数 n(1≤n≤103)，以及已有经验值(≤107)。

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

接下来 n 行。第 i 行的第一个数 mi(0≤mi

下面的程序已 O(n2)的时间复杂完成这个问题，试补全程序。

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

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn],bonus[maxn];
int points;
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
", ans);
    return 0;
}

⑤处应填（）

A. unlock[i] = cnt[i] B. unlock[i] = m C. unlock[i] = 0 D. unlock[i] =-1

第153题

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

输入第一行有两个正整数，分别为规则个数 n(1≤n≤64),以及石子个数 m(≤107)。

接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

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

提示：

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

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

代码说明：

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

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

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

#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 (aa[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;
}

② 处应填（）

A. a[j]< i B. a[j] ==i C. a[j] !=i D. a[j] >i

第154题

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

输入第一行有两个正整数，分别为规则个数 n(1≤n≤64),以及石子个数 m(≤107)。

接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

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

提示：

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

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

代码说明：

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

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

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

试补全程序

#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 (aa[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;
}

③ 处应填（）

A. trans |= 1ull <<(b[j] - 1) B. status |=1ull << (b[j]- 1) C. status +=1ull << (b[j]-1) D. trans +=1ull<< (b[j]-1)

第155题

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

输入第一行有两个正整数，分别为规则个数 n(1≤n≤64),以及石子个数 m(≤107)。

接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

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

提示：

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

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

代码说明：

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

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

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

试补全程序

#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 (aa[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;
}

④ 处应填（）

A. ~status | trans B. status ＆ trans C. status | trans D. ~status ＆ trans

第156题

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

输入第一行有两个正整数，分别为规则个数 n(1≤n≤64),以及石子个数 m(≤107)。

接下来 n 行。第i行有两个正整数 a[i]和 b[i]。1≤a[i]≤107,b[i]≤64

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

提示：

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

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

代码说明：

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

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

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

试补全程序

#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 (aa[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;
}

⑤处应填（）

A. trans = status | trans ^win B. status = trans >> 1^win C. trans = status ^trans |win D. status =status <<1^win

第157题

（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。

例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤109。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

② 处应填（）

A. n / i B. n / (i * i) C. i * i D. i * i * i

第158题

（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。

例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤109。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;
int n, i;
int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

③ 处应填（）

A. if (n % i == 0) B. if (i * i <= n) C. while (n % i == 0) D. while (i * i <= n)

第159题

（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。

例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤109。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

④ 处应填（）

A. n > 1 B. n <= 1 C. i + i <= n D. i < n / i

第160题

（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。

例如：输入n=120，程序应该输出 2 2 2 3 5，表示 120=2×2×2×3×5。输入保证 2≤n≤109。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;

int n, i;

int main() {
    scanf("%d", &n);
    for (i = ①; ② <= n; i ++) {
        ③ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if (④) {
        printf("%d ", ⑤);
    }
    return 0;
}

⑤处应填（）

A. 2 B. n/i C. n D. i

训练

CSP考试

知识点标签