2020年csp j入门级复赛真题.docx

CSP信息学奥赛入门级复赛真题解析将对2020年CSP-J入门级复赛真题进行详细解析，涵盖题目描述、标签、部分内容等方面。对于热衷于信息学竞赛的学生，这些真题解析不仅可以帮助他们理解题目的设计思路，还能提高他们的编程能力。题目1：优秀的拆分（power）

题目描述：一般来说，一个正整数可以拆分成若干个正整数的和。1=1，10=1+2+3+4等。对于正整数n的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，n被分解为了若干个不相同的2的正整数次幂。

输入格式：输入文件名为power.in。输入文件只有一行，一个正整数n，代表需要判断的数。

输出格式：输出文件名为power.out。如果这个数的所有拆分中，存在优秀的拆分，那么你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。

样例1输入：6

样例1输出：4 2

样例1解释：6=4+2=2^2+2^1是一个优秀的拆分。

数据范围与提示：对于20%的数据，n<=10。对于另外20%的数据，保证n为奇数。对于另外20%的数据，保证n为2的正整数次幂。对于80%的数据，n<=1024。对于100%的数据，1<=n<=1x10^7。

题目解析：一个数本来就可以拆分成2的正整数次幂，因为利用它的二进制即可得到。例如：6的二进制是110，分别代表2^2，2^1，所以6可以看成2^2+2^1=4+2。对n进行二进制分解，然后倒序输出即可。

参考程序：

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int n;

int main(){

    cin >> n;

    if (n % 2 == 1) { 

        cout << -1; 

        return 0; 

    }

    int a[30], cnt = 0;

    int base = 1;

    while (n) {

        if (n % 2 == 1) { 

            a[++cnt] = base; 

        }

        n /= 2;

        base *= 2;

    }

    for (int i = cnt; i >= 1; i --) { 

        cout << a[i] << " "; 

    }

    return 0;

}

cmath>cstdio>iostream>

零一点评：本题难度显著高于2019，2018，2017年的第一题。没有联想到二进制转化的同学可能会被卡住。一旦联想到，就是一个入门级题目。

骗分方法：

• 第一个20%：对每个n，打表

• 第二个20%：根据题意，不存在，直接输出-1

• 第三个20%：它的拆分就是它本身，直接输出n本身。

若您对信息学竞赛有更深入的兴趣，建议参考《ACM编程算法艺术与信息学竞赛题目完全解析》等相关书籍，进一步提高您的编程水平。

题目2：直播获奖（live）

题目描述：NO12130即将举行。为了增加观赏性，CCF决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为w%，即当前排名前w%的选手的最低成绩就是即时的分数线。

输入格式：输入文件名为live.in。第1行两个正整数n，w，分别代表选手总数与获奖率。第2行有n个非负整数，依次代表逐一评出的选手成绩。

输出格式：输出文件名为live.out。只有一行，包含n个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。

样例1输入：10 60 20

样例1输出：20 20

数据范围与提示：无特殊限制。

这两个题目涵盖了基本的编程概念和算法思想，适合入门级选手练习和提高编程能力。如果您希望更全面地了解信息学竞赛的题目解析与解法，您可以参考《信息学题目代码答案.rar》以及《算法艺术与信息学竞赛题目完全解析.pdf》，这些资料将为您提供更详尽的学习指导。