感觉初赛不过关,洛谷上找了一套没做过的来练习。
顺便写了详细的题解。
试题用时:1h
十进制数 114 的相反数的 8 位二进制补码是:
A.10001110
B.10001101
C.01110010
D.01110011
题目好臭
\(114\) 二进制为 \(1110010\),其补码取反,符号位变 \(1\),最后 \(+1\) 即可。
答案:\(\color{green} A\)
以下哪个网站不是 Online Judge(在线程序判题系统)?
Online Judge 可以查看算法题目,提交自己编写的程序,然后可以获得评测机反馈的结果。
A.Luogu
B.Gitee
C.LeetCode
D.Codeforces
\(A,C,D\) 耳熟能详。
答案:\(\color{green} B\)
小 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\)
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\)
在一个长度为 n 的数组中找到第 k 大的数字,平均的算法时间复杂度最低的是:
A.O(n)
B.O(nk)
C.O(nlogn)
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\)
对于“树”这种数据结构,正确的有:
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\)
博艾中学进行了一次信息学会考测试,其优、良、及格、不及格的试卷数量分别为 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\)
一个二叉树的前序遍历是 HGBDAFEC,中序遍历是 BGHFAED,同时采用顺序存储结构,
即用一维数组元素存储该二叉树中的结点,则该数组的最大下标至少为( )
A.7
B.13
C.15
D.12
根据题意画出以下二叉树,并标上下标即可。
答案:\(\color{green} B\)
在 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\)
在一个初始长度为 n 的链表中连续进行 k 次操作,每次操作是读入两个数字 ai 和 bi,
在链表中找到元素为 ai 的结点(假设一定可以找到),然后将 b i这个元素插入到这个结点前面。
在最理想的情况下,链表访问的结点数量最少可能是多少(不算将要插入的结点)?
A.n 次
B.k 次
C.nk 次
D.n+k 次
每次都刚好是第一个就找到了,一共 \(k\) 次。
答案:\(\color{green} B\)
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\)
以下哪种排序算法的时间复杂度是 O(n^2)?
A.计数排序
B.插入排序
C.希尔排序
D.归并排序
送分。
答案:\(\color{green} B\)
已知 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\)
一个 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\)
2020 年 8 月,第( )届全国青少年信息学奥林匹克竞赛在( )举行?
A.26,广州
B.26,长沙
C.37,广州
D.37,长沙
人品题。
答案:\(\color{green} D\)
错解:\(\color{red} C\)
#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\)
#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\)
#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\)
(封禁 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}\)
(烧作业)某课作业布置了 \(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
手机扫一扫
移动阅读更方便
你可能感兴趣的文章