2020普及组初赛题解

作者： 作者的头像   江见月 ,  2021-01-06 16:59:20 ,  所有人可见 ,  阅读 696

0


2020普及组初赛

选择题：

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

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

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

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

  2. c++ 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~4~^4^ * 2

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

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

总方案数就是：C ~7~^3^ +C ~7~^2^ * 2 +C ~7~^1^ = 35 + 42 + 7 = 84

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

总方案数就是：（ C ~5~^2^ * C ~6~^1^ +* C ~4~^1^ ）/ 2 = 120

阅读程序1：

/*
这个程序通过encoder,decoder两次转换产生一个乱序字符串，利用乱序字符串加密

encoder ="CSPABDEFGHIKLMNOQRTUVWXYZ"
decoder ="DEAFGHIKLMNOPQCRSBTUVWXYZ"

*/
#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)//每个字符放到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 <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];//每次个位 +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;
}

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

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

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

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

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

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

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

    从十为到百位，有10次，

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

    这个规律推广一下，产生一个 k^n^ 需要进位次数为：1 + k^1^ + k^2^ + k^3^ + k^4^ ...... + k^n-1^ = ( k^n^ - 1 ) / (k - 1)

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

    ​ 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：

    ```c++
    /*

    题目输入：
    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 0

    30
    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 5

    15
    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 [HTML_REMOVED]

    include [HTML_REMOVED]

    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~2~ + S~3~ + S~4~ ...... + S~20~ = 2 * 9 + 3 * 9 + 4 * 9 ..... 20 * 9 = 1881

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

      这里计算的就是 :

      ​ S~1~ - 5 + S~2~ - 5 + S~3~ - 5 ...... + S~29~ - 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~1~ + S~2~ + S~3~ + S~4~ ...... + S~14~ ) = 2240

程序填空1：

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

程序填空2：

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

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

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

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

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

0 评论