欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

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

程序员文章站 2023-03-29 07:59:58
选择题十进制数114的相反数的8位二进制补码是:(10001110)【解析】整数的二进制表示的最高位为符号位,用0表示“正”,用1表示“负”正整数的补码是其二进制表示,与原码相同。负整数的补码是将其原码除符号位外的所有位取反(0变1,1变0,符号位为1不变)后加1。所以,114的二进制表示为(01110010)2(01110010)_2(01110010)2​,-114的补码表示为(10001110)2(10001110)_2(10001110)2​。小A用字母AAA表示111,B...

说明

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

选择题

T1. 十进制数114的相反数的8位二进制补码是:(10001110

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

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

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

【解析】可将字符串看做26进制数, A − Z A-Z AZ分别对应 1 − 26 1-26 126 A A AA AA按照权值展开就是 1 × 2 6 1 + 1 × 2 6 0 = 27 1\times26^1+1\times26^0=27 1×261+1×260=27 A Z = 1 × 2 6 1 + 26 × 2 6 0 = 26 + 27 = 52 AZ=1\times26^1+26\times26^0=26+27=52 AZ=1×261+26×260=26+27=52 A A A = 1 × 2 6 2 + 1 × 2 6 1 + 1 × 2 6 0 = 703 AAA=1\times26^2+1\times26^1+1\times26^0=703 AAA=1×262+1×261+1×260=703,那么 B Y T = 2 × 2 6 2 + 25 × 2 6 1 + 20 × 2 6 0 = 2022 BYT=2\times26^2+25\times26^1+20\times26^0=2022 BYT=2×262+25×261+20×260=2022

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

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

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

上式是一个等比数列求和,公比为2,最终结果为: T ( n ) = 1 − 2 × n 1 − 2 = 2 n T(n) = \frac{1-2 \times n}{1-2}=2n T(n)=1212×n=2n

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

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

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

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

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

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

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

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

  • C班派出0名风纪委员,那么A班派出的人数有4种可能, 2 − 5 2-5 25
  • C班派出1名风纪委员,那么A班派出的人数有5种可能, 1 − 5 1-5 15
  • C班派出2名风纪委员,那么A班派出的人数有5种可能, 0 − 4 0-4 04
  • C班派出3名风纪委员,那么A班派出的人数有4种可能, 0 − 3 0-3 03

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

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

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

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

【解析】一棵树也可以成为森林,所以将完全图变为一棵树,最少删掉 21 − 6 = 15 21-6=15 216=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. luo函数中,m的值不可能是奇数。(错误
  2. 将第11行的 < < <改为 < = <= <=,程序的输出结果可能会改变。(正确

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

  1. 若将第8、9、13行删除,程序的运行的结果不变。(正确

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

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

【解析】 255 = ( 11111111 ) 2 = 0 x F F 255 = (11111111)_2=0xFF 255=(11111111)2=0xFF,相当于将gu数组初始化为-1

  1. 输入数据为4 8,则输出为(8)。

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

  1. 最坏情况下,此程序的时间复杂度是( O ( m 2 n ) O(m^2n) O(m2n))。

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

  • m = 2,调用1次
  • m = 4,调用2次
  • m = 8,调用3次

    总的调用次数 = 1 + 2 + 3... =1+2+3... =1+2+3...,近似于 m 2 m^2 m2,所以时间复杂度是 O ( m 2 n ) O(m^2n) O(m2n)

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. 14到16行,将外层则内层的循环变量依次训整为i、j、k,程序的运行的结果不变。(错误

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

  1. 这个程序的时间复杂度和m无关。(错误

【解析】难道输入也算?

  1. 20行的ans如果初始化为 1 0 7 10^7 107时,可能无法得到正确结果。(正确

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

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

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

  1. 若数据如数据为下面的值,则输出结果为(14)。
4 5
1 2 3
1 3 6
2 3 4
2 4 7
3 4 2

【解析】如下图所示,在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
洛谷CSP-J/S2020初赛模拟部分题解

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. i<=j时,A[i][j]的值是0。(错误

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

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

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

  1. sum[i][j]的值( 1 < j ≤ 1000 1<j\le1000 1<j1000)不小于sum[i-1][j-1]的值。(错误)

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

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

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

  1. A[i][j] 1 ≤ i ≤ 10 , 1 ≤ j ≤ 10 1\le i\le10,1\le j\le10 1i10,1j10)的所有元素中,最大值为是()。

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

  1. 若输入下列数据,则输出为(50
1
5 3

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

完善程序

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

输入第一行是一个不超过300000的整数 n n n,第二行是 n n n 1 1 1 n n n的整数表示 a i a_i ai

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

#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]

T2. 大水

本文地址:https://blog.csdn.net/qiaoxinwei/article/details/108975693