写在前面的话
快要CSP了,最近疯狂刷题中…
终于 抽出时间 乘爸妈不在 写了一篇题解
题面
如需做题,请到以下网站自行练习。
本博客只提供讲解。
洛谷有题
初赛真题 - 信奥赛题库
题解
答案合集
题号 | |||||
---|---|---|---|---|---|
1~5: | A | A | D | C | C |
6~10: | B | A | A | A | A |
11~15: | A | D | C | A | A |
16~20: | 对 | 错 | 对 | 错 | A |
21~25: | D | 错 | 错 | 对 | D |
26~30: | B | D | 错 | 对 | 错 |
31~35: | B | C | C | C | C |
36~40: | C | A | C | B | D |
41~43: | A | A | B | 😛 | 😛 |
单项选择题
1
在内存储器中每个存储单元都被赋予一个唯一的序号,称为()。
A.地址
B.序号
C.下标
D.编号
没啥好说的,这个只能背了。
2
编译器的主要功能是( )。
A. 将源程序翻译成机器指令代码
B. 将源程序重新组合
C. 将低级语言翻译成高级语言
D. 将一种高级语言翻译成另一种高级语言
作为C/C++/Pascal
选手,这应该是必会知识点
3
设 x=true,y=true,z=false,以下逻辑运算表达式值为真的是( )。
A. (y∨z)∧x∧z
B. x∧(z∨y) ∧z
C. (x∧y) ∧z
D. (x∧y)∨(z∨x)
这一题没什么难点,唯一就是分不清 与/或
这个没有办法了,背吧
∨是与,∧是或
4
现有一张分辨率为 2048 × 1024 2048×1024 2048×1024 像素的 32 32 32 位真彩色图像。请问要存储这张图像,需要多大的存储空间?( )。
A. 16MB
B. 4MB
C. 8MB
D. 2MB
这似乎只是一道计算题。
2048
×
1024
2048×1024
2048×1024 即有这么多像素点
32
32
32位 即每个点32个
b
i
t
bit
bit(
8
b
i
t
8bit
8bit ==
1
B
1B
1B)
计算可知结果为8MB
5
冒泡排序算法的伪代码如下:
输入:数组L, n ≥ k。输出:按非递减顺序排序的 L。
算法 BubbleSort:
1. FLAG ← n //标记被交换的最后元素位置
2. while FLAG > 1 do
3. k ← FLAG -1
4. FLAG ← 1
5. for j=1 to k do
6. if L(j) > L(j+1) then do
7. L(j) ↔ L(j+1)
8. FLAG ← j
对 n 个数用以上冒泡排序算法进行排序,最少需要比较多少次?( )。
A. n²
B. n-2
C. n-1
D. n
最好情况即为原数组已有序,由于设置了 F L A G FLAG FLAG标记位置,第一遍循环之后即会结束,而第一遍循环依次比较了:1和2、2和3…… N − 1 N-1 N−1和 N N N,共计 N − 1 N-1 N−1次。
6
设 A 是 n 个实数的数组,考虑下面的递归算法:
XYZ (A[1..n])
1. if n=1 then return A[1]
2. else temp ← XYZ (A[1..n-1])
3. if temp < A[n]
4. then return temp
5. else return A[n]
请问算法 XYZ 的输出是什么?()。
A. A 数组的平均
B. A 数组的最小值
C. A 数组的中值
D. A 数组的最大值
可以看出,该递归的返回值是 数组A的一段 中的两个元素(不用管具体是啥)中较小的一个。
而当这个“一段”为整个A数组是,即为数组中的最小值。
7
链表不具有的特点是()。
A. 可随机访问任一元素
B. 不必事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比
链表的特点:
- 可以充分利用计算机内存空间,实现灵活的内存动态管理。
- 不能随机读取。
- 空间开销比较大。
- 插入和删除都比较快,查找比较慢。
于是乎,答案出来了
8
有 10 个顶点的无向图至少应该有( )条边才能确保是一个连通图。
A. 9
B. 10
C. 11
D. 12
几乎是常识了。
一个N个节点的图(无重边,无自环):
- 至少要有N-1条边才可能联通
- 至少要有N条边才能确保有一个环。
- 最多可以有 N(N-1) / 2 条边
9
二进制数 1011 转换成十进制数是( )。
A. 11
B. 10
C. 13
D. 12
8421法转换即可:
8 4 2 1
1 0 1 1
↓ ↓ ↓ ↓
8+0+2+1
→
11
11
11
10
5 个小朋友并排站成一列,其中有两个小朋友是双胞胎,如果要求这两个双胞胎必须相邻,则有( )种不同排列方法?
A. 48
B. 36
C. 24
D. 72
首先将双胞胎当成一个人,即变为4个小朋友排队,共有C(4, 4)种排列方法
而双胞胎又存在C(2, 2)种排列方法
根据乘法原理,共有C(4, 4) * C(2, 2)种排列方法
11
下图中所使用的数据结构是( )。
A. 栈
B. 队列
C. 二叉树
D. 哈希表
看到了压入
、弹出
即可确定为
栈
/
队列
栈/队列
栈/队列,又看到只有一个开口,确定为栈。
12
独根树的高度为 1。具有 61 个结点的完全二叉树的高度为( )。
A. 7
B. 8
C. 5
D. 6
独根树高度为1,高度为X的满二叉树共有2X - 1 个节点,即:
高度为5的满二叉树有31个节点,高度为6的满二叉树有63个节点,31 < 61 < 63,所以,该完全二叉树高度为6.
13
干支纪年法是中国传统的纪年方法,由 10 个天干和 12 个地支组合成 60 个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。
- 天干 =(公历年份)除以 10 所得余数
- 地支 =(公历年份)除以 12 所得余数
例如,今年是 2020 年,2020 除以 10 余数为 0,查表为"庚”;2020 除以 12,余数为 4,查表为“子” 所以今年是庚子年。
请问 1949 年的天干地支是( )
A. 己酉
B. 己亥
C. 己丑
D. 己卯
除法计算并取余即可(小学数学)
14
10 个三好学生名额分配到 7 个班级,每个班级至少有一个名额,一共有( )种不同的分配方案。
A. 84
B. 72
C. 56
D. 504
人肉暴力即可。
15
第 15 题
有五副不同颜色的手套(共 10 只手套,每副手套左右手各 1 只),一次性从中取 6 只手套,请问恰好能配成两副手套的不同取法有( )种。
A. 120
B. 180
C. 150
D. 30
计算方法如下:
- 随机取一双手套(5种方案)
- 再随机取一双手套(4种方案)
- 除以二(先选A再选B && 先选B再选A 属于同一种方案)
- 在剩下的6只手套中随机取一只(6种方案)
- 在剩下的4只颜色与刚刚取出来的一只不同的手套中随机选取一只(4种方案)
- 除以二(同理)
阅读程序题
一
#include <cstdlib>
#include <iostream>
using namespace std;
char encoder[26] = {'C','S','P',0};
char decoder[26];
string st;
int main() {
int k = 0;
for (int i = 0; i < 26; ++i)
if (encoder[i] != 0) ++k;
for (char x ='A'; x <= 'Z'; ++x) {
bool flag = true;
for (int i = 0; i < 26; ++i)
if (encoder[i] ==x) {
flag = false;
break;
}
if (flag) {
encoder[k]= x;
++k;
}
}
for (int i = 0; i < 26; ++i)
decoder[encoder[i]- 'A'] = i + 'A';
cin >> st;
for (int i = 0; i < st.length( ); ++i)
st[i] = decoder[st[i] -'A'];
cout << st;
return 0;
}
16
输入的字符串应当只由大写字母组成,否则在访问数组时可能越界。(正确)
若输入字符串中的字符小于A,下标为负,越界。
若输入字符串中的字符大于A,下标大于26,越界。
17
若输入的字符串不是空串,则输入的字符串与输出的字符串一定不一样。(错误)
encoder = "CSPABDEFGHIJKLMNOQRTUVWXYZ"
decoder = "DEAFGHIJKLMNOPQCRSBTUVWXYZ"
理解代码后发现:只要所有输入的字符在T
到Z
之间(包括)则数据不会有改变
18
将第 12 行的 i < 26 改为 i < 16,程序运行结果不会改变。(正确)
执行第12行代码时,encoder数组只有前三位符合条件,故不会改变结果
19
将第 26 行的 i < 26 改为 i < 16,程序运行结果不会改变。(错误)
第26行时,encoder已经全部有效了,改变i无疑会改变decoder从而改变结果。
20
若输出的字符串为 ABCABCABCA,则下列说法正确的是( )。
A. 输入的字符串中既有 S 又有 P
B. 输入的字符串中既有 S 又有 B
C. 输入的字符串中既有 A 又有 P
D. 输入的字符串中既有 A 又有 B
根据decoder倒推即可
21
若输出的字符串为 CSPCSPCSPCSP,则下列说法正确的是( )。
A. 输入的字符串中既有 P 又有 K
B. 输入的字符串中既有 J 又有 R
C. 输入的字符串中既有 J 又有 K
D. 输入的字符串中既有 P 又有 R
同上题
二
#include <iostream>
using namespace std;
long long n, ans;
int k, len;
long long d[1000000];
int main() {
cin >> n >> k;
d[0] = 0;
len= 1;
ans = 0;
for (long long i = 0; i <n; ++i) {
++d[0];
for (int j = 0; j + 1<len; ++j) {
if (d[j] == k) {
d[j] = 0;
d[j + 1] += 1;
++ans;
}
}
if (d[len- 1] == k) {
d[len - 1] = 0;
d[len] =1;
++len;
++ans;
}
}
cout << ans << endl;
return 0;
}
假设输入的 n 是不超过 262的正整数,k 都是不超过 10000 的正整数,完成下面的判断题和单选题:
这一题还是很有意思的,目的是将10进制数n转化为k进制数,len为数字长度
22
若 k=1,则输出 ans 时,len=n。(错误)
首先,明白了该题代码的目的之后,我们发现:“一进制”不存在,会有bug
而bug有两种情况:全部堆积在第二位
o
r
or
or无限进位
这个程序是第一种情况。
所以len = 2
23
若 k>1,则输出 ans 时,len —定小于 n。(错误)
当k = 2, n = 1时,len = 1
len不小于n
24
若 k>1,则输出 ans 时,k len —定大于 n。(正确)
k是进制数,len是字符长度,klen在k进制下即为 1000000…000(k个0)
那么,该数的长度为len+1,一定大于n(长度为len)
25
若输入的 n 等于:1015,输入的 k 为 1,则输出等于()。
A. 1
B. (1030−1015)/2
C. (1030+1015)/2
D. 1015
1进制,所有的数都堆积在第二位,共计进位1015次。
26
若输入的 n 等于 205,891,132,094,649(即 3^ 30^ ),输入的 k 为 3,则输出等于( )。
A. 330
B. (330 −1)/2
C. 330 −1
D. (330 +1)/2
330在3进制中,为100000…000(30个0)
而输出为进位次数,计算方法如下:
第一位进位1次,第二位进位3次,第三位进位33次……
共1 + 31 + 32 + …… + 329次
根据等比序列求和公式:(330 −1)/2
27
若输入的 n 等于 100,010,002,000,090,输入的 k 为 10,则输出等于( )。
A. 11,112,222,444,543
B. 11,122,222,444,453
C. 11,122,222,444,543
D. 11,112,222,444,453
搞明白程序的目的之后,唯一的难点就是确定这个数字进位了几次了。
那问题来了:怎么确定呢?
第一位进位了 100,010,002,000,090 / 10次
第二位 100,010,002,000,090 / 100次
……
求和即可
三
#include <algorithm>
#include <iostream>
using namespace std;
int n;
int d[50][2];
int ans;
void dfs(int n, int sum) {
if (n == 1) {
ans = max(sum, ans);
return;
}
for (int i = 1; i < n; ++i) {
int a = d[i - 1][0], b = d[i - 1][1];
int x = d[i][0], y = d[i][1];
d[i - 1][0] = a + x;
d[i - 1][1] = b + y;
for (int j = i; j < n - 1; ++j)
d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
int s = a + x + abs(b - y);
dfs(n - 1, sum + s);
for (int j = n - 1; j > i; --j)
d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
d[i - 1][0] = a, d[i - 1][1] = b;
d[i][0] = x, d[i][1] = y;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i][0];
for (int i = 0; i < n;++i)
cin >> d[i][1];
ans = 0;
dfs(n, 0);
cout << ans << endl;
return 0;
}
假设输入的 n 是不超过 50 的正整数,d[i][0]
、d[i][i]
都是不超过 10000 的正整数,完成下面的判断题和单选题:
28
若输入 n 为 0,此程序可能会死循环或发生运行错误。(错误)
有人说:0它会死递归,因为它永远到不了终止条件。
我回答:他也不会往下递归啊!(看第14行)
29
若输入 n 为 20,接下来的输入全为 0,则输出为 0。(正确)
它只有相互加、相互减,全为0,当然不会改变。
30
输出的数一定不小于输入的
d[i][0]
和d[i][1]
的任意一个。(错误)
d[i][1]
在进行减法,可能变小d[i][0]
在进行加法,也可能变小(负数)
反例:
0 0
5 5
输出:
0
31
若输入的 n 为 20,接下来的输入是 20 个 9 和 20 个 00,则输出为( )。
A. 1890
B. 1881
C. 1908
D. 1917
这一题考察对d[i][0]
的理解。d[i][0]
的最佳情况即每次堆叠一个到d[0][0]
上,即为:
9
∗
2
+
9
∗
3
+
9
∗
4
+
…
…
+
9
∗
20
=
1881
9 * 2 + 9 * 3 + 9 * 4 +……+ 9 * 20 = 1881
9∗2+9∗3+9∗4+……+9∗20=1881
32
若输入的 nn 为 3030,接下来的输入是 3030 个 00 和 3030 个 55,则输出为( )。
A. 2000
B. 2010
C. 2030
D. 2020
这题考察的就是对d[i][1]
的理解了。d[i][1]
的最好情况如下:
第一层:5 - 5 = 0
第二成:5 - 5 + 5 = 5 * 1
第三层:10 - 5 + 5 = 5 * 2
……
最后:5 * 29 - 5 = 5 * 28
t o t a l = 5 ∗ ( 1 + 2 + 3 + . . . + 27 + 28 ) = 2030 total = 5 * (1 + 2 + 3 + ... + 27 + 28) = 2030 total=5∗(1+2+3+...+27+28)=2030
33
若输入的 n 为 15,接下来的输入是 15 到 1,以及 15 到 1,则输出为( )。
A. 2440
B. 2220
C. 2240
D. 2420
这里分两列考虑即可:
-
d[i][0]
:
第一次堆叠:15 + 14
第二次堆叠:15 + 14 + 13
第三次堆叠:15 + 14 + 13 + 12
……
最后:15 + 14 + 13 + 12 + …… + 2 + 1
t o t a l = 15 ∗ 15 + 14 ∗ 14 + 13 ∗ 13 + . . . + 2 ∗ 2 + 1 ∗ 1 = 1225 total = 15 * 15 + 14 * 14 + 13 * 13 + ... + 2 * 2 + 1 * 1 = 1225 total=15∗15+14∗14+13∗13+...+2∗2+1∗1=1225 -
d[i][1]
第一层递归:1
第二层递归:15 + 1
第三层递归:15 + 14 + 1
……
最后:15 + 14 + 13 + …… + 4 + 3 + 1
t o t a l = 15 ∗ 13 + 14 ∗ 12 + 13 ∗ 11 + . . . + 4 ∗ 2 + 3 ∗ 1 + 1 ∗ 14 = 1015 total = 15 * 13 + 14 * 12 + 13 * 11 + ... + 4 * 2 + 3 * 1 + 1 * 14 = 1015 total=15∗13+14∗12+13∗11+...+4∗2+3∗1+1∗14=1015
最后的最后:
t
o
t
a
l
—
t
o
t
a
l
=
1015
+
1225
=
2240
total—total = 1015 + 1225 = 2240
total—total=1015+1225=2240
完善程序题
一
(质因数分解)给出正整数 n,请输出将 n 质因数分解的结果,结果从小到大输出。
例如:输入 n=120,程序应该输出 2 2 2 3 5,表示:*120=2×2×2×3×5。输入保证 2≤n≤109 。
提示:先从小到大枚举变量 i,然后用 i 不停试除 n 来寻找所有的质因子。
试补全程序。
#include <cstdio>
using namespace std;
int n, i;
int main() {
scanf("%d", &n);
for(i = ①; ② <=n; i ++){
③{
printf("%d ", i);
n = n / i;
}
}
if(④)
printf("%d ", ⑤);
return 0;
}
34
①处应填():
A. 1
B. n-1
C. 2
D. 0
此处循环变量i应该是用于枚举n的质因数,0
、1
不是质数,排除;n-1
不符合题意,排除。
35
②处应填():
A. n / i
B. n / (i * i)
C. i * i
D. i * i * i
此处是循环终止条件,在i>=1的情况下,n / i
、n / (i * i)
一定小于等于n,会造成死循环,故排除;而在i * i * i > n
时终止循环则可能造成分解质因数不彻底的情况,例如:i = 2, n = 4,若选D则会在此时终止循环,造成逻辑错误
36
③处应填():
A. if(n % i == 0)
B. if(i * i <= n)
C. while(n % i == 0)
D. while(i * i <= n)
首先,此处应当用while
,否则可能造成分解不彻底,其次,i为n的因数的判断方法为n % i == 0
,故选C
37
④处应填():
A. n>1
B. n<=1
C. i<n/i
D. i+i<=n
n == 1
说明已经彻底分解;否则说明,现在的n也是答案之一。
38
⑤处应填():
A. 2
B. n/i
C. n
D. i
理由同上
二
(最小区间覆盖)给出 n 个区间,第 i 个区间的左右端点是 [ai,bi]。现在要在这些区间中选出若干个,使得区间 [0,m] 被所选区间的并覆盖(即每一个0≤i≤m 都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。
输入第一行包含两个整数 n 和 m (1≤n≤5000, 1≤m≤109 )
接下来 n 行,每行两个整数 ai, bi (0≤ai, bi ≤ m)。
提示:使用贪心法解决这个问题。先用 O(n2) 的时间复杂度排序,然后贪心选择这些区间。
试补全程序。
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if (①)
{
segment t = A[j];
②
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i].b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if (③)
A[p++] = A[i];
n = p;
int ans = 0, r = 0;
int q = 0;
while (r < m)
{
while (④)
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}
这其实就是个算法模板。背就完了!
39
①处应填():
A. A[j].b>A[j-1].b
B. A[j].a<A[j-1].a
C. A[j].a>A[j-1].a
D. A[j].b<A[j-1].b
根据左端点升序排序。(最小区间覆盖 必备)
40
②处应填():
A. A[j+1]=A[j];A[j]=t;
B. A[j-1]=A[j];A[j]=t;
C. A[j]=A[j+1];A[j+1]=t;
D. A[j]=A[j-1];A[j-1]=t;
这就是手动模拟一下
s
w
a
p
swap
swap,有手就行。
就算不会模拟,冒泡排序、选择排序、快速排序 总学过一个的吧?!照搬不完了吗?
41
③处应填():
A. A[i].b>A[p-1].b
B. A[i].b<A[i-1].b
C. A[i].b>A[i-1].b
D. A[i].b<A[p-1].b
此处的操作是删除 被前一个区间覆盖了的区间。(左端点比前一个区间靠后,右端点比其靠前)
42
④处应填():
A. q+1<n&&A[q+1].a<=r
B. q+1<n&&A[q+1].b<=r
C. q<n&&A[q].a<=r
D. q<n&&A[q].b<=r
此处是选择 左端点能够与已选区间链接 且右端点尽可能靠右的区间(贪心思想)
43
⑤处应填():
A. r=max(r,A[q+1].b)
B. r=max(r,A[q].b)
C. r=max(r,A[q+1].a)
D. q++
将所选区间的右端点更新到新选择的区间的右端点文章来源:https://www.toymoban.com/news/detail-672299.html
尾声
写完了
欢迎差评、批评,不欢迎喷子。
写的怎么样?文章来源地址https://www.toymoban.com/news/detail-672299.html
到了这里,关于2020 CSP - J初赛 题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!