【比赛题解】2021蓝桥杯青少组省赛（中级组）题解_c++种蔬菜问题
赞
踩
目录
前言
大家好，这一篇题解主要是关于2021那届蓝桥杯的题解。
一、字符串
题目描述
给定一个字符串，然后将字符串倒序输出。
输入描述：一个字符串S（2<S长度<100）
输出描述：将字符串S倒序输出
样例输入
abc
样例输出
cba
题目解析
这道题是一个开胃菜，很简单，分分秒解答，for循环即可完成。
给两个方法，一种是string类型，一种是传统的char[]类型。
AC代码1
- #include<string>//使用字符串头文件
- #include<iostream>//使用输入输出流头文件
- using namespace std;//使用标准名字空间
- string s;//定义字符串类型变量s
- int main(){//主函数开始
- getline(cin,s);//整行输入字符串s
- for(int i=s.size()-1;i>=0;i--){//for循环，计数器i从s的长度-1自减到0，共循环s的长度次
- cout<<s[i];//输出s的i号元素
- }
- return 0;//主函数结束，返回0
- }
AC代码2
- #include<cstring>//调用C语言字符串头文件
- #include<iostream>//调用输入输出流头文件
- using namespace std;//使用标准名字空间
- char s[100];//定义字符数组类型变量s
- int main(){//主函数开始
- cin.getline(s,100);//整行输入含有100个字符的字符串s
- for(int i=strlen(s)-1;i>=0;i--){//for循环，计数器i从s的长度-1，自减到0，共循环s的长度次
- cout<<s[i];//输出s的i号元素
- }
- return 0;//主函数结束，返回0
- }
二、剪绳子
题目描述
一条绳子从中间剪一刀可以剪成两端绳子；如果对折1次，中间剪一刀可以剪出3段绳子；如果连续对折2次，中间剪一刀可以剪出5段绳子；那么，连续对折n次，中间剪一刀可以剪出多少段绳子？
输入描述：输入一个正整数n（2<n<20）作为绳子对折的次数
输出描述：输出一个正整数，表示对折n次后绳子中间剪一刀可以剪出的绳子的段数
样例输入
3
样例输出
9
题目解析
这是一道入门级别的题，找到公式：ans=2^n+1。
但越简单的题越是暗藏玄机，用了for循环，一算，提交：“诶？怎么TE了？”那是因为这一题推荐使用cmath中的pow函数，代码为pow(2,n)+1。
好了，相信大家都迫不及待了吧，好，上代码，这里我喜欢用函数来封装一个运算的过程，因为这样程序更结构化。
AC代码
- #include<iostream>//调用输入输出流头文件
- #include<cmath>//调用数学函数头文件
- using namespace std;//使用标准名字空间
- long long n;//定义长整数类型变量n
- int main(){//主函数开始
- long long cut(long long num);//声明函数cut，参数num为长整数类型，返回值为长整数类型
- cin>>n;//输入n的值
- cout<<cut(n);//输出cnt(n)
- return 0;//主函数结束，返回0
- }
- long long cut(long long num){//定义函数cut， 参数num为长整数类型，返回值为长整数类型
- return pow(2,num)+1;//返回2的num次方加1
- }
三、求和
题目描述
合数指自然数中除了能被1和它本身整除外，还能被其他数（0除外）整除的数。最小的合数是4.如：合数4既可以被1和4整除，还能被2整除。
给定一个正整数N，计算出4到N之间所有合数的和。
例如：N等于7，其中4到6之间的合数有4、6，所有合数和等于4+6=10
输入描述：输入一个正整数N（4<N<101）
输出描述：输出一个整数，表示4到N之间（包含4和N）所有合数的和
样例输入
7
样例输出
10
题目解析
这道题不算太难，只需要构建一个判断合数的函数，反复调用即可。其中，为了减小时间复杂度，函数里for的条件需写成i*i<num。
在for循环中，如果找到了符合条件的因数，直接返回真，如果一轮for下来还没有找到，就返回假。
AC代码
- #include<iostream>//定义输入输出流头文件
- using namespace std;//使用标准名字空间
- int ans,N;//定义整数类型变量ans,N
- int main(){//主函数开始
- cin>>N;//输入N的值
- bool cpsit(int num);//声明函数cpsit，参数num为整数类型，返回值为布尔类型
- for(int i=4;i<=N;i++){//for循环，计数器i从4自增到N,共循环n-3次
- ans+=cpsit(i)*i;//ans自增cpsit(i)乘i
- }cout<<ans;//输出ans的值
- return 0;//主函数结束，返回0
- }
- bool cpsit(int num){//定义函数cpsit，参数num为整数类型，返回值为布尔类型
- for(int i=2;i*i<=num;i++){//for循环，计数器i从2自增到sqrt(num),共循环sqrt(num)-1
- if(num%i==0){//如果num能被i整除
- return true;//返回真
- }
- }return false;//返回假
- }
四、求和比较
题目描述
小蓝在学习 C++数组时，突发奇想想知道如果将一个连续的正整数数组拆分成两个
子数组，然后对拆分后的两个子数组求和并作差，且差值正好等于一个固定的正整
数，像这样同一个连续的正整数数组拆分方案有多少种。
我们一起帮助小蓝涉及以下规则：第一给出两个正整数 N 和 M；
第二从 1 到 N 组成一个连续正整数数组 A（A={1,2,3,4……N}）
第三将数组 A 拆分成两个子数组 A1、 A2（拆分的两个子数组中不能出现相同的数，
子数组中的数字可以连续也可以不连续，拆分出的两组子数组的元素个数可以不同，
但总数量等于 A 数组的元素个数）
第四对 A1、 A2 两个子数组分别求和；
第五对两个子数组的和作差（大减小）如果差值正好等于 M，则该拆分方案成立。
如： N=5,M=1，连续正整数数组 A={1,2,3,4,5}， 符合条件的拆分方案有三种：
A1={1,2,4},A2={3,5} A1={1,3,4} A2={2,5} A1={3,4},A2={1,2,5}
输入描述：
分别输入两个正整数 N（3<N<30） 和 M（0≤ M≤500） ， 由一个空格隔开
输出描述： 输出一个正整数，表示 1 到 N（包含 1 和 N） 连续的正整数数组中有
多少种方案， 使得拆分的两个子数组部分和的差值等于
样例输入
5 1
样例输出
3
题目解析
这一道题用到了深度搜索（dfs）或者动态规划，这两种方法在此处不做讲解，后期会设置相应专栏。
AC代码1（深度搜索）
- #include<iostream>//调用输入输出流头文件
- using namespace std;//使用标准名字空间
- int N,M,cnt;//定义整数类型变量N,M,cnt
- void dfs(int n,int m){ //凑 n, 每个数至少为 m
- if(n==0) cnt++;//如果n等于0，cnt自增1
- if(m>n) return;//如果m大于n，跳出函数
- for(int i=m;i<=N;i++)//for循环，计数器i从m自增到N，共循环
- dfs(n-i,i+1);//递归
- }
- int main(){//主函数开始
- cin>>N>>M;//输入N,M的值
- M=(N*(N+1)/2-M)/2;//下面只需凑出和为 M的子组
- dfs(M,1);//执行函数
- cout<<cnt;//输出cnt的值
- return 0;//主函数结束，返回0
- }
AC代码2（动态规划）
- #include<iostream>//调用输入输出流头文件
- using namespace std;//使用标准名字空间
- int N,M,cnt[2022]={1}; //cnt[i]代表和为 i的子组数量
- int main(){//主函数开始
- cin>>N>>M;//输入N,M的值
- M=(N*(N+1)/2-M)/2; //下面只需凑出和为 M的子组
- for(int i=1;i<=N;i++)//for循环，计数器i从1自增到N,共循环N次
- for(int j=M;j>=i;j--) //倒推,防止同一个数被用两次
- cnt[j]+=cnt[j-i];//cnt的j号元素自增cnt的j-i号元素
- cout<<cnt[M];//输出cnt的M号元素
- return 0;//主函数结束，返回0
- }
五、最大价值
题目描述
一名种菜的农民伯伯，需要在给定的时间内完成种菜，现有 m 种不同的蔬菜提供给
农民伯伯选择，且每种蔬菜种植所花费的时间不同，成熟后售卖的价值也不同
要求：在限定的总时间里进行蔬菜种植，并且种植蔬菜的种类不能超出限制的数量，
选择最优的种植方案使得蔬菜成熟后售卖的总价值最大（每种蔬菜只能种植一次）
例如：给定的总时间为 55，种植蔬菜的种类限制为 3，三种蔬菜花费的时间及售卖
价格分别为： 21 和 9,20 和 2,30 和 21
最优的种植方案是选择第一种和第三种，两种农蔬菜的种植总价值 30+21=51，未
超过总时间限制 55， 所种植的蔬菜价值爱为 9+21=30，是最优的。
输入描述：
第一行输入两个正整数 t（1≤ t≤ 600） 和 m（1≤m≤ 50） ，用一个空格隔开， t 代
表种菜总时间限制， m 代表蔬菜种类
接下来的 m 行每行输入两个正整数 ti（1≤ ti≤101） 和 pi（1≤pi≤ 101） ，用一个空
格隔开， ti 表示每种蔬菜种植所花费的时间， pi 表示对应蔬菜成熟后售卖的价值
输出描述： 输出一个正整数， 表示最优方案蔬菜成熟后售卖的总价值
样例输入
55 3
21 9
20 2
30 21
样例输出
30
题目解析
这一道题同样用到了动态规划的做法，是其中典型的背包问题。要注意的点是：当使用输入做执行条件，输入到头要用Ctrl+Z打断。
AC代码
- #include<iostream>//调用输入输出流头文件
- #include<algorithm>//调用算法头文件
- using namespace std;//使用标准名字空间
- int T,M,a[609]; //总时间 T, 种类 M
- int main(){//主函数开始
- cin>>T>>M;//输入T,M的值
- for(int t,p;cin>>t>>p;)//for循环
- for(int j=T;j>=t;j--)//倒推, 使同种蔬菜仅能用 1次
- a[j]=max(a[j],a[j-t]+p);//将a的j号元素赋值为max(a[j],a[j-t]+p)
- cout<<a[T];//输出a的T号元素的值
- return 0;//主函数结束，返回0
- }
结束语
本期题解就到这里了，谢谢大家的观看！
