CFF CSP认证备考入门题目练习（复习c++语言适用）

由于之前学习的是C现在需要使用C来备考CSP所以先练习入门题目来熟悉C的格式考虑到本人编程能力较弱所以从简单的题目入手更加能加强信心帮助自己坚持下去后续会持续更新博客一方面可以巩固知识点一方面可以记录学习过程监督自己如果有不对的地方欢迎各位老师指正。补充一点我用的洛谷刷题下面记录了题序可以去洛谷搜到一、顺序、输入输出、分支 if第一题P1001 AB Problem入门【HelloWorld 级熟悉输入输出】题目描述输入两个整数 a,b输出它们的和。任何一个伟大的思想都有一个微不足道的开始。输入格式输入两个以空格分隔的整数 a,b。输出格式输出一个整数表示 ab。代码展示#include iostream using namespace std; int main(){ int a,b; cin a b; cout a b endl; return 0; }运行结果知识点复习#include iostreamC的专属头文件用来支持cin、coutc的输入输出.using namespace std;cin和cout是放在std标准命名空间的.cin a b;cin C的输入等价于C的scanf 叫做提取运算符想象成箭头从键盘流向变量.cout ab endl;叫做插入运算符箭头把内容送到屏幕上打印;endl意思换行 刷新缓冲区等价于\n.第二题P5710 数的性质入门判断奇偶、正负练习 if 分支题目描述一些整数可能拥有以下的性质性质 1是偶数性质 2大于 4 且不大于 12。小 A 喜欢这两个性质同时成立的整数Uim 喜欢这至少符合其中一种性质的整数小 B 喜欢刚好有符合其中一个性质的整数正妹喜欢不符合这两个性质的整数。现在给出一个整数 x请问他们是否喜欢这个整数输入格式输入一个整数 x(0≤x≤1000)输出格式输出这 4 个人是否喜欢这个数字如果喜欢则输出1否则输出0用空格分隔。输出顺序为小 A、Uim、小 B、正妹。代码展示#include iostream using namespace std; int main(){ /数的性质/ int a; cin a; bool p1 a%2 0,p2 a4 a 12; cout (p1 p2) (p1 || p2) (p1 ! p2) (!p1 !p2) endl; return 0; }运行结果知识点复习cout (p1 p2);括号不能随便省略优先级比、||高不加括号会出错。cout x y;输出格式多个数空格分隔第三题P5711 闰年判断入门经典多分支判断CSP非常爱考这种判断逻辑题目描述输入一个年份判断这一年是否是闰年如果是输出 1否则输出 0。1582 年以来闰年的定义普通闰年公历年份是 4 的倍数且不是 100 的倍数的为闰年如 2004 年、2020 年等就是闰年。世纪闰年公历年份是整百数的必须是 400 的倍数才是闰年如 1900 年不是闰年2000 年是闰年。输入格式输入一个正整数 n表示年份。输出格式输出一行。如果输入的年份是闰年则输出 1否则输出 0。代码展示#include iostream using namespace std; int main(){ int a; cin a; if( (a % 4 0 a % 100 ! 0) || a % 400 0) { cout 1 endl; } else{ cout 0 endl; } return 0; }代码运行分析此题根据看到题目的思路写出来和答案一致并且没有出现比较模糊的知识点所以只放出代码即可。二、循环 for / while考点循环遍历、累加、计数CSP-T1 90%都会用到循环第一题P1089 津津的储蓄计划入门按月循环累加判断经典模拟雏形题目描述津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 300 元钱津津会预算这个月的花销并且总能做到实际花销和预算的相同。为了让津津学习如何储蓄妈妈提出津津可以随时把整百的钱存在她那里到了年末她会加上 20% 还给津津。因此津津制定了一个储蓄计划每个月的月初在得到妈妈给的零花钱后如果她预计到这个月的月末手中还会有多于 100 元或恰好 100 元她就会把整百的钱存在妈妈那里剩余的钱留在自己手中。例如 11月初津津手中还有 83 元妈妈给了津津 300 元。津津预计11月的花销是 180 元那么她就会在妈妈那里存 200 元自己留下 183 元。到了 11 月月末津津手中会剩下 3 元钱。津津发现这个储蓄计划的主要风险是存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初津津手中的钱加上这个月妈妈给的钱不够这个月的原定预算。如果出现这种情况津津将不得不在这个月省吃俭用压缩预算。现在请你根据 2004 年 1 月到 12 月每个月津津的预算判断会不会出现这种情况。如果不会计算到 2004 年年末妈妈将津津平常存的钱加上 20% 还给津津之后津津手中会有多少钱。输入格式12 行数据每行包含一个小于 350 的非负整数分别表示 1 月到 12 月津津的预算。输出格式一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况输出 −XX 表示出现这种情况的第一个月否则输出到 2004 年年末津津手中会有多少钱。代码展示#include iostream using namespace std; int main(){ /* 津津的储蓄计划 */ int money 0; int tatal 0; int rest 0; int budget 0; int i ; for(i 1; i lt; 12; i){ cin gt;gt; budget; money rest 300; rest money - budget; if((money - budget) gt; 0) /*第一次运行出现错误因为这里没有加上等于零的情况 */ { while(rest gt; 100) { tatal 100; rest - 100; } } else { cout lt;lt; -i; return 0; } } cout lt;lt; (tatal*1.2 rest) lt;lt;endl; /*第二次编译错误因为这里没有考虑津津到月底还有剩余的钱再加上妈妈给的钱 */ return 0; }运行结果分析题目比较长先在草稿纸上模拟一下整个流程找出循环的点再列出需要用到的变量一一命名写出框架后输入数据编译找出遗漏的细节。第二题P1035 级数求和入门while循环控制循环终止条件题目描述已知Sn​11/2​1/3​…1/n。显然对于任意一个整数 k当 n 足够大的时候Sn​k。现给出一个整数 k要求计算出一个最小的 n使得 Sn​k。输入格式一个正整数 k。输出格式一个正整数 n。代码展示#include iostream using namespace std; int main(){ /* 级数求和 */ int n 0; int k 0; double sn 0; cin gt;gt; k; while(sn lt; k){ n ; sn sn 1.0/n; } cout lt;lt; n; return 0; }运行结果分析错误写法int sn 0; int n 0; sn 1/n; // 1/n 整数除法全部是0此处忽略了n为整型1/n会忽略小数部分始终为0所以在调试的时候sn始终为1而n在不停增加因此在定义和初始化变量以及做除法的时候需要注意变量的范围。第三题P1217 [USACO1.5]回文质数普及-循环枚举判断同时练循环判断题目描述因为 151 既是一个质数又是一个回文数从左到右和从右到左是看一样的所以 151 是回文质数。写一个程序来找出范围 [a,b](5≤ab≤100,000,000)一亿间的所有回文质数。输入格式第一行输入两个正整数 a 和 b。输出格式输出一个回文质数的列表一行一个。复习这道题需要我们回顾一下质数和回文数的判断方法。我们先来看质数也叫做素数判断质数的方法可以在csdn上找到很多我们今天只讲思维量最低的两种比较好上手第一种是根据定义暴力遍历时间复杂度为O(n)但是做题来说一般没问题。质数的定义大于一的自然数除了一和本身没有其他因数就是质数。所以我们只需要设立循环把这个数依次除比它小的数看有没有其他因数即可。第二种方法和第一种方法类似但是根据以下规则当一个数不是质数时必定存在两个约数一个大于等于 sqrt (n)另一个小于 sqrt (n)。我们只需要遍历到sqrt (n)这个数即可时间复杂度为Osqrt (n)降低了不少。还有更多巧妙的方法我们目前做入门题目就先不做了解。然后就是回文数当然后面学到数组还会判断回文字符串今天还是只用简单方法判断回文数吧首先从定义入手从左到右和从右到左是看一样的数其次我们知道一个数如151除以十的余数是它的最后一个数1除以十的商是前两个数15由此我们可以单独得到每个位数上的数字把个位数字×100十位数字×10百位数字×1我们就得到倒过来的新数字再比较新数和原数是否相等即可。接下来开始写代码吧。代码展示#include iostream using namespace std; int main(){ /* 回文质数 / int a,b,i; bool flag true; cin a b; for( a; a b; a){ / 先用循环判断是不是质数 / for( i 2; i a; i){ flag true; if( a % i 0){ / 只要不是质数就可以直接下一个数不用再判断是不是回文数所以命名一个标记可以直接跳过回文数的判断 / flag false; break; //不是质数跳出循环开始遍历下一个数 } / 继续判断下一个数直至遍历完跳出循环 / } / 开始判断回文数 / if(flag) //是质数才进行判断 { int temp; int newed 0; temp a; while(temp 0){ newed newed10 temp % 10; temp / 10; } if(newed a){ cout a endl; continue; } } } return 0; }先判断质数再判断回文数且都用的暴力遍历结果超时了看了题解发现回文数比指数少且可以先直接排除掉所有偶数这样就可以省掉很多时间了。#include iostream #include cmath using namespace std; int main(){ /* 回文质数 / int a,b,i; bool flag true; cin a b; for( a; a b; a){ flag true; / 先排除偶数 / if(a % 2 0) { continue; } / 判断回文数 */ int temp; int newed 0; temp a; while(temp gt; 0){ newed newed*10 temp % 10; temp / 10; } if(newed ! a){ continue; } /* 判断是不是质数 */ for( i 2; i lt; sqrt(a); i){ if( a % i 0){ flag false; //不是质数 break; } } if(flag){ cout lt;lt; alt;lt; endl; } } return 0; }直接遍历还是有部分超时所以用了判断质数的第二种方法才通过了测评运行结果复盘遍历的题一定要注意超时的问题要用到数学库函数时要加上对应头文件。#include cmath三、数组一维数组考点数组读入、遍历、找最大/最小、统计、求和第一题P1047 校门外的树入门一维数组标记、区间修改经典模拟题目描述某校大门外长度为 l 的马路上有一排树每两棵相邻的树之间的间隔都是 1 米。我们可以把马路看成一个数轴马路的一端在数轴 0 的位置另一端在 l 的位置数轴上的每个整数点即 0,1,2,…,l都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数区域之间可能有重合的部分。现在要把这些区域中的树包括区域端点处的两棵树移走。你的任务是计算将这些树都移走后马路上还有多少棵树。输入格式第一行有两个整数分别表示马路的长度 l 和区域的数目 m。接下来 m 行每行两个整数 u,v表示一个区域的起始点和终止点的坐标。输出格式输出一行一个整数表示将这些树都移走后马路上剩余的树木数量。复习数组的内容有点忘了复习一下再来做题。定义方式数据类型 数组名 [数组长度]数据类型 数组名 [数组长度] {值1 值2...}数据类型 数组名 [] {值1 值2...}数组名的用途sizeofarr可以统计整个数组在内存中的长度sizeof(arr[0])某个数在内存中的长度sizeofarr/ sizeof(arr[0]) 数组个数cout arr endl; 获取数组在内存中的首地址一些简单的知识点这道题可能用不上但是无所谓开始做题吧。思路分析这道题的思路可以拆成三步来想。第一步确定数组大小。马路长度为 l数轴上 0 到 l 每个整数点都有一棵树所以一共有 l1 棵树。因此数组长度要开成 l1下标 0 到 l 正好一一对应每一棵树的位置。第二步想清楚“移走”怎么表示。静态数组没办法真的把元素删掉而且题目给的区间之间还可能有重合部分如果直接对数组元素做删除或置空重合区间就会重复处理很容易出错。所以换一种思路不记录“树还在不在”而是记录“这棵树有没有被标记过”。用 0 表示还没被移走用 1 表示已经被移走。第三步标记与统计。先把整个数组初始化为 0表示所有树都还在。然后每读入一组区间 u、v就把下标 u 到 v 之间的元素全部置为 1表示这些位置上的树被移走了。由于是直接赋值 1即使区间重合重复标记也不会影响结果。最后再遍历一遍数组统计值为 0 的元素个数就是马路上剩余的树木数量。这样写的好处是逻辑非常直观标记阶段只负责“打点”统计阶段只负责“数数”两个阶段互不干扰也不需要考虑区间重合带来的复杂情况。代码展示#include iostream using namespace std; int main(){ /* 校门外的树 */ int l,m,u,v; int num 0; cin l m; int v1[l1]; for( int i 0; i l 1; i ){ v1[i] 0; } for( int i 0; i lt; m; i ){ cin gt;gt; u gt;gt; v; for( u; u lt; v; u){ v1[u] 1; } } for( int i 0; i lt; l 1; i ){ if( v1[i] 0 ) { num ; } } cout lt;lt; num; return 0; }看了题解后意识到数组里面只有1/0变量类型其实可以定义为bool型这样bool的初始值就为false就可以少一个遍历定义数组的过程。运行结果第二题P1059 明明的随机数入门去重排序数组基础综合题题目描述明明想在学校中请一些同学一起做一项问卷调查为了实验的客观性他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N≤100)对于其中重复的数字只保留一个把其余相同的数去掉不同的数对应着不同的学生的学号。然后再把这些数从小到大排序按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。输入格式输入有两行第 1 行为 1 个正整数表示所生成的随机数的个数 N。第 2 行有 N 个用空格隔开的正整数为所产生的随机数。输出格式输出也是两行第 1 行为 1 个正整数 M表示不相同的随机数的个数。第 2 行为 M 个用空格隔开的正整数为从小到大排好序的不相同的随机数。复习这道题涉及到“去重”和“排序”两个点去重用遍历比较就可以解决排序却是个比较经典解法也很丰富的算法题我们先来复习几种简单常见的排序算法吧。关于排序是参考以下作者的做法和思路原文链接https://blog.csdn.net/2301_80215560/article/details/136604635一、冒泡排序通过对待排序序列从前向后从下标较小的元素开始,依次对相邻两个元素的值进行两两比较若发现前一个数大于后一个数则交换使值较大的元素逐渐从前移向后部就如果水底下的气泡一样逐渐向上冒。#include iostream using namespace std; /* 冒泡排序 */ int swap( int *a, int *b) { int temp *a; *a *b; *b temp; }//因为冒泡排序是比较相邻的两个数并按照排序规则交换顺序所以会使用交换这个动作很多次 int bubble(int *arr, int n){ for( int i 0; i lt; n; i){ int change 0; for( int j 0; j lt; n-i-1; j){ //由于每一轮最大的数已经确定所以每次可以少比较一个 if( arr[j] gt; arr[j1] ){ swap( arr[j], arr[j1]); change ;//如果在一整轮循环中没有交换则说明已经排好了所以有交换我们就标记一下 } } if(change 0) { break; //一轮循环没有交换直接跳出循环减少时间 } } } int main(){ int arr[5] {3,4,7,2,0}; bubble( arr, 5); for( int i 0; i 5; i){ cout arr[i] ; } }二、选择排序内层循环一趟找出最小值的下标与第一个数交换。重复找小交换的两个操作。#include iostream #include utility using namespace std; /* 选择排序 */ int SelectSort( int *arr, int n) { for( int i 0; i n - 1; i){ int min i;//一开始把这一步定义min写在了下面一层循环里面 怎么运行都不对 因为写在下面那个for循环就是局部变量 出了这个循环 下面就不能再引用 for( int j i; j n; j){ if(arr[j] arr[min]){ min j; } } swap(arr[i], arr[min]); //swap函数在头文件utility里面 可以直接调用 } } int main(){ int arr[5] {3,4,7,2,0}; SelectSort( arr, 5); for( int i 0; i 5; i){ cout arr[i] ; } }三、插入排序在待排序的元素中假设前n-1个元素已有序现将第n个元素插入到前面已经排好的序列中使得前n个元素有序。按照此法对所有元素进行插入直到整个序列有序。但我们并不能确定待排元素中究竟哪一部分是有序的所以我们一开始只能认为第一个元素是有序的依次将其后面的元素插入到这个有序序列中来直到整个序列有序为止。#include iostream #include utility using namespace std; /* 插入排序 */ int InsertSort( int *arr, int n) { for(int i 1; i n; i){ //从下标为1开始 if(arr[i] arr[i-1]) {//先判断 如果要插入的这个数比前面有序数组的最后一个大就直接放到最后一个就好了 即不用变化 //现在我们要开始挨个和前面的数比较 找到合适的位置 //当前面一个数比当前数大时 把前面一个数往后移一个 //此时当前这个arr[i]的位置变成了更大的这个数 那么我们就要先定义一个临时变量把我们拿出来要插入的数存起来 int temp; temp arr[i]; int j; //把要插入的数挨个往前比较 直到到了第一个数或者找到了比它小的 即下标等于0了或者arr[j]arr[i] for( j i-1; j 0 temp arr[j]; j --){ //还没有检索到合适的位置就把当前的arr[j]往后移一个 arr[j 1] arr[j]; } //直到检索到的这个值arr[j]比temp小 把temp赋值给j后面这个位置 //或者已经把下标为0的数往后移另一位 所以j--后为-1 不会再进入循环 把要插入的值放入j1也就是0下标 arr[j 1] temp; } } } int main(){ int arr[5] {3,4,7,2,0}; InsertSort( arr, 5); for( int i 0; i 5; i){ cout arr[i] ; } }排序方法太多了今天就学到这里好了光这三种方法就弄了几个小时还是继续刷题复习基础吧。代码展示#include iostream #include vector using namespace std; void InsertSort( int *arr, int n) { for(int i 1; i n; i){ //从下标为1开始 if(arr[i] arr[i-1]) {//先判断 如果要插入的这个数比前面有序数组的最后一个大就直接放到最后一个就好了 即不用变化 //现在我们要开始挨个和前面的数比较 找到合适的位置 //当前面一个数比当前数大时 把前面一个数往后移一个 //此时当前这个arr[i]的位置变成了更大的这个数 那么我们就要先定义一个临时变量把我们拿出来要插入的数存起来 int temp arr[i]; int j; //把要插入的数挨个往前比较 直到到了第一个数或者找到了比它小的 即下标等于0了或者arr[j]arr[i] for( j i-1; j 0 temp arr[j]; j --){ //还没有检索到合适的位置就把当前的arr[j]往后移一个 arr[j 1] arr[j]; } //直到检索到的这个值arr[j]比temp小 把temp赋值给j后面这个位置 //或者已经把下标为0的数往后移另一位 所以j--后为-1 不会再进入循环 把要插入的值放入j1也就是0下标 arr[j 1] temp; } } } int main(){ //先排序再去重 这里排序我们直接调用我们前面写过的函数 int N; cin N; vectorint arr(N); for( int i 0; i N; i) { cin arr[i]; } InsertSort( arr.data(), N); //去重 把不重复的数记录下来 int k 0;//用k来记录不重复数 for( int i 0; i N; i) { //第一个数直接记录下来 再比较 和后一个数不同的也记录下来 if(k 0 || arr[k-1] ! arr[i]) { arr[k] arr[i]; } } cout k endl; for( int i 0; i k; i){ cout arr[i] ; } return 0; }运行结果总结这里把做错的地方列举一下问题 1cout arr[i];— 编译错误Ccout arr[i];是空字符字面量C 不允许空字符字符必须包含至少一个字符。编译器会直接报错。cout arr[i] ; // 用空格字符 // 或者 cout arr[i] ; // 用字符串 没有 return — 未定义行为int InsertSort( int *arr, int n) { // 返回类型是 int for(int i 1; ... ) { ... } // ← 没有 return 语句 }修复函数不需要返回值改为voidvoid InsertSort( int *arr, int n) {问题 3使用了 VLA变长数组— 标准 C 不支持int arr[N]; // N 是运行时变量这是 C99 的 VLA 特性标准 CC11/14/17/20不支持。GCC 作为扩展可以编译但 Clang/MSVC 可能不行。修复#include vector // ... vectorint arr(N);第三题P1781 宇宙总统普及-读入一堆数据找最大值下标结构体雏形题目描述地球历公元 6036 年全宇宙准备竞选一个最贤能的人当总统共有 n 个非凡拔尖的人竞选总统现在票数已经统计完毕请你算出谁能够当上总统。输入格式第一行为一个整数 n代表竞选总统的人数。接下来有 n 行分别为第一个候选人到第 n 个候选人的票数。输出格式共两行第一行是一个整数 m为当上总统的人的号数。第二行是当上总统的人的票数。代码展示#include iostream using namespace std; int main(int argc, char** argv) { /*宇宙总统*/ int n; //题目中说明票数可能会很大 可能会到 100 位数字 所以不能用int(int只能存大约10位数 string s; string max ;//设一个变量来存储最大值 int maxNum 1;//用来存最大值的下标 cin n; for(int i 0; i n; i){ cin s; //这里要用字符串比较大小的方法 if(s.size() max.size() || (s.size() max.size() s max)) { max s; maxNum i 1; } } cout maxNum endl; cout max endl; return 0; }运行结果总结①问题int存不下 100 位的数类型最大值大约位数int214748364710 位long long约 9.2×10¹⁸19 位题目票数可达100 位string存的不是一个数而是一串字符。它根本没有数值范围这个概念只要内存够想存多长存多长。②string的用法s.size()得到字符串的长度③用string比较大小字符串从左往右比只看最高位。9的最高位是 9100的最高位是 1于是9 100——完全忽略了100后面还有两位。string的直接比大小只适合在位数相同时当数值比较用位数不同时它会误判9 100。所以必须先用size()比较位数得出谁更大长度相同才落到字典序比较上。好了这一篇就到这里了基础入门题目还有五节就放下一篇了这一篇已经做了三天先完结一下。