洛谷CSP-J/S2020初赛模拟部分题解

说明

试题来源于洛谷CSP-J/S2020初赛模拟试题。

选择题

T1. 十进制数114的相反数的8位二进制补码是：（ 10001110 ）

【解析】整数的二进制表示的最高位为符号位，用0表示“正”，用1表示“负”

• 正整数的补码是其二进制表示，与原码相同。
• 负整数的补码是将其原码除符号位外的所有位取反（0变1，1变0，符号位为1不变）后加1。
  所以，114的二进制表示为 $(01110010{)}_2$ ，-114的补码表示为 $(10001110{)}_2$ 。

T3. 小A用字母 $A$ 表示 $1$ ， $B$ 表示 $2$ ，以此类推，用 $26$ 表示 $Z$ 。对于27以上的数字，可以用两位或者更长的字符来对应，例加 $AA$ 对应 $27$ ， $AB$ 对应 $28$ ， $AZ$ 对应 $52$ ， $AAA$ 对应 $703$ ，…，那么 $BYT$ 字符串对应的数字是（ 2022 ）

【解析】可将字符串看做26进制数， $A-Z$ 分别对应 $1-26$ ， $AA$ 按照权值展开就是 $1\times 26^1+1\times 26^0=27$ ， $AZ=1\times 26^1+26\times 26^0=26+27=52$ ， $AAA=1\times 26^2+1\times 26^1+1\times 26^0=703$ ，那么 $BYT=2\times 26^2+25\times 26^1+20\times 26^0=2022$

T5. 在一个长度为 $n$ 的数组中找到第 $k$ 大的数字，平均的算法时间复杂度最低的是： $O(n)$

【解析】使用快速排序的思想实现。因为每次分区完只需要继续操作一边，所以该算法的平均时间复杂度是 $O(n)$ 。
用 $T(n)$ 表示元素的比较次数，那么平均情况下：

• 第一次划分： $T(n)=T(\frac{n}{2})+n$
• 第二次划分： $T(n)=T(\frac{n}{4})+\frac{n}{2}+n$
• 第三次划分： $T(n)=T(\frac{n}{8})+\frac{n}{4}+\frac{n}{2}+n$
• $...$
• 最终： $T(n)=T(\frac{n}{n})+2+4+...+\frac{n}{4}+\frac{n}{2}+n=1+2+4+...+n$

上式是一个等比数列求和，公比为2，最终结果为： $T(n)=\frac{1-2\times n}{1-2}=2n$ 。

T6. 对于树这种数据结构，正确的有：②③
①一个有n个顶点、n-1条边的图是树。
②一个树中的两个顶点之间有且只有一条简单路径
③树中一定存在度数不大于1的顶点
④树可能存在环

【解析】
①错误，n-1条边的图可能不连通，也可能存在环，树中不能有环。
④错误。
正确答案为：②③

T7. 博艾中学进行了一次信息学会考测试，其优、良、及格、不及格的试卷数里分别为10、13、14、5张。现在这些卷子混在一起，要将这些卷子按照等级分为4叠。分卷子的方法是，每次将一叠有不同等级答卷的卷子分为两堆，使得这两堆中没有相同等级的卷子，然后可以再分，直到分为4叠。要分完这些卷子，至少需要（ 84 ）次“分卷子“的操作。注意：将一堆数量为n的卷子分成两堆，就会产生n次“分卷子”的操作。

【解析】类似于将42张扑克牌按花色分成4堆，每张牌至少被分了两次，所以答案为 $42\times 2=84$

T10. 在一个初始长度为 $n$ 的链表中连续进行k次操作，每次操作是读入两个数字 $a_i$ 和 $b_i$ ，在链表中找到元素为 $a_i$ 的结点（假设一定可以找到），然后将 $b_i$ 这个元素插入到这个结点前面。在最理想的情况下，链表访问的结点数量最少可能是（ k ）(不算将要插入的结点)。

【解析】最理想的情况就是每次都在第一个结点前插入 $b_i$ ，此时链表表访问的总的结点数量为 k 。

T11. A班有5名风纪委员，B班有4名风纪委员，C班有3名风纪委员。现在需要这些同学中选取6名风纪委员巡逻，如果只关注各班派出的风纪委员人数，有（ 18 ）种不同的方案？

【解析】题目要求只关注各班派出的风纪委员人数，可以分情况讨论：

• C班派出0名风纪委员，那么A班派出的人数有4种可能， $2-5$
• C班派出1名风纪委员，那么A班派出的人数有5种可能， $1-5$
• C班派出2名风纪委员，那么A班派出的人数有5种可能， $0-4$
• C班派出3名风纪委员，那么A班派出的人数有4种可能， $0-3$

所以一共有 18 种不同的方案

T13. 已知rand()可以生成一个0到32767的随机整数，如果希望得到一个范围在 $[a,b)$ 的随机整数， $a$ 别 $b$ 均是不超过100的正整数且 $a<b$ ，那么可行的表达式是什么?

【解析】举例验证即可，例如要生成的是 $[1,10)$ 的随机整数，可以通过 $rand()\%9+1$ 得到，即 $rand()\%(b-a)+a$

T14. 一个7个顶点的完全图需要至少删掉（ 15 ）条边才能变为森林?

【解析】一棵树也可以成为森林，所以将完全图变为一棵树，最少删掉 $21-6=15$ 条边。

T15. 2020年8月，第（ 37 ）届全国青少年信息学奥林匹克竞赛在（ 长沙 ）举行。

【解析】常识题，NOI从1984年开始举办全国性竞赛，所以到2020年应该是第37届。

阅读程序

T1.

#include <iostream>
using namespace std;
#define MAXN 20
int gu[MAXN][MAXN];
int luo(int n, int m) {
    if(n <= 1 || m < 2)
        return 1;
    if(gu[n][m] != -1)
        return gu[n][m];
    int ans = 0;
    for(int i = 0; i < m; i += 2)
        ans += luo(n - 1, i);
    gu[n][m] = ans;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < MAXN; i ++)
        for(int j = 0; j < MAXN; j ++)
            gu[i][j] = -1;
    cout << luo(n, m);
    return 0;
}





    

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

1. luo 函数中，m的值不可能是奇数。（ 错误 ）
2. 将第11行的 $<$ 改为 $<=$ ，程序的输出结果可能会改变。（ 正确 ）

【解析】 i <= m 会导致 for 循环中多一次递归调用，而当 n <= 1 || m < 2 时， luo 函数返回 1 ，从而导致结果发生改变。

3. 若将第8、9、13行删除，程序的运行的结果不变。（ 正确 ）

【解析】第8、9、13行去掉，也就是不会记忆 gu[i][j] ，相当于没有记忆化的深度优先搜索，效率降低了，但不影响最后结果。

4. 在添加合适的头文件后，将第19到21行替换为 memset(gu, 255, sizeof(gu)); 可以起到相同的作用。（ 正确 ）

【解析】 $255=(11111111{)}_2=0xFF$ ，相当于将 gu 数组初始化为 -1 。

5. 输入数据为4 8，则输出为（ 8 ）。

【解析】画递归树模拟即可。

6. 最坏情况下，此程序的时间复杂度是（ $O(m^{2}n)$ ）。

【解析】本题深度优先搜索的递归树的高度为 $n$ ，每层的调用次数和 $m$ 有关：

• m = 2，调用1次
• m = 4，调用2次
• m = 8，调用3次
  …
  总的调用次数 $=1+2+3...$ ，近似于 $m^2$ ，所以时间复杂度是 $O(m^{2}n)$ 。

T2.

#include <cstdio>
using namespace std;
int n, m;
int f[101][101];
int F[101][101];
int main() {
    scanf("%d%d", &n, &m); //n的值在1到100之间
    memset(f, -1, sizeof(f));
    for(int i = 1; i <= m; i ++) {
        int u, v, w; //w的值在0到10000之间
        scanf("%d%d%d", &u, &v, &w);
        f[u][v] = f[v][u] = w;
    }
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                if(f[i][k] != -1 && f[k][j] != -1)
                    if(f[i][j] == -1 || f[i][j] > f[k][j] + f[i][k])
                        f[i][j] = f[i][k] + f[k][j];
    int ans = 2147483647;
    for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++) {
                for(int x = 1; x <= n; x ++)
                    for(int y = 1; y <= n; y ++)
                        F[x][y] = f[x][y];
                F[i][j] = F[j][i] = 0;
                for(int x = 1; x <= n; x ++)
                    for(int y = 1; y <= n; y ++)
                        if(F[x][y] == -1 || F[x][y] > F[x][i] + F[i][y])
                            F[x][y] = F[x][i] + F[i][y];
                for(int x = 1; x <= n; x ++)
                    for(int y = 1; y <= n; y ++)
                        if(F[x][y] == -1 || F[x][y] > F[x][j] + F[j][y])
                            F[x][y] = F[x][j] + F[j][y];
                int res = 0;
                for(int x = 1; x <= n; x ++)
                    for(int y = 1; y <= n; y ++)
                        res += F[x][y];
                ans = min(res, ans);
            }
    printf("%d\n", ans);    
    return 0;
}





    

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43

1. 14到16行，将外层则内层的循环变量依次训整为 i、j、k ，程序的运行的结果不变。（ 错误 ）

【解析】Floyd多源汇最短路算法是利用动态规划的思想，枚举每一个点作为中转点，来松弛任意两点的路径。所以第一重循环是枚举中转点，循环变量依次训整为 i、j、k 后，19行代码也要随之修改。

2. 这个程序的时间复杂度和 m 无关。（ 错误 ）

【解析】难道输入也算？

3. 20行的 ans 如果初始化为 $10^7$ 时,可能无法得到正确结果。（ 正确 ）

【解析】 ans 为任意两点最短距离之和的最小值，一共有 $\frac{(n-1)\times n}{2}$ 条边，每条边的权值最大为10000，所以最大值可能超过 $10^7$

4. 若将第27到30行的部分和31到34行的两个部分互换，程序的运行的结果不变。（ 正确 ）

【解析】程序的第26行 F[i][j] = F[j][i] = 0; ，作用是将 i、j 两点用权值为0的边连接起来，相当于合并了两点，然后使用 i、j 两点尝试松弛其它点之间的最短路径。所以，先使用 i 点或是 j 点对最终结果没有影响。

5. 若数据如数据为下面的值，则输出结果为（ 14 ）。

4 5
1 2 3
1 3 6
2 3 4
2 4 7
3 4 2

• 1
• 2
• 3
• 4
• 5
• 6

• 1
• 2
• 3
• 4
• 5
• 6

【解析】如下图所示，在 1、4 之间连接一条权值为0的边，此时个点之间的最短距离：

• f[1][2] = 3
• f[1][3] = 2 ，经过 4 点中转。
• f[1][4] = 0
• f[2][3] = 4
• f[2][4] = 3 ，经过 1 点中转
• f[3][4] = 2

最短距离之和为 14

T3.

#include <iostream>
using namespace std;
#define MOD 19260817
#define MAXN 1005
long long A[MAXN][MAXN] = {0}, sum[MAXN][MAXN] = {0};
int n, m, q;
int main() {
    A[1][1] = A[1][0] = 1;
    for(int i = 2; i <= 1000; i ++) {
        A[i][0] = 1;
        for(int j = 1; j <= i; j ++)
            A[i][j] = (A[i - 1][j] + A[i - 1][j - 1]) % MOD;
    }
    for(int i = 1; i <= 1000; i ++)
        for(int j = 1; j <= 1000; j ++)
            sum[i][j] = (sum[i - 1][j] + sum[i][j - 1]
                - sum[i - 1][j - 1] + A[i][j] + MOD) % MOD;
    int q;
    cin >> q;
    while(q --) {
        int n, m;
        cin >> n >> m;
        cout << sum[n][m] << endl;
    }
    return 0;
}





    

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26

1. 当 i<=j 时， A[i][j] 的值是0。（ 错误 ）

【解析】当 i == j 时， A[i][j] = 1 。

2. 当 i>j 时， A[i][j] 的值相当于从 i 个不同元素中取出 j 个元素的排列数。（ 错误 ）

【解析】杨辉三角（帕斯卡三角）求组合数。

3. sum[i][j] 的值（ $1<j\le 1000$ ）不小于 sum[i-1][j-1] 的值。( 错误 )

【解析】 sum[i][j] 为矩阵的前缀和，但是，因为在计算过程中需要对 MOD 求余数，所以 sum[i][j] 的值不一定大于 sum[i-1][j-1] 的值。

4. 若将第12行改为 A[i][j]=(A[i-1][j] + A[i-1][j-1] + MOD) % MOD; ，程序的运行结果不变。（ 正确 ）

【解析】加法的同余性质。

5. A[i][j] （ $1\le i\le 10,1\le j\le 10$ ）的所有元素中，最大值为是（）。

【解析】最大值为 $C_{10}^5=252$ 。

6. 若输入下列数据，则输出为（ 50 ）

1
5 3





    

• 1
• 2

• 1
• 2

【解析】求杨辉三角前5行3列的子矩阵的和，答案为50。

完善程序

T1. （封禁xxs）现有 $n$ 个xxs（编号为1到n），每个xxs都有一个关注者，第 $i$ 个xxs的关注者是 $a_i$ 。现在管理员要将其小的一些xxs的账号封禁，但需要注意的是如果封禁了第 $i$ 个人，那么为了不打草惊蛇，就不能封禁他的关注者 $a_i$ 。现在想知道最多可以封禁多少个xxs。

输入第一行是一个不超过300000的整数 $n$ ，第二行是 $n$ 个 $1$ 到 $n$ 的整数表示 $a_i$ 。

输出一行，一个整数表示答案。

#include <cstdio>
using namespace std;
#define MAXN 300005
int n, ans = 0, a[MAXN], in[MAXN] = {0};
bool vis[MAXN] = {0};
void dfs(int cur, int w) {
    if(vis[cur])
        return;
    vis[cur] = true;
    if(w == 1) ans ++;
    ①
    if(②)
        dfs(a[cur], ③);
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
       scanf("%d", &a[i]);
       in[a[i]] ++;
    }
    for(int i = 1; i <= n; i ++)
        if(!in[i]) ④;
    for(int i = 1; i <= n; i ++)
        if(⑤) dfs(i, 0);
    printf("%d\n", ans);
   return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27

【解析】题目中提示每个xxs只有一个关注者， a[i] 表示第 i 个xxs的关注者，即 a[i] 是 i 的粉丝。 in[a[i]] 表示 a[i] 的入度，可以理解为 a[i] 的粉丝个数。那么如果 in[a[i]] 不为0，为了不打草惊蛇，就不能封禁 a[i] 。

• 空①，分析第10行， if(w == 1) ans ++; ，表示封禁一个xxs。封禁后，这个xxs的关注者（ a[cur] ）的粉丝数量应该减少一个，所以应填入 in[a[cur]]-- 。
• 空②，封禁 cur 后，如果 cur 的关注者的粉丝为0，或者 cur 的粉丝数量为0，那么继续对 cur 的关注者进行处理，所以此空应判断 in[a[cur]] == 0 || w == 1 。
• 空③，如果 w == 1 ，那么对 cur 的关注者不能够直接封禁，那么递归处理时， w = 0 ；如果 w == 0 && in[a[cur]] == 0 ，此时对 a[cur] 可以封禁， w = 1 。所以此空应填入 1 - w 。
• 空④，如果 i 的粉丝为0，可以直接封禁，此空应填 dfs(i, 1) 。
• 空⑤，如果 i 还没有处理，即 vis[i] 为0，所以此空应填 !vis[i] 。

T2. 大水