2021.9.5 初赛模拟（一）错题整理

· · 个人记录

P12

使用冒泡排序算法对下面这个数组[23, 5, 11, 7, 13]进行从小到大排序，需要进行（）次相邻两数的交换操作。

A. 4

B. 5

C. 6

D. 7

错因：把13写成3 （就离谱……）

错解：D

正解：B

解析：纯模拟，主要考察对冒泡排序思想的理解记忆

P13

从{0, 1, 2, 3, 4, 5, 6}中选出三个数字，组成既能被3整除又能被5整除的三位数，这种数字共有（）个。

A. 18

B. 20

C. 9

D. 15

错因：计算错误

错解：D

正解：B

解析：

首先考虑能被5整除的数末位为0或5，所以分两种情况讨论

1.末位为0

    在1-6中选择何为3的倍数的两个数：
    1 2,
    1 5,
    2 4, 
    3 6, 
    4 5，
    共5种选法，每种选法有两种排列，所以共有5 * 2 = 10种方案

2.末位为5

    在[0, 1, 2, 3, 4, 6]中选和除以3余数为1的两个数：
    余0：0, 3, 6, 有两种（不算0）
    余1：1, 4,
    余2：2, 5, 有2 * 2 种
    选0：有两种（105, 405）        
    所以共有2 * 2 * 2 + 2 = 10 种
∴综上，共有10 + 10 = 20 种

P14

83 D – 47 O + 1A H = （)

A. 00100110 B

B. 01100010 B

C. 01000110 B

D. 01001010 B

错因：计算错误

错解：A

正解：C

解析：

∵47 O = 4 * 8 + 7 * 1 = 39 D
1A H = 1 * 16 + 10 = 26 D

∴ 83 D - 39 D + 26 D = 70 D = 01000110 B

P22

CODE

#include <cstdio>
#include <iostream>
using namespace std;
int a[101], b[101];
int dfs(int a[], int b[], int x, int y) {
    if(x > y) return 0;
    int p = x, res = 0;
    for(int i = x;i<= y; i++) {
        if(a[i] * b[i] > res) {
            res = a[i] * b[i];
            p = i;
        }
    }
    return dfs(a, b, x, p - 1) + dfs(a, b, p + 1, y) + res;
}
int main() {
    int n; 
    cin>> n;
    for(int i = 1;i <= n; ++i) cin>> a[i];
    for(int j = 1;j <= n; ++j) cin>> b[j];
    cout<<dfs(a, b, 1, n) <<endl;
    return 0;
}

若输入为n为10，a[i] 依次为1到10，b[i]依次为10到1，则答案为（）

A. 180

B. 220

C. 225

D. 255

错因：没有理解代码的实质性作用

错解：D

正解：B

解析：代码的实质性作用就是将a数组和b数组的对应值相乘，在加起来，简单计算可知答案为220

P29

CODE

#include <cstdio>
#include <iostream>
using namespace std;
struct node {int a, b;};
node segment[1005];
int main() {
    int n; cin >> n;
    for(int i = 1;i <= n; i++) {
        cin >> segment[i].a >> segment[i].b;
    }
    for(int i = 1;i <= n; i++) {
       for(int j = 2;j <= n; j++) {
            if(segment[j].b < segment[j - 1].b) { 
                node t = segment[j]; 
                segment[j] = segment[j - 1]; 
                segment[j - 1] = t;
            }
        }
    }
    int t = 0, ans = 0;
    for(int i = 1;i <= n; ++i) {
        if(segment[i].a > t) {
            t = segment[i].b;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

将第十一行的for(int i = 1;i <= n; i++)改for(int i = 1;i <= n - 1; i++)输出结果和改动之前相比不会有任何变化（）

错因：看错

错解：×

正解：√

解析：11行为冒泡排序，最多为n-1次，所以改动没有影响

P34

（一） （数列分段）对于给定的一个长度为N的正整数数列A1~An，现要将其分成M段，并且要求每段连续，且每段和的最大值最小。保证M<= N。

关于最大值最小：例如一个数列[4, 2, 4, 5, 1]要分成3段，将其如下分段[[4], [2, 4], [5, 1]]，可以分成3段，且此时第一段和为4，第二段和为6，第三段和为6，最大的和为6。可以看出，其他的分段方法的最大值都不小于6，因此答案6即为每段和的最大值的最小值。

输入的数据范围为1 <= N <= 105, M <= N，Ai< 108，答案不超过109

CODE

#include <cstdio>
#include <iostream>
using namespace std;
int n, m, num[100005];
int main() {
    cin >> n >> m; 
    int l = 1, r = 1e9;
    for(int i = 1;i <= n; i++) {
        cin >> num[i];
        if(num[i] > l) ____32_____
    }
    while(l < r) {
        int mid = (l + r) / 2;
        int ans = 0, sum = 0;
        for(int i = 1;i <= n; i++) {
            ____33_____
            if(____34_____) {
                sum = num[i];
                ans++;
            }
        }
        if(sum) ____35_____
        if(____36_____) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    cout << r << endl;
    return 0;
}

A. sum != mid

B. sum == mid

C. sum > mid

D. sum < mid

错因：没有理解代码的作用，导致错解

错解：B

正解：C

解析：当sum > mid时，不用更改r的值。