2017年南海区青少年信息学奥林匹克竞赛（小学甲组）
A. 吃西瓜
题目描述
夏天来得异常迅速，在这炎热的季节里很快就要到了。小花猫与编程兔决定去购买一个又大又甜的大西瓜。然而小花与编程兔是两只非常特别的小动物--都喜欢数字2的各种倍数。它们希望将西瓜切成两半后每一份都重达2公斤以上的整数值。当然有编程兔在--它们很快就做出了决定要买哪个瓜了。小朋友你是否想跟他们一起买这样一个瓜呢？
第一行为唯一的一个正整数变量w（单位为公斤）。当达到预期条件时，请输出'YES'；若未达到，则输出'NO'。（区分大小写字母）
样例输入1
8
样例输出 1
YES
样例说明：
8可以分成2和6，或者4和4。
数据范围：
对于100%的数据，1≤w≤100。
坑点：2是只能分成1&1，是不满足的 （就是我错了）
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int a;
int main() {
freopen("watermelon.in", "r", stdin);
freopen("watermelon.out", "w", stdout);
cin >> a;
if (a % 2 == 0&&a!=2)//注意！！！
cout << "YES";
else
cout << "NO";
return 0;
}B.最小的球
题目描述
这只猫对乒乓球有着浓厚的兴趣。近日它混入了中国乒乓球队封闭集训场地（为备战2017年德国世乒赛，在深圳和湖北黄石分别设置了男队与女队封闭集训），潜心研究起桌上的乒乓球来。经过长时间练习后发现，在这些大小不一的小球中找到一个是最有趣的。现在她想找出一堆直径已知且大小不一的所有乒乓球中最小的那一颗球。
输入格式
第一行为一个正整数n（表示乒乓球的数量）。
第二行为n个互不相同的正整数值（这些值代表每个球的直径），它们之间用空格分隔开。
输出格式
一行输出一个最小值（即为所有乒乓球中最小的那个直径）。
样例输入 1
5
4003 4002 4001 4004 4005
样例输出 1
4001
样例说明：
样例中，最小的球的直径是4001，所以答案是4001。
数据范围：
对于100%的数据，都有1≤n小于等于100,4000≤d＜4100。
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
int a, ans, n;
int main() {
freopen("ball.in", "r", stdin);
freopen("ball.out", "w", stdout);
cin >> n;
ans = 50000;
for (int i = 1; i <= n; i++) {
cin >> a;
ans = min(ans, a);
}
cout << ans;
return 0;
}C.比分
题目描述
输入格式
输入由多个字符串构成（每个字符串长度不超过20个字符），这些字符串仅包含大写字母F、A和E。
其中字符E标识比赛信息结束的位置，在此之后的所有数据应被系统忽略。
输出格式：输出结果将由多行数据呈现，并且每一行对应一局比赛的具体情况记录。（具体记录内容可参考示例）
每一行记录一局比赛的结果数据，并按照输入顺序进行排列。
样例输入 1
FFFFFFFFFFFFFFFFFFFF
FFAFE
样例输出 1
11:0
11:0
1:1
样例说明
数据范围
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
char c;
int F, A;
void same() {
if (c == 'E' || F - A == 2 || A - F == 2) {
cout << F << ":" << A << endl;
F = 0;
A = 0;
return;
}
cin >> c;
if (c == 'F')
F++;
if (c == 'A')
A++;
same();
}
int main() {
freopen("score.in", "r", stdin);
freopen("score.out", "w", stdout);
while (c != 'E') {
cin >> c;
if (c == 'F')
F++;
if (c == 'A')
A++;
if (F == 10 && A == 10)
same();
if (F == 11 || A == 11) {
cout << F << ":" << A << endl;
F = 0;
A = 0;
}
}
if (F != 0 || A != 0)
cout << F << ":" << A << endl;//注意
return 0;
}D.吃鱼
题目描述
小花对鱼类有着特殊的偏好，在全球范围内这是一直以来的事实。她的好友编程兔特意为她准备了许多美味的食物，并非只有鱼类最受欢迎。不过，在某些特定的情况下，“其中最主要的自然是鱼类”。某天早晨时分（假设）（假设）（假设），编程兔带来了两种不同规格的食物——一种规格是1kg、另一种规格是2kg（见公式）。这些食物不仅种类丰富（见公式），而且每种规格的食物都有其独特的风味价值（见公式）。现在假设你必须从这些食物中选择一部分（见公式），并且你无法超过自己的食量限制v，则你的目标是在不超过食量限制的前提下获得最大的风味总和（见公式）。
输入格式
第一行为两个正整数n与v，分别代表鱼的数量及小花的食量。
随后的n行中，每一行为两个正整数w_i与f_i（其中i=1,2,...,n），其中w_i仅限于1和2两种数值，并用作标记第i条鱼的重量参数；而f_i则用作标记第i条鱼对应的美味度数值。
输出格式
一行输出一个整数值m_{\text{max}}, 表示小花能够获取的最大美味度数值之总合。
样例输入 1
3 2
1 2
2 7
1 3
样例输出 1
7
样例说明：
数据范围：
我们很容易想到贪心，但具体怎么实现就有待思考
先放90分代码
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
int n, k, ans;
struct food {
int y, w;
double v;
} p[30005];
bool cmp(food a, food b) {
if (a.v != b.v)
return a.v > b.v;
if (a.v == b.v)
return a.y > b.y;
}
int main() {
freopen("fish.in", "r", stdin);
freopen("fish.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> p[i].w >> p[i].y;
p[i].v = p[i].y / p[i].w;
}
sort(p + 1, p + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
if (k == 0)
break;
if (k >= p[i].w)
ans = ans + p[i].y, k = k - p[i].w;
}
cout << ans;
return 0;
}看起了似乎没有问题
但我们出个样例试试
3 4
2 10
1 5
2 6
正确答案应该是16
但这个代码输出的是15
so,让我们想一想（2000 years later……)
想到啦！
先用二鱼填满，如果还有空位就吃一鱼，再用二鱼换2*一鱼，比原来大则换
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
int n, k, tx, ty, x[30005], y[30005], v, ans, w, s;
bool cmp(int a, int b) { return a > b; }
int main() {
freopen("fish.in", "r", stdin);
freopen("fish.out", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> v;
if (v == 1)
cin >> x[++tx];
if (v == 2)
cin >> y[++ty];
}
sort(y + 1, y + 1 + ty, cmp);
sort(x + 1, x + 1 + tx, cmp);
for (int i = 1; i <= ty; i++) {
if (w * 2 <= k) {
w++;
ans = ans + y[w];
}
}//先用二鱼填满
s = 1;
v = w * 2;
while (v < k) {
v = v + 1;
ans = ans + x[s];
s++;
}//还有空位就吃一鱼
for (; s <= tx;) {
if (y[w] <= x[s] + x[s + 1]) {
ans = ans - y[w];
ans = ans + x[s] + x[s + 1];
w--;
s = s + 2;
}//再用二鱼换2*一鱼，比原来大则换
else
break;
}
cout << ans;
return 0;
}E. 折纸
题目描述
某天早晨, 小花暗中潜入教室, 发现学生们正在进行一节数学课. 在课堂上, 老师正在讲解一个与 origami 折纸相关的问题. 现在有一张 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 <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
long long a, b, ans;
int main() {
freopen("paper.in", "r", stdin);
freopen("paper.out", "w", stdout);
cin >> a >> b;
while (a != b) {
if (a <= b)
swap(a, b);
if (a % b == 0) {
ans = ans + a / b;
cout << ans;
return 0;
}
if (a % b != 0) {
ans = ans + a / b;
a = a % b;
}
}
return 0;
}F. 分萝卜
题目描述
在一个充满魔法的世界里，有一只聪明的编程兔（兔兔），它每天都会编写大量的代码，在各种编程语言中如Pascal、C、C++、Java、Basic等都表现得非常出色，并且对各种算法都有深入的理解和应用能力。它的朋友小花经常与之互动玩耍。
一天早晨，小花送给了兔兔一共有n袋胡萝卜（每袋胡萝卜都有不同的数量）。兔兔非常高兴，并决定将这些胡萝卜与其他小兔子一起分享。小花一共带来了n袋胡萝卜（编号从1到n），每袋胡萝卜的数量各不相同。兔兔共有m只 companion 兔子（按照编号1到m依次排列），它们都很守规矩地按照编号从小到大的顺序领取胡萝卜（即先领取第1号胡萝卜的排位较小的兔子）。
为了让分发更加公平合理，请同学们思考以下问题：
假设我们希望将胡萝卜尽可能平均地分配给所有兔子——也就是让分得最多胡萝卜的那个 rabbit 所得到的数量最少——那么应该如何分配呢？这个问题对于编程兔来说很简单，请同学们积极思考！
输入格式
第一行包含两个正整数n和m，分别代表萝卜的袋数n和兔子的数量m。
接下来的一行包含n个正整数a_1, a_2, \dots, a_n（其中a_i \geq 1），这些数字分别代表每袋萝卜的数量。
输出格式
输出一行一个整数值x，表示在满足所有条件的情况下使得获得最多萝卜的那只兔子所获得的数量尽可能少（即最小化最大值）。
样例输入 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个胡萝卜），那么此时第二只兔子获得了最多的数量（即最大值）。因此这种情况下不是最优解。
在样例2中，则是将第1至3袋胡萝卜分配给第一只兔子（共计10个胡萝卜），并将第4至5袋胡萝卜分配给第二只兔子（共计 7 个 胡 蘑）。其中获得最多 胡 蘑 的 数 量 是 10 个 （即最大值），这对应的是最优解的情形
对于60%的案例而言，在满足条件的情况下（即m和n满足关系式1\leq m\leq n\leq 10），每袋萝卜的数量最多为十。而对于全部案例而言（即m和n满足关系式1\leq m\leq n\leq 1\times 1e4），每袋萝卜的数量最多为一千。
二分答案，但我一开始只有60分，原因竟是……
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
long long n, m, a[100005], l, r, mid, ans;
bool check(int maxx) {
int p = 1, k = 0;
for (int i = 1; i <= n; i++) {
if (k + a[i] <= maxx)
k = k + a[i];
else {
if (a[i] <= maxx)
k = a[i], p++;
else//判断如果一袋萝卜都比最大的大，那就return 0 （我就没有加判断）
return 0;
}
}
if (p > m)
return 0;
else
return 1;
}
int main() {
freopen("eat.in", "r", stdin);
freopen("eat.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], r = r + a[i];
l = a[1];
while (l < r) {
mid = (l + r) / 2;
if (check(mid) == 0)
l = mid + 1;
else
r = mid, ans = mid;
}
cout << ans;
return 0;
}完美结束！
这次考了540（第二名） yeah ~ o(￣▽￣)ブ~
第一依旧是那个大佬（600）太厉害啦
总体还不错，比上次好。
~ o(￣▽￣)ブ~
主要是前面做的快
下次前面的题要做快点!!!