P多题型

历年真题

# CPS赛事介绍
2019 年由 CCF 统一组织的评价计算机非专业人土算法和编程能力的活动。在同一时间、不同地点以各省市为单位由 CCF 授权的省认证组织单位和总负责人组织。全国统一大纲、统一认证题目，任何人均可报名参加。CSP-J/S 成绩优异者,可参加 NOI 省级选拔，省级选拔成绩优异者可参加 NOI。
官网：http://rg.noi.cn
信息学奥赛（CSP）是中国中小学生五大学科竞赛之一。和数学，物理，化学，生物竞赛，并称为五大学科竞赛。是我国信息学，计算机学科竞赛的最具含金量的赛事。 获得提高组奖项的学员，有机会得到各大名校的降分签约，以低于录取线几十分的成绩进入心仪的大学。

# 认证形式
CSP J/S 分两个级别进行,分别为 CSP-J（入门级，Junior）和 CSP-S（提高级，Senior) , 两个级别难度不同,均涉及算法和编程。第一轮分两组 CSP-S1、CSP-J1 进行，第一轮成绩优异者进入第二轮 CSPS2、CSP-J2。
认证方式： 两轮两组认证试题均采用电子版本下发给 CCF 授权的省认证点，各省认证点视情况印刷纸质试题。
- 第一轮认证以笔试为主，CCF 将选取少数省份以机试方式认证，考察通用和实用的计算机科学知识
- 第二轮认证为程序设计，机试；CSP-S2 组有两次认证，参加认证者成绩为两次认证成绩之和；CSP-J2 组一次认证，共四个题目，口认证者可同时参加CSP-S2/J2 两组测试

# 报名相关
### 考试时间： 
第一轮（CSP-J1/S1）：2024 年 9 月 21 日
 第二轮（CSP-J2/S2）：2024 年 10 月 26 日
### 考试费用： 
第一轮 CSP-S/J 组：50 元/人(该费用不包括食宿及交通费)。
第二轮 CSP-S 组：480 元/人(该费用不包括食宿及交通费)。
 第二轮 CSP-J 组：260 元/人(该费用不包括食宿及交通费)。

# 试卷详情
第一轮试题（CSP-J1 & CSP-S1）组成：
- 试题由3部分组成，满分100分
- 选择题（共15题，每题2分，共计30分）提高组的前10道题为单选题，后5道题为不定项选择题（只有全部选对才得分，否则不得分）；普及组的前15道题都是单选题。
- 程序理解题（共3题，共计40分）题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序进行答题，分为选择题和判断题。
- 程序完善题（共3题，共计30分）题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，

要求考生根据程序的功能说明和代码的上下文，选择对应答案 。三题皆为选择题。
  
第二轮试题组成：

- CSP-J2：时间为3小时，共4道题，每题100分，共计400分。
- CSP-S2：包括一试和二试，分两天进行。每次测试时间为3小时，有3道题，每题100分。选手的总分为两次测试的分数的总和，最高600分。

每一试题包括：题目、问题描述、输入输出要求、样例数据（部分题目有样例的说明）。测试时，测试程序为每道题提供了10-20组测试数据，考生程序每答对一组得5-10分，累计分即为该道题的得分。


# 考试注意事项
【对于初学者】
  1. 文件输入输出
    这部分是参数选手们出错最多的地方！因为和平时练习不一样。CSP复赛要求用文件输入输出，一定要确保提交文件中freopen()文件读写没有被注释掉，再具体点，就是
    一定要记住两句话：freopen(“xxxx.in”,“r”,stdin) ;    freopen(“xxxx.out”,“w”,stdout) ;    
    注：xxxx是每道题的英文名字。
  2. 注意“四名”
    文件夹名、程序文件名、输入文件名、输出文件名。
    每道题这部分的英文名称都是一样的，都是小写，一定要多检查几遍！
  3. 输出格式和大小写问题
    比如，注意题目要求每个输出结果在同一行，还是在不同行。
    或者输出yes no right impossible等英文提示时，是否要求首字母大写，大小写在Linux下面是不一样的。
  4. 注意存盘，不要关机
    为了防止突发事件，至少20分钟存盘一次 。千万不要关机，否则程序会丢失。
  5. 头文件
    最常用的头文件，一般写代码时先都把这几个写上去：<iostream>、<cstdio>、<cmath>、<cstring>、<cstdlib>
    较常用的头文件：<algorithm>、<vector>、<queue>、<string>
    头文件太多时，容易忘写using namespace std;但是用了using namespace std;之后容易产生的问题是：自己的变量名和std命名空间的变量名冲突，而且在Windows下
    编译器不报错，在Linux下报错。所以自己的变量名不要使用hash、x0、x1、y0、y1，time、next、pipe等。如果需要这几个单词，可以用Time、Next等第一个字母大写
    或者加上一些字母，如mytime、mynext等，或者定义成局部变量。当然，time、next、pipe等作为结构体的成员名是没问题的。
  6. 变量初始化
    变量在使用之前忘了初始化，里面的值是随机的，结果就会出问题，所以使用的时候不要忘记初始化，可以定义成全局变量，系统会自动初始化。
  7. 数据类型
    注意数据类型，输入输出的时候占位符和数据类型要一致，不一致在有时候可能结果也没有错误，但是评测的时候可能就有问题，比如long long的数据类型不能用
    “%d”，而应该用“%lld”。
  8. 不要使用gets函数
    由于gets函数会造成安全隐患，在C++中已经被弃用，所以注意不要使用gets函数。可以使用：fgets\getchar\scanf\std::cin或其他读入方式。
  9. 数组
    C++里数组有时候可能会出现莫名其妙的问题，所以一定要记得把数组开大点，并且赋初值。最好是开成全局变量，因为在main函数里定义的是局部变量，给你的空间会
    比较小，二维数组很容易就爆了。
【对水平比较高的选手们的建议】
  10. STL
    STL主要是依靠各种容器和函数来实现各种功能，但是STL有些不是很常用，比如队列和栈，手写很方便，而且快一些，主要就用堆（priority_queue）、字符串
  （string）和动态数组（vector）。
  11. 指针
    指针一般竞赛选手用得比较少，因为太容易出错了，一般选手会开个数组用下标i做指针，比较方便。
  12. 时间空间资源和精度
    1000毫秒内最大循环次数不要超过10^8（10^8有点悬，10^7绝对不超时）。空间限制在128MB时，数组元素类型为int时，元素个数最多千万级别（约3*10^7），要定
    义在到main函数外面的全局变量区（二维数组的两个维度大小要相乘）。
  13. 数据范围
    有的题目，多个数相加，每个数的最大值就到了1e9，那么存放和的变量就必须是long long 。有的题目，边权的最大值都到了1e9，并且更新最短路径时两个边权相加，
    结果就是2e9，那么我们在为数组元素赋值为无穷大时，应该设多少呢？我们的无穷大可以是1e9+1，或者0x3f3f3f3f=十进制1061109567, 0x7f7f7f7f=十进制
    2139062143，int 的范围是-2147483648 ~ 2147483647。所以程序中的无穷大可以定义为1e9+1或0x3f3f3f3f 。
  14. 建立图的邻接矩阵和邻接表时，注意单向边和双向边，重边，自环等情况。