2020 CSP-J 初赛题目全解析（chasem）

2020普及组初赛

选择题：

1.内存编号，就是地址。

2.编译器的作用是讲源程序翻译成机器指令代码，将高级语言转换成低级语言。

4.一位即 1 比特,1字节=8比特。 即2048 * 1024 * 32 / 8 / 1024 /1024 MB

5. 冒泡排序比较次数最少的情况：原本所有数字的顺序就是对的，一趟比较结束，所以是比较 n-1 次。

6. int XYZ(int a[],int n)//n个元素 从下标 1 开始存储 
   {if(n==1)return a[n]；else{int temp=XYZ(a,n-1);return min(temp,a[n]);} 
   }
   

代码翻译后如上图所示，即求最小值。

8.n个节点连通，可以当成是连成一条线，这样需要的边最少。

10.这是一个排列问题，可以把双胞胎绑一块，当成一个人，然后每次排列完交换他们两个人的顺序。总排列数就是：A₄⁴ * 2

14.每班先给一个名额，问题就变成了7个班级分三个名额。

三个名额：可以分成三份，两份，或者一份。

总方案数就是：C ₇³ +C ₇² * 2 +C ₇¹ = 35 + 42 + 7 = 84

15.这是一个组合问题，先选出两幅成套的，然后剩余6只选一只，然后剩下的不能匹配成套的4只手套选1只，这里会出现后面两只手套先选后选导致的重复，所以要方案数要除以二。

总方案数就是：（ C ₅² * C ₆¹ +* C ₄¹ ）/ 2 = 120

阅读程序1：

/*
这个程序通过encoder,decoder两次转换产生一个乱序字符串，利用乱序字符串加密encoder ="CSPABDEFGHIKLMNOQRTUVWXYZ"
decoder ="DEAFGHIKLMNOPQCRSBTUVWXYZ"*/
#include 
#include 
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)//每个字符放到encoder[i] 与 字符'A'的差处  产生decoder字符数组decoder[encoder[i] - 'A'] = i + 'A';cin >> st;for (int i = 0; i < st.length(); ++i) //利用decoder再加密输入字串st[i] = decoder[st[i] - 'A'];cout << st;return 0;
}

16.因为数组大小为26，所以只能是大写字母

17.根据decoder字符串的值我们会发现，从字符T开始后面的字母都不会在这里被替换。

18.第16行那里是统计字符数。代码修改后统计结果不变。

19.这里改了之后，decoder数组会少一段，影响输出。

20.输出中有ABC，对应decoder[2]、decoder[18]、decoder[15],则输入的字符分别为字符C S P.

21.输出中有ABC，对应decoder[15]、decoder[17]、decoder[13],则输入的字符分别为字符P R N.

阅读程序2：

/*代码的作用是十进制的 n 转换成 k 进制的数字，输出的ans为进位的次数,len为结果的长度
*/
#include 
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];//每次个位 +1//进位处理到倒数第二高位for (int j = 0; j + 1 < len; ++j) { if (d[j] == k) {d[j] = 0;d[j + 1] += 1;++ans;}}//最高位单独处理 涉及到len的调整if (d[len - 1] == k) {d[len - 1] = 0;d[len] = 1;++len;++ans;}}cout << ans << endl;return 0;
}

22. 当k为1时，n为1，1进制的1，len 为2，所以错误。

23. 输入n为1且 k > 1 时，ans == n

24. n转化为 len 位的 k 进制数字值 最大值为 k ^len - 1 ，所以正确。

25. 当输入的 k 为 1 时，会直接进位，len为2，但是后面触发不了len++的条件，结果就是，len一直是2，每次 d[0]++ 都会进位，输出 ans == n。

26. 这里和27实际是一个问题，我们看一下进位的规律：

    比如产生一个十进制的1000，会进位几次呢？

    从百位到千位，只有1次，

    从十为到百位，有10次，

    从各位到十位，有100次，共计111次。

    这个规律推广一下，产生一个 kⁿ 需要进位次数为：1 + k¹ + k² + k³ + k⁴ … + k^n-1 = ( kⁿ - 1 ) / (k - 1)

27. 利用上面的规律，产生进位次数为

    ​ 9

    ​ 2 2 2 2 2 2

    ​ 1 1 1 1 1 1 1 1 1 1

    ​ + 1 1 1 1 1 1 1 1 1 1 1 1 1 1

    即可得结果

    阅读程序3：

    /*题目输入： 
    20
    9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 030
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 515
    15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
    15 14 13 12 11 10 9 8 7 6 5 4 3 2 1代码大意：函数名说明是一个深搜的算法，代码基本是按照深搜模板来的。看搜的是什么 s = a + x + abs(b - y) ans +=  s a,b为上一行两列数字的值，x,y为本行两列数字的值   这里输入的值都为正值，所以 输出的 ans 的最大值实际就是从第二行到最后一行s 累加 */
    #include 
    #include 
    using namespace std;int n;
    int d[50][2];
    int ans;
    int times=1;//保留前50位 
    void dfs(int n, int sum) {cout << sum << " " << n << " " << times << endl;  times += 1;if(times >= 50)return; 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);
    //        cout << "a:" << a << " x:" << x << " b:" << b << " y:" << y << " s:" << s << endl; //打开可以查看计算过程 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;
    }
    

    28.输入 n 为0，什么都没做，结束程序。

    29.全是0，运算过程中所有 s 都是 0，ans 也是0

    30.这里减法，所以 ans 可能小于 输入的 d[ i ][ 1 ],例如

    ​ 输入：

    ​ 2 0 0 2 3

    ​ 输出：

    ​ 1

    31.第二列为0，可以忽略，我们用 S_n 表示前 n 项的和，这里计算的就是 :

    ​ S₂ + S₃ + S₄ … + S₂₀ = 2 * 9 + 3 * 9 + 4 * 9 … 20 * 9 = 1881

    32. 这里不会出现 b < y 的情况，所以可以去掉绝对值符号，们用 S_n 表示前 n 项的和，

        这里计算的就是 :

        ​ S₁ - 5 + S₂ - 5 + S₃ - 5 … + S₂₉ - 5 = 0 * 5 + 1 * 5 + 2 * 5 … 28 * 5 = 2040

​ 33.这里输入的两列数字是一样的，我们再看 计算的内容：

					s = a + x + abs(b - y) ans +=  s 

这里不会出现 b < y 的情况，所以可以去掉绝对值符号，x, y抵消，s = a + b,

所以 ans = 2 * ( S₁ + S₂ + S₃ + S₄ … + S₁₄ ) = 2240

程序填空1：

34. 因子最小为2，所以 选 i = 2
35. 因子最大为 根号n 所以选 i * i
36. 由题目可知，一个因子可能被分解出好多次，所以选 C
37. 分解完成后，n 的值为 1 或者质数，判断剩余的是不是质数。
38. 不是 1 的 话需要单独输出

程序填空2：

39.按照区间起点进行排序，所以选B

40.基础的交换代码，选D

41.这里筛掉起点靠后同时终点靠前的区间，这样的区间不可能选用。选A

42.此时剩余的区间逐个选用。

43.选用最后一个区间，更新r。

如发现有问题，欢迎评论区指正。
如需要详细答疑或者信奥学习咨询，可微csm_904.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！