洛谷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 A−Z分别对应 1 − 26 1-26 1−26, 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)=1−21−2×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 2−5
- C班派出1名风纪委员,那么A班派出的人数有5种可能, 1 − 5 1-5 1−5
- C班派出2名风纪委员,那么A班派出的人数有5种可能, 0 − 4 0-4 0−4
- C班派出3名风纪委员,那么A班派出的人数有4种可能, 0 − 3 0-3 0−3
所以一共有
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()%(b−a)+a
T14. 一个7个顶点的完全图需要至少删掉(15
)条边才能变为森林?
【解析】一棵树也可以成为森林,所以将完全图变为一棵树,最少删掉 21 − 6 = 15 21-6=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 = 0 x F F 255 = (11111111)_2=0xFF 255=(11111111)2=0xFF,相当于将
gu
数组初始化为-1
。
- 输入数据为4 8,则输出为(
8
)。
【解析】画递归树模拟即可。
- 最坏情况下,此程序的时间复杂度是( 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;
}
- 14到16行,将外层则内层的循环变量依次训整为
i、j、k
,程序的运行的结果不变。(错误
)
【解析】Floyd多源汇最短路算法是利用动态规划的思想,枚举每一个点作为中转点,来松弛任意两点的路径。所以第一重循环是枚举中转点,循环变量依次训整为
i、j、k
后,19行代码也要随之修改。
- 这个程序的时间复杂度和
m
无关。(错误
)
【解析】难道输入也算?
- 20行的
ans
如果初始化为 1 0 7 10^7 107时,可能无法得到正确结果。(正确
)
【解析】
ans
为任意两点最短距离之和的最小值,一共有 ( n − 1 ) × n 2 \frac{(n-1)\times n}{2} 2(n−1)×n条边,每条边的权值最大为10000,所以最大值可能超过 1 0 7 10^7 107
- 若将第27到30行的部分和31到34行的两个部分互换,程序的运行的结果不变。(
正确
)
【解析】程序的第26行
F[i][j] = F[j][i] = 0;
,作用是将i、j
两点用权值为0的边连接起来,相当于合并了两点,然后使用i、j
两点尝试松弛其它点之间的最短路径。所以,先使用i
点或是j
点对最终结果没有影响。
- 若数据如数据为下面的值,则输出结果为(
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
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 ≤ 1000 1<j\le1000 1<j≤1000)不小于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 ≤ i ≤ 10 , 1 ≤ j ≤ 10 1\le i\le10,1\le j\le10 1≤i≤10,1≤j≤10)的所有元素中,最大值为是()。
【解析】最大值为 C 10 5 = 252 C_{10}^5=252 C105=252。
- 若输入下列数据,则输出为(
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
上一篇: 为了排名网站采取大量原创内容是否是最佳的优化路径?
下一篇: 营销策划 电子商务网站的捆绑销售策略