【初赛】CSP 2020 第一轮(初赛)模拟记录
阅读原文时间:2023年07月08日阅读:4

感觉初赛不过关,洛谷上找了一套没做过的来练习。

顺便写了详细的题解。

试题用时:1h

单项选择:

第 1 题

十进制数 114 的相反数的 8 位二进制补码是:
A.10001110
B.10001101
C.01110010
D.01110011

题目好臭

\(114\) 二进制为 \(1110010\),其补码取反,符号位变 \(1\),最后 \(+1\) 即可。

答案:\(\color{green} A\)


第 2 题

以下哪个网站不是 Online Judge(在线程序判题系统)?
Online Judge 可以查看算法题目,提交自己编写的程序,然后可以获得评测机反馈的结果。
    A.Luogu
    B.Gitee
    C.LeetCode
    D.Codeforces

\(A,C,D\) 耳熟能详。

答案:\(\color{green} B\)


第 3 题

小 A 用字母 A 表示 1,B 表示 2,以此类推,用 26 表示 Z。
对于 27 以上的数字,可以用两位或者更长的字符串来对应.
例如 AA 对应 27,AB 对应 28,AZ 对应 52,AAA 对应 703……
那么 BYT 字符串对应的数字是什么?
    A.2018
    B.2020
    C.2022
    D.2024

byt?

\(ans=2\times 26^2+25 \times 26 +20=2022\)

答案:\(\color{green} C\)


第 4 题

UIM 拍摄了一张照片,其分辨率是 4096\times 2160,每一个像素都是 24 位真彩色。
在没有压缩的情况下,这张图片占用空间接近以下哪个值?
    A.8MB
    B.25MB
    C.200MB
    D.200KB

\(\frac{4096\times 2160 \times 24 bite}{1024\times 1024 \times 8} \approx 25 MB\)

答案:\(\color{green} B\)


第 5 题

在一个长度为 n 的数组中找到第 k 大的数字,平均的算法时间复杂度最低的是:
    A.O(n)
    B.O(nk)
    C.O(nlog⁡n)
    D.O(n^2)

\(D\):使用 \(O(n^2)\) 的排序,比如冒泡排序,然后输出 \(a[k]\) 即可

\(C\):使用 \(O(nlogn)\) 的排序,比如 \(sort()\),然后同上

\(B\):两层循环,依次找出 \(1st,2nd,2rd,4th…(k-1)th,kth\) 大的数即可

\(A\):利用快排的思想,每次在目标的区间内选一个数 \(i\),然后把比 \(a[i]\) 小的都放在其左,比\(a[i]\)大的都放在其右。判断 \(a[i]\) 在这一次后的位置与k的大小关系,然后选择 \(k\) 所在的那个区间重复进行。时间复杂度:\(n+n/2+n/4+n/8+…….=2n=O(n)\)

答案:\(\color{green} A\)

错解:\(\color{red} C\)


第 6 题

对于“树”这种数据结构,正确的有:
1、一个有 n 个顶点、n−1 条边的图是树
2、一个树中的两个顶点之间有且只有一条简单路径
3、树中一定存在度数不大于 1 的顶点
4、树可能存在环
    A.1、2、4
    B.1、2、3
    C.2、3
    D.1、2

\(1\):要是联通图

\(2\):对

\(3\):叶子结点

\(4\):不可能

答案:\(\color{green} C\)


第 7 题

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

类似于合并果子的最小代价。

最优方案是:\(42 = 15 + 27 = (10 + 3) + (13 + 14)\),代价为 \(42 + 15 + 27 = 84\)

蒙对了

答案:\(\color{green} A\)


第 8 题

一个二叉树的前序遍历是 HGBDAFEC,中序遍历是 BGHFAED,同时采用顺序存储结构,
即用一维数组元素存储该二叉树中的结点,则该数组的最大下标至少为( )
    A.7
    B.13
    C.15
    D.12

根据题意画出以下二叉树,并标上下标即可。

答案:\(\color{green} B\)


第 9 题

在 C++ 语言中,如果 a=1;b=0;c=1; 那么以下表达式中为 1 的是:
    A.a&&b||b&&c
    B.a+b>c||b
    C.!(!c&&(!a||b))
    D.a+b+c

手算即可。

答案:\(\color{green} C\)


第 10 题

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

每次都刚好是第一个就找到了,一共 \(k\) 次。

答案:\(\color{green} B\)


第 11 题

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

以下几种情况(依次为 \(A、B、C\)):

\(5,1,0/5,0,1/4,1,1/4,2,0/4,0,2/3,1,2/\)

\(3,2,1/3,3,0/3,0,3/2,4,0/2,3,1/2,1,3/\)

\(2,2,2/1,4,1/1,3,2/1,2,3/0,4,2/0,3,3\)

答案:\(\color{green} D\)


第 12 题

以下哪种排序算法的时间复杂度是 O(n^2)?
    A.计数排序
    B.插入排序
    C.希尔排序
    D.归并排序

送分。

答案:\(\color{green} B\)


第 13 题

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

\(rand()\mod(b-a)\) 可产生 \(0\) 到 \(b-a-1\) 的随机数,再 \(+a\) 即可。

答案:\(\color{green} A\)


第 14 题

一个 7 个顶点的完全图需要至少删掉多少条边才能变为森林?
    A.16
    B.21
    C.15
    D.6

首先,有七个点的完全图一共有 \(1+2+3+4+5+6=21\) 条边。

但注意:森林可以只有一棵树!!

所以 \(7\) 个节点的树有 \(6\) 条边,应删除 \(21-6=15\) 条边

答案:\(\color{green} C\)

错解:\(\color{red} A\)


第 15 题

2020 年 8 月,第( )届全国青少年信息学奥林匹克竞赛在( )举行?
    A.26,广州
    B.26,长沙
    C.37,广州
    D.37,长沙

人品题。

答案:\(\color{green} D\)

错解:\(\color{red} C\)


阅读程序:

第 16 题

#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、(1 分)luo 函数中,\(m\) 的值不可能是奇数。( )

输入一个奇数就好了。

答案:\(\color{green} F\)

2、(1 分)若将第 \(11\) 行的 \(<\) 改为 \(<=\),程序的输出结果可能会改变。( )

显然,循环会多执行。

答案:\(\color{green} T\)

3、若将第 \(8,9,13\) 行删除,程序的运行的结果不变( )

只是去掉了记忆化搜索的优化,答案是不会变的。只是可能 TLE

答案:\(\color{green} T\)

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

涨芝士了。

答案:\(\color{green} T\)

错解:\(\color{red} F\)

选择题

1、(4 分)若输入数据为 4 8,则输出为( )。

A.7   B.8   C.15   D.16

手算即可。

答案:\(\color{green} B\)

2、最坏情况下,此程序的时间复杂度是( )。

A.O(m^2 n)
B.O(nm!)
C.O(n^2)
D.O(n^2 m)

记忆化计算 \(nm\) 个值,每次计算复杂度为 \(O(m)\),所以为\(O(m^2n)\)

答案:\(\color{green} A\)

错解:\(\color{red} B\)


第 17 题

#include<bits/stdc++.h>
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 < x; y++)
          res += F[x][y];
      ans = min(res, ans);
    }
  printf("%d\n", ans);
  return 0;
}

看到 \(k,i,j\) 循环直接 \(Floyd\)。

判断题

1、(1 分)\(14\) 到 \(16\) 行,将外层到内层的循环变量依次调整为 \(i,j,k\),程序的运行的结果不变。( )

\(Floyd\) 算法,显然不行。

答案:\(\color{green} F\)

2、这个程序的时间复杂度和 \(m\) 无关。( )

要枚举边,于 \(m\) 有关,但影响很小。

答案:\(\color{green} F\)

3、\(20\) 行的 \(ans\) 如果初始化为 \(10^7\) 时,可能无法得到正确结果。( )

一条路 \(n \times w =10^6\),再 \(\times n\) 到 \(10^8\),不够。我当时少乘了 n

答案:\(\color{green} F\)

错解:\(\color{red} T\)

4、若将第 27 到 30 行的部分和 31 到 34 行的两个部分互换,程序的运行的结果不变。( )

都是松弛操作,前后顺序无所谓。

答案:\(\color{green} T\)

选择题

1、若输入数据为 4 5/1 2 3/1 3 6/2 3 4/2 4 7/3 4 2(其中“/”为换行符),则输出为( )。

A.14    B.18    C.21    D.28

好像得手算

答案:\(\color{green} A\)

错解:\(\color{red} B\)

2、这个程序使用了( )算法。

A.Floyd    B.Dijkstra    C.Prim    D.Kruskal

显然。

答案:\(\color{green} A\)


第 18 题

#include<bits/stdc++.h>
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、(1 分)当 \(i\leq j\) 时,\(A[i][j]\) 的值是 \(0\)。( )

\(i=j\) 时值为 \(1\) 。这个s*脑抽了

答案:\(\color{green} F\)

错解:\(\color{red} T\)

2、当 \(i>j\) 时,\(A[i][j]\) 的值相当于从 \(i\) 个不同元素中取出 \(j\) 个元素的排列数。( )

是组合数而不是排列数。

答案:\(\color{green} F\)

3、\(sum[i][j]\) 的值(\(1<j<i\leq 1000\))不小于 \(sum[i-1][j-1]\) 的值。( )

有取模运算,所以不一定。

答案:\(\color{green} F\)

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

加上 \(MOD\) 再取模显然不变。

答案:\(\color{green} T\)

选择题

1、(4 分)\(A[i][j](1\leq i\leq 10, 1\leq j\leq 10)\)的所有元素中,最大值是( )。

A.126    B.276    C.252    D.210

手算即可,即杨辉三角前 \(11\) 行最大的数。

答案:\(\color{green} C\)

2、若输入数据为 1/5 3(其中“/”为换行符),则输出为( )。

A.10    B.35    C.50    D.24

用画好的杨辉三角算一下前缀和即可(注意第一列不用加)。

答案:\(\color{green} C\)

完善程序:

第 19 题

(封禁 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.
    A.a[cur]=cur;
    B.in[a[cur]]=0;
    C.in[a[cur]]--;
    D.in[cur]--;
2.
    A.in[a[cur]]!=0||w==1
    B.in[a[cur]]==0||w==0
    C.in[a[cur]]!=0||w==0
    D.in[a[cur]]==0||w==1
3.
    A.0
    B.1
    C.w
    D.1-w
4.
    A.dfs(i,1)
    B.dfs(i,0)
    C.dfs(a[i],1)
    D.dfs(a[i],0)
5.
    A.!in[i]
    B.in[i]
    C.!vis[i]
    D.vis[i]

\(vis\) 数组表示有没有遍历到,\(in\) 数组表示一个点的入度,\(w\) 记录有没有被删除。

1:这个点遍历了,相当于去掉它

2:如果这个点没有入度了,相当于没有限制了,可以直接跑。如果 \(w=0\),说明它的父亲是没有删除的,那么自然它也可以遍历

3:父亲删除了,自己不能删;父亲没删,自己可以删

4:每个没有父亲的点开始遍历

5:把没有遍历到的点遍历完

答案:\(\color{green} {CDDAC}\)

错解:\(\color{green} C\)\(\color{red} B\)\(\color{green} {DAC}\)


第 20 题:

(烧作业)某课作业布置了 \(N(3\leq N\leq 100000)\) 个题目,第 \(i\) 题对应的得分是 \(a_i\)。作业的总得分的计算方式为去掉作业中得分最小的一个题,剩下其它所有题目得分的平均值。但很不幸小 A 遇到了一场火灾,前 \(K(1\leq K\leq N-2)\) 个题目被烧了,无法记录得分。小 A 想知道,\(K\) 是多少时,可以得到最高的作业得分? 作业被烧了前 \(K\) 页,这时的得分是从第 \(K+1\) 页到最后一页中,去除最小得分后取平均值。

输入第一行是整数 \(N\),第二行是 \(n\) 个不超过 \(10000\) 的非负整数表示 \(a_i\)。

输出一行,若干个整数表示答案。如果有多个 \(K\),请依次升序输出。

#include <cstdio>
#include <cmath>
#define min(a,b) (a<b?a:b)
#define MAXN 100002
using namespace std;
int n, k[MAXN], cnt = 0;
int s[MAXN], minScore, sum;
double maxAverage = 0, nowAverage;
int main() {
   scanf("%d", &n);
   for(int i = 1; i <= n; i++)
       scanf("%d", &s[i]);
   minScore = s[n];
   ①________;
   for(int i = n - 1; i >= 2; i--) {
       minScore = min(minScore, s[i]);
       ②_________;
       nowAverage = ③_________;
       if(nowAverage > maxAverage) {
           ④__________
           maxAverage = nowAverage;
       } else if(fabs(nowAverage - maxAverage) < 1e-6)
           ⑤_________;
   }
   for(int i = cnt; i >= 1; i--)
       printf("%d\n", k[i]);
   return 0;
}



1.
    A.sum=n
    B.sum=s[1]
    C.sum=s[n]
    D.sum=0

2.
    A.sum=maxAverage*(n-i)
    B.sum+=s[i]
    C.sum+=s[n-i]
    D.sum=s[i]+minScore

3.
    A.(double)(sum+minScore)/(n-i)
    B.sum*1.0/(n-i)
    C.(int)(sum-minScore)/(n-i)
    D.(double)(sum-minScore)/(n-i)

4.
    A.k[++cnt]=i;
    B.k[cnt++]=i-1
    C.cnt=1;k[cnt]=i-1;
    D.cnt=0;k[cnt]=i;

5.
    A.k[cnt++]=i;
    B.k[++cnt]=i-1;
    C.k[cnt++]=n-i;
    D.k[cnt]=i;

这才是第一题吧

1:从后往前,初值赋 \(s[n]\)。

2:总和加上当前的 \(s[i]\)。

3:算当前平均分,总和减最低分再除以数量。分数转一下 \(double\) 即可。

4:出现更优解就更新最优解和目前答案。

5:出现一样优的解就加上。

答案:\(\color{green} {CBDCB}\)

我才不会告诉你才考了 81

G L & H F !