2022 年合肥市经开区第七届青少年信息学竞赛 小学组试题题解
目录
第一题 车辆统计
第二题 直角三角形
第三题 质因数
第四题 采摘苹果
第一题 车辆统计
(car.cpp）
注意这里不能直接翻译成英语或其他语言，并且不能添加解释或观点。因此可能无法直接修改这个词组
同样受限于规则
国豪家楼下有一个T型交叉路口。在暑假期间, 国豪会坐在路口旁边的树荫下乘凉, 有时也会一边纳凉一边观察从路口驶过的汽车, 发现大多数司机都会遵循交通信号指示, 在绿灯亮起时通过马路; 有一些司机会在黄灯即将变红时快速穿过马路; 这样的行为确实存在安全隐患; 少数司机会无视红 灯 直接通行, 看得国豪心惊肉跳; 现在给出某段时间 国豪 观察到 的车辆通过情况, 请你统计 绿 灯 、 黄 灯 、 红 灯 三种情况下通过 的车辆数
输入：
由 green、yellow、red 三个单词构成的字符串，分别表示一辆车在
绿色、黄色、红色的交通灯下经过路口。
输出：
一行三个整数，表示绿灯、黄灯、红灯三种情况下通过的车辆数。
样例输入：
greengreenyellowgreenredgreenyellow
样例输出：
4 2 1
说明：
整个字符串有 4 个 green，2 个 yellow 和 1 个 red，说明有 4 辆车在
绿灯的情况下通过，有 2 辆车在黄灯的情况下通过，有 1 辆车在红灯
的情况下通过。
数据范围：
3<=字符串的长度<=10000
题解：
本题旨在考察对字符串相关知识的理解。其中包含了green、yellow和red这三种字符串，各自具有独特的字符特征。例如，在green字符串中包含的特定字符是'g'和'n', yellow字符串中包含的特殊字符包括'y','l','w',而red字符串中包含的特殊字符是'd'.一旦出现一个’g’就会对应一次绿色状态。因此我们只需要统计这些特殊字符的数量并使用三个变量进行记录就可轻松解决这个问题。
参考程序：
#include <iostream>
#include <cstring>
using namespace std;
string s;
int green=0,yellow=0,red=0;
int main(){
//freopen("car.in","r",stdin);
//freopen("car.out","w",stdout);
cin>>s;
for(int i=0;i<s.length();i++){
//找出green、yellow、red各自的特有字符
switch(s[i]){
case 'g':
green++;
break;
case 'y':
yellow++;
break;
case 'd':
red++;
break;
default:
continue;
}
}
cout<<green<<" "<<yellow<<" "<<red<<endl;
return 0;
}第二题 直角三角形
(rt.cpp）
国豪与国庆非常热衷于研究数学，在很小的时候就对几何学产生了浓厚的兴趣，并自主学习了三角函数的基础知识。在几何学中，默认使用 a, b, c 三个小写字母来表示三条线段的长度。当且仅当这三条线段满足以下条件时：a² + b² = c²（其中 c代表斜边），则它们构成一个直角三角形。给定任意 n 条线段的长度，请问其中有多少组能够组成直角三角形？
输入：
共两行。第一行，一个整数 n，表示有 n 条边。第二行 n 个正整数，
表示每条边的长度。
输出：
共一行，一个整数，表示能构成的直角三角形的个数。
样例输入：
7
4 3 4 1 3 5 4
样例输出：
6
说明：
a^ 2 读 a 的平方，表示有 2 个 a 相乘，即 a×a。
在样例输入中可以选择从7条边上挑选出长度分别为3、4、5的三条边；原因在于这些长度满足毕达哥拉斯定理（3^2 +4^2=5^2），因此这三条边能够构成一个直角三角形；此外还值得注意的是这些长度中有两条是与数字3相关联的
次，4 出现了 3 次，所以一共能构成 2*3=6 个直角三角形。
数据范围：
3<=n<=100000
1<=每条边的长度<=1000
题解：
本题旨在识别一组数字中能够形成直角三角形的所有三元组。值得注意的是，在这组数字中可能存在重复值。寻找能够构成直角三角形的三元组数量是最直观的想法就是通过循环遍历所有可能的组合。寻找这些符合条件的三元组最直接的方法就是使用三种不同的循环结构（即三层循环）。然而这种方法会导致代码运行效率低下，在面对大量测试数据时容易出现性能瓶颈问题。因此我们需要想办法对这种思路进行一个改进以提高算法性能并解决上述问题
首先，在处理过程中可能会遇到相同的数值。为了高效统计这些数值的数量关系，在设计一个数据结构时可以采用映射表的方式进行处理。具体来说，在建立一个二维数组时可以将其分解为两个区域：第一列为数值存储区域（即键的位置），第二列为频率统计区域（即值的位置）。这种设计方式不仅能够反映每个数值出现的具体次数（类似于map的功能），还能方便后续的数据运算需求。当我们需要计算满足条件的所有组合数量时（例如能构成直角三角形的情况），可以通过将对应频率区域的数据进行乘法运算，并将这些乘积结果累加起来就能得到总的三角形数量。这种方法既避免了数据冗余带来的问题（如重复计算相同组合的情况），又能够在一定程度上提升算法运行效率
此外还需要优化循环结构。由于三重for循环的时间复杂度过高导致运行超时问题我们可以尝试将其降维至二重从而提升效率。具体来说当我们遍历所有可能的两个数组合时计算出由这两条直角边所确定的斜边长度并检查该长度是否存在于数组中。如果找到对应的斜边则将这三个数组各自的出现次数（二维数组中的第二个数值）相乘并将结果累加到计数器中；否则则跳过这一组数据继续处理下一对组合数据。
最后一个问题可以采用二分查找来提高效率。
对于那些尚未掌握二分查找原理的人来说，
可以在对数据进行排序后利用这一方法，
从而能显著提升代码效率
参考程序：
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[100005],cnt=0,i,j,k,result=-1,target;
int num[100005][2];
int c[100005]={0};
int index=0;
//二分查找斜边
int BinarySearch(int arr[][2], int j,int len, int target) {
int low = j+1;
int high = len;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (target < arr[mid][0]*arr[mid][0]) high = mid - 1;
else if (target > arr[mid][0]*arr[mid][0]) low = mid + 1;
else return mid;
}
return -1;
}
int main(){
//freopen("rt.in","r",stdin);
//freopen("rt.out","w",stdout);
cin>>n;
for(i=0;i<n;i++) cin>>a[i];
//次数累乘法：建立一个二维数组，第一列为数的数值，第二列为该数值出现的次数
//首先统计每个元素出现的次数
for(i=0;i<n;i++){
c[a[i]]++;
}
j=0;
//构造二维数组
for(i=0;i<n;i++){
if(c[i]!=0){
num[j][0]=i;
num[j++][1]=c[i];
index++;
}
}
//枚举直角边，计算斜边，利用二分查找斜边降低时间复杂度
for(i=0;i<=index-3;i++){
for(j=i+1;j<=index-2;j++){
target=num[i][0]*num[i][0]+num[j][0]*num[j][0];
result=BinarySearch(num,j,index-1,target);
if(result!=-1){
cnt+=num[i][1]*num[j][1]*num[result][1];
}
}
}
cout<<cnt<<endl;
return 0;
}第三题 质因数
(prime.cpp）
国豪熟悉多种素数判定方式，并非仅限于简单的试除法。例如列举该合数的所有因数组合时需要考虑优化方案。国庆希望通过问题来检验国豪对素数认识的深度及其应用能力。于是提出一个问题：给定一个合數c，请统计其質因數的個數量、每一個質因数值及其出现次數。
输入：
共一行，一个正整数 c。
输出：
若干行。第一行表示 c 的质因数的个数。接下来若干行，按照字典序
给出 c 的每个质因数及其出现的次数。
样例输入：
600
样例输出：
3
2 3
3 1 5 2
说明：
600=2 3 35 2 ，600 有三个质因数，从小到大依次是 2,3,5，其中 2 出
现了 3 次，3 出现了 1 次,5 出现了 2 次。
数据范围：
4<=c<=2000000000
题解：
进行质因数分解时通常采用while循环而非for循环的原因在于for循环仅能获取到因数但未必是质因数而使用while循环则能更加便捷地确定质因子考虑到采用while循环更为便捷从而使得问题得以轻松解决。
参考程序：
#include <iostream>
#include <cmath>
using namespace std;
int c,t,cnt=0,k=0,flag;
int a[100005]={0},b[100005]={0};
int main(){
//freopen("prime.in","r",stdin);
//freopen("prime.out","w",stdout);
cin>>c;
t=c; //用变量t暂存c的值
for(int i=2;i<=t/2;i++){
flag=0; //flag是状态标志，若能分解出质因子，则置为1
//注意用while循环不要用for循环，否则求解出的是因子而不是质因子
while(c%i==0){
flag=1;
a[k]=i;
b[k]++;
c/=i;
}
if(flag==1){
cnt++;
k++;
}
}
cout<<cnt<<endl;
for(int i=0;i<cnt;i++){
cout<<a[i]<<" "<<b[i]<<endl;
}
return 0;
}第四题 采摘苹果
(apple.cpp）
深秋时节里
输入：
共 n+2 行。第 1 行，两个正整数 n 和 s。第 2 行，两个正整数 a 和 b。
接下来的 n 行，每行两个正整数 xi 和 yi。
输出：
共一行，一个整数，表示国豪最多能摘到的苹果数。
样例输入：
4 10 20 140
150 4
170 2
130 5
155 3
样例输出：
2
说明：
共有4个苹果。国豪的体力值达到了10单位。他能够到达的最大高度是最高可达的高度为160米。第二个苹果超出他所能触及的高度范围因而无法采摘；剩下的三个苹果虽然都在可采摘范围内但他目前的体能水平只能让他完成两个采摘任务。
数据范围：
n<=5000,a<=50,b<=200,s<=1000,xi<=280,yi<=100
题解：
本题所需存储的数据量较大，在理清解题思路时并不算困难。需要注意的是题目要求的是 国豪所能摘取的最大数量的苹果，在此过程中 国豪每采摘一个苹果会耗费一定数量的体力值 为了最大限度地获取更多的果实 我们必须采用贪心算法 其核心策略在于优先选取那些对体力消耗较低的苹果 这种选择方式能够最终导至全局最优的结果 为了确定哪些水果属于这一类 我们通常会按照yi从小到大的顺序进行排序 在排序过程中相应地调整xi的位置排列 并采用冒泡排序方法即可解决问题
参考程序：
#include <iostream>
using namespace std;
int main(){
//freopen("apple.in","r",stdin);
//freopen("apple.out","w",stdout);
int n,s,a,b,cnt=0,i,j,t1,t2;
int x[5005],y[5005];
cin>>n>>s;
cin>>a>>b;
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
}
//按体力值进行冒泡排序
for(i=0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(y[j]>y[j+1]){
t1=x[j];x[j]=x[j+1];x[j+1]=t1;
t2=y[j];y[j]=y[j+1];y[j+1]=t2;
}
}
}
for(i=0;i<n;i++){
if(a+b>=x[i]&&s>=y[i]){
cnt++;
s-=y[i]; //注意：摘到后体力要被消耗
}
}
cout<<cnt<<endl;
return 0;
}