洛谷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以上的数字，可以用两位或者更长的字符来对应，例加 $A A$ 对应 $27$ ， $A B$ 对应 $28$ ， $A Z$ 对应 $52$ ， $A A A$ 对应 $703$ ，…，那么 $B Y T$ 字符串对应的数字是（2022）

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

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

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

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

上式是一个等比数列求和，公比为2，最终结果为： $\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\times2 = 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;
}

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

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

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

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

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

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

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

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

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

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

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

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;
}

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

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

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

【解析】难道输入也算？

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

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

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

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

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

【解析】如下图所示，在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;
}

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

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

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

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

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

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

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

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

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

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

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

1
5 3

【解析】求杨辉三角前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;
}

【解析】题目中提示每个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]。