2017 NHOI小学（C++）

A. 吃西瓜（2017 NHOI小学 1）

问题描述:

炎热的夏天来的可真快，小花猫和编程兔决定去买一个又大又甜的西瓜。可是小花和编程兔是两只非常奇怪的动物，都是偶数的爱好者，它们希望把西瓜切成两半后，每一部分的重量都是 2 的倍数公斤（大于 0）。当然有编程兔在，它们很快就决定了买哪个瓜。小朋友你知道要不要买这个瓜吗？

输入格式：
第一行只有一个正整数，表示西瓜的重量 w（单位是公斤）。

输出格式：
如果能达到要求，就输出 YES，否则就输出 NO。(注意区分大小写)
输入样例：
8
输出样例：
YES
样例说明：
8 可以分成 2 和 6，或者 4 和 4。
数据规模：
对于 100%的数据，1<=w<=100。

思路

这道题考的是循环结构和分支结构

代码

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){cin>>n;for(int i=1;i<n;i++)//循环结构if(i%2==0&&(n-i)%2==0){//分支结构cout<<"YES";return 0;//结束程序}cout<<"NO";//没有完成特判的输出return 0;
}

B. 最小的球（2017 NHOI小学 2）

问题描述：
小花是一只非常热爱乒乓球的猫，近日它混进了中国乒乓球队封闭训练的场地（为了备战 2017 年的德国世乒赛，中国男队在深圳，女队在湖北黄石，分别进行封闭训练），偷偷的玩乒乓球。小花发现这些球的大小并不是完全相同的，而是大小略有差异，在玩了很久之后它发现还是最小的那个最好玩。现在小花想知道一堆已知直径的乒乓球中最小的那颗球。
输入格式：
输入数据有两行，第一行是一个正整数 n，表示乒乓球的数量。第二行是有 n 个整数，表示每个球的直径 d，数与数之间用一个空格隔开。
输出格式：
输出只有一行一个整数，表示最小的球的直径。
输入样例：
5
4003 4002 4001 4004 4005
输出样例：
4001
样例说明：
样例中，最小的球的直径是 4001，所以答案是 4001。
数据规模：
对于 100%的数据，都有 1<=n<=100,4000<=d<4100。

一、题目考察点

这道题主要考察以下几个方面：

对基本输入输出的掌握。

循环结构的运用。

条件判断语句来找出最小值。

二、代码思路

首先从用户输入中读取乒乓球的数量 n。

然后使用一个循环，依次读取每个乒乓球的直径 x。

在循环中，通过条件判断将当前读取到的直径与已记

录的最小直径 x_min 进行比较，如果当前直径更

小，则更新 x_min。

循环结束后，输出最小直径 x_min。

三、代码

#include<bits/stdc++.h>
using namespace std;
int n,x,x_min=4101;// n 表示乒乓球的数量，x 用于临时存储每个球的直径，x_min 初始化为一个较大值，用于存储最小直径
int main(){cin>>n;// 读取乒乓球的数量for(int i=0;i<n;i++){cin>>x;// 读取每个球的直径 if(x_min>x)x_min=x;// 如果当前球的直径小于已记录的最小直径，则更新最小直径}cout<<x_min;// 输出最小的球的直径return 0;
}

C. 比分（2017 NHOI小学 3）

问题描述：

小花在乒乓球馆里最喜欢一个叫樊振东的选手，今天它趴在窗户上看了一下午他们的训练，直到被打扫卫生的大叔赶走。小花的记性非常好，能够记录一整个下午的比赛情况，比如它记录的情况是（其中 F 表示樊振东选手获得一分，A 表示樊振东的对手获得一分）：FFFFFFFFFFFFFFFFFFFFFFAF。在当前的赛制下，此时比赛的结果是樊振东第一局 11 比 0 获胜，第二局 11 比 0 获胜，正在进行第三局，当前比分 1 比 1。
因为小花看得太全神贯注了，完全没有注意比分，以至于它完全不知道一下午的具体比分，于是小花找了它的好朋友编程兔来帮忙。可是编程兔去挖萝卜了，于是小花来求助聪明的小朋友们。
你的程序就是要对于一系列比赛信息的输入（FA 形式），输出正确的结果。
注：
1）当前使用的是 11 分制，到 10 平后，需要胜出 2 分后，才算胜，如：12：10；17：15 等。
2）如果一局比赛刚开始，则此时比分不必输出。
3）输入数据每行至多 20 个字母，行数可能很多，最多可能有 10000 行。
输入格式：
输入包含若干行字符串（每行至多 20 个字母），字符串由大写的 F、A 和 E 组成。
其中 E 表示比赛信息结束，程序应该忽略 E 之后的所有内容。
输出格式：
输出有若干行，每一行对应一局比赛的比分（按输入顺序）。
输入样例：
FFFFFFFFFFFFFFFFFFFF
FFAFE
输出样例：
11:0
11:0
1:1
样例说明：
前 11 分都是 F，所以第一局 11:0，之后 11 分也都是 F，所以第二句也是 11:0，最后两分分别是 A 和 F，所以是 1:1，E 表示结束。
数据规模：
每行最多有 20 个字符，只有 F、A 和 E 三种字母，没有其他多余的字母。
对于 30%的数据，输入只有一行。
对于 60%的数据，输入不超过 10 行。
对于 100%的数据，输入数据不超过 10000 行。

思路

本题考查字符串的应用

代码

#include<bits/stdc++.h>
using namespace std;
char s;
long long x,y;
//定义双方得分
int main(){for(;;)//无限循环{cin>>s;if(s=='F')x++;//统计樊振东得分if(s=='A')y++;//统计对手得分if(x==11&&y<=9)cout<<x<<":"<<y<<endl,x=0,y=0;//判断比分是否结束if(y==11&&x<=9)cout<<x<<":"<<y<<endl,x=0,y=0;if(x>=10&&y>=10)if(abs(x-y)==2)cout<<x<<":"<<y<<endl,x=0,y=0;
//判断特殊情况if(s=='E'){if(x!=0&&x!=0)cout<<x<<":"<<y<<endl;break;}//E结束，输出现比分}return 0;
}

D. 吃鱼（2017 NHOI小学 4）

问题描述：

小花爱吃鱼，这是全世界都知道的事情。它的好朋友编程兔给它准备了很多的零食，每一样都是小花喜欢的。当然了，里面最多的肯定是鱼。某一天编程兔给小花准备了两种鱼，一种鱼的重量是 1，另一种鱼的重量是 2，重量为 1 的鱼有不同的美味值，重量为 2 的鱼也有不同的美味值。现在假设小花的胃口最多能吃下不超过重量为 v 的鱼，小花希望吃掉的鱼的美味值总和最大。
输入格式：
输入数据第一行是两个正整数 n 和 v，n 表示鱼的数量，v 表示小花的胃口。接下来 n 行，每行两个正整数，第一个正整数表示鱼的重量（只有 1 和 2 两种可能），另一个正整数表示这条的美味值。
输出格式：
输出只有一行一个整数，表示小花能得到的最大美味值总和。
输入样例：
3 2
1 2
2 7
1 3
输出样例：
7
样例说明：
小花选择了第 2 条鱼吃，美味值是 7。
数据规模:
对于 60%的数据，1<=n<=2000。
对于 100%的数据，1<=n<=30000,1<=v<=60000,每条鱼的美味值不超过 10000。

#include<bits/stdc++.h>
using namespace std;
long long n,v,x,y,s1,s2,l,r,s,a[100005],b[100005];
bool cmp(int a,int b){return a>b;
}
int main(){cin>>n>>v;for(int i=1;i<=n;i++){cin>>x>>y;if(x==1)a[++s1]=y;else b[++s2]=y;}sort(a+1,a+1+s1,cmp),sort(b+1,b+1+s2,cmp);if(s2*2>=v){r=v/2;if(r*2<v)l++;}else r=s2,l=v-r*2;while(l<=s1&&r){if(b[r]<a[l+1]+a[l+2])r--,l+=2;else break;}for(int i=1;i<=l;i++){s+=a[i];}for(int i=1;i<=r;i++){s+=b[i];}cout<<s;return 0;
}

E. 折纸（2017 NHOI小学 5）

问题描述

有一天，小花偷偷的溜进教室，发现同学们正在上数学课，课上老师在讲一个关于折纸的问题。有一张 a 毫米*b 毫米的纸(a>b)，每次按照下图所示，折出一个边长为 b的等腰直角三角形，然后把直角三角形剪掉，然后对于余下的 b*（a-b)的矩形做同样的处理，一直重复这个过程，直到剩余的纸是正方形，对这个正方形做完最后一次折纸就结束了。

现在的问题是，对于一张 a*b（a>b)的纸，需要折多少次才能使得这张纸被剪没了。

输入格式：
输入只有一行两个正整数 a 和 b(a>b)，表示矩形的大小。
输出格式：
输出需要折的次数。
输入样例 1：
2 1
输出样例 1：
2
输入样例 2：
10 7
输出样例 2：
6
样例说明：
第一个样例和第二个样例的说明：
数据规模：
对于 60%的数据，1<=b<a<=2000。
对于 100%的数据,1<=b<a<10^12。

考点

本题考查数学思维

思路

这题它说要折成一个等腰直角三角形，再剪掉，其实它的意思是在一个长方形纸上一直减去一个最大的正方形，这个过程可以用出发一步到位。

代码

#include<bits/stdc++.h>
using namespace std;
long long a,b,k;
int main(){cin>>a>>b;for(;;){k+=a/b;//剪了几次a%=b;//剪完还剩多少if(b>a) swap(a,b);//交换长边与短边if(a==b||b==0||a==0) break;//剪不了就退出} cout<<k;return 0;
}

F. 吃萝卜（2017 NHOI小学 6）

问题描述：

在一个神奇的国度里，有一只编程兔，它每天都写很多的代码，各种编程语言如pascal、c、c++、java、basic 等等它都了如指掌，各种算法也都已经滚瓜烂熟了。小花是它的好朋友，经常和它一起玩耍。
某一天，小花给编程兔送来了很多的萝卜。编程兔很开心，决定把它的萝卜和其它的小兔子一起分享。小花共计送来了 n 袋萝卜（编号 1 到 n），每袋里面都有一定数量的萝卜。小兔子共计有 m 只，兔子们都很守规矩，按照编号 1 到 m 依次排好领取萝卜，萝卜按照编号从小到大的顺序依次发放（也就是编号小的兔子领取前面的萝卜，编号大的兔子领取后面的萝卜，萝卜一定要分完，不能有剩余），每只兔子都只能领取连续的若干袋萝卜，每只兔子至少领取一袋萝卜，一袋萝卜也只能分给一只兔子，不能分给两只以上的兔子。
编程兔希望萝卜尽量能分的平均一点（否则小兔子们要不开心的^_^），也就是它希望得到萝卜最多数量的兔子的萝卜要最少。这个问题对于编程兔来说很简单,亲爱的同学们，你们会么？
输入格式：
第一行是两个正整数 n 和 m，表示萝卜的袋数和兔子的数量。
第二行是 n 个正整数，表示每袋萝卜的数量。
输出格式：
输出只有一行一个整数，表示得到萝卜最多的那只兔子最少可以得到的萝卜数量，即让最大值最小。
输入样例 1：
9 3
1 2 3 4 5 6 7 8 9
输出样例 1：
17
输入样例 2：
5 2
3 2 5 4 3
输出样例 2：
10
样例说明：
样例 1 中，第 1-5 袋萝卜分给第一只兔子，总数是 15 个萝卜，第 6-7 袋萝卜分给第二只兔子，总数是 13 个萝卜，第 8-9 袋萝卜分给第三只兔子，总数是 17 个萝卜，萝卜最多的兔子得了 17 个萝卜，这是最多的兔子得到的最少的情况。如果第 1-4 袋分给第一只兔子，共计 10 个萝卜，第 5-7 袋分给第二只兔子共计 18 个萝卜，第 8-9 袋分给第三只兔子，共计 17 个萝卜，这样最多的兔子得到了 18 个萝卜，比之前的方案大，所以不是最优。
样例 2 中，第 1-3 袋萝卜分给第一只兔子，得到 10 个萝卜，第 4-5 袋萝卜分给第二只兔子，得到 7 个萝卜，所以最多的兔子得到了 10 个萝卜，这是最优的情况。
数据规模：
对于 60%的数据，1<=m<=n<=100,每袋萝卜的数量不超过 10。
对于 100%的数据，1<=m<=n<=100000,每袋萝卜的数量不超过 10000。

一、题目考察内容

这道题主要考察了二分查找算法的应用以及对问题的分析和建模能力。具体来说，考察了以下几个方面： 对问题的理解和建模能力：将萝卜分配问题转化为一个求最大值最小的问题。 二分查找的应用：通过不断缩小可能的答案范围，找到满足条件的最优解。 算法的实现能力：能够正确地实现给定的算法逻辑，处理输入、进行计算并输出结果。

二、代码思路

首先读取输入的萝卜袋数 n 和兔子数量 m，并初始化两个变量 l 和 r，分别表示可能的答案范围的最小值和最大值。 l 初始化为单袋萝卜中数量最多的，通过遍历输入的每袋萝卜数量，找到最大值并赋值给 l。 r 初始化为所有萝卜数量之和。 然后进入一个循环，使用二分查找的方法不断缩小答案范围。 在每次循环中，取 l 和 r 的中间值 minn，并初始化变量 s1（表示当前分配方案下兔子的数量）和 s（表示当前正在考虑的兔子已经分配到的萝卜数量）为 0。 遍历每袋萝卜，将萝卜数量累加到 s 中。如果 s 超过当前的中间值 minn，说明这只兔子分配的萝卜太多了，需要增加一只兔子来分萝卜，此时将 s1 加 1，并将 s 重置为当前袋的萝卜数量。 遍历完所有萝卜后，s1 为当前分配方案下兔子的数量。如果 s1 大于给定的兔子数量 m，说明当前尝试的中间值 minn 过小，需要增大 l；否则说明当前尝试值可能过大，需要减小 r。 循环结束后，l 就是得到萝卜最多的那只兔子最少可以得到的萝卜数量，输出 l 作为结果。

三、代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],l,r,minn,s1,s;
int main(){scanf("%d%d",&n,&m);//输入萝卜的袋数n和兔子的数量mfor(int i=1;i<=n;i++){scanf("%d",&a[i]);//输入每袋萝卜的数量并更新l和r的初始值l=max(l,a[i]);//l初始为单袋萝卜中数量最多的r+=a[i];//r初始为所有萝卜数量之和}while(l<=r){minn=(l+r)>>1;//尝试当前的中间值作为最多兔子得到的萝卜数量s1=0,s=0;for(int i=1;i<=n;i++){s+=a[i];//累加当前考虑的连续几袋萝卜的数量if(s>minn){s1++;//如果累计数量超过当前尝试值，说明需要增加一只兔子来分萝卜s=a[i];}}s1++;//统计完所有萝卜后，s1 为当前分配方案下兔子的数量if(s1>m){l=minn+1;//如果兔子数量超过给定数量 m，说明当前尝试值过小，需要增大 l}else {r=minn-1;// 如果兔子数量不超过给定数量 m，说明当前尝试值可能过大，需要减小 r}}printf("%d",l);// 输出最终结果，即得到萝卜最多的那只兔子最少可以得到的萝卜数量return 0;
}