**欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
编程题
B3968 成绩排序
【题目来源】
洛谷：B3968 [GESP202403 五级] 成绩排序 - 洛谷
【题目描述】
有 名同学，每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序：
- 比较总分，高者靠前；
- 如果总分相同，则比较语文和数学两科总分，高者靠前；
- 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
- 如果仍相同，则二人并列。
你需要输出每位同学的排名，如遇x xx人并列，则他们排名相同，并留空后面的x − 1 x-1x−1个名次。例如，有3 33名同学并列第1 11，则后一名同学自动成为第4 44名。
【输入】
第一行一个整数N NN，表示同学的人数。
接下来N NN行，每行三个非负整数c i , m i , e i c_i,m_i,e_ici,mi,ei分别表示该名同学的语文、数学、英语成绩。
【输出】
输出N NN行，按输入同学的顺序，输出他们的排名。
注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名
【输入样例】
6 140 140 150 140 149 140 148 141 140 141 148 140 145 145 139 0 0 0【输出样例】
1 3 4 4 2 6【算法标签】
《洛谷 B3968 成绩排序》 #模拟# #排序# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intn;// 学生人数// 学生结构体，存储各科成绩和相关信息structStu{intyw,sx,yy;// 语文、数学、英语成绩inttot;// 总分intys;// 语文+数学总分intmax_ys;// 语文和数学中的最高分intid;// 学生编号intrk;// 最终排名};Stu stu[10005];// 学生数组// 排序比较函数1：用于成绩排序boolcmp(Stu x,Stu y){if(x.tot!=y.tot)returnx.tot>y.tot;// 规则1：总分高的在前elseif(x.ys!=y.ys)returnx.ys>y.ys;// 规则2：语文+数学高的在前elseif(x.max_ys!=y.max_ys)returnx.max_ys>y.max_ys;// 规则3：语文或数学单科高的在前elsereturnx.id<y.id;// 规则4：编号小的在前}// 排序比较函数2：用于按学生编号排序输出boolcmp2(Stu x,Stu y){returnx.id<y.id;}intmain(){cin>>n;// 输入学生人数// 输入并处理每个学生的成绩数据for(inti=1;i<=n;i++){intci,mi,ei;cin>>ci>>mi>>ei;stu[i].id=i;// 记录学生编号stu[i].yw=ci;// 语文成绩stu[i].sx=mi;// 数学成绩stu[i].yy=ei;// 英语成绩stu[i].ys=ci+mi;// 语文+数学总分stu[i].max_ys=max(ci,mi);// 语文或数学最高分stu[i].tot=ci+mi+ei;// 三科总分}// 第一次排序：按成绩规则排序sort(stu+1,stu+n+1,cmp);intcnt=1;// 排名计数器// 计算每个学生的实际排名（处理并列情况）for(inti=1;i<=n;i++){// 检查是否与前一名学生成绩完全相同if(i>1&&stu[i].tot==stu[i-1].tot&&stu[i].ys==stu[i-1].ys&&stu[i].max_ys==stu[i-1].max_ys){stu[i].rk=stu[i-1].rk;// 并列排名}else{stu[i].rk=cnt;// 新排名}cnt++;// 排名计数器递增}// 第二次排序：按学生编号排序，方便输出sort(stu+1,stu+n+1,cmp2);// 输出每个学生的排名for(inti=1;i<=n;i++){cout<<stu[i].rk<<endl;}return0;}【运行结果】
6 140 140 150 140 149 140 148 141 140 141 148 140 145 145 139 0 0 0 1 3 4 4 2 6B3969 B-smooth 数
【题目来源】
洛谷：B3969 [GESP202403 五级] B-smooth 数 - 洛谷
【题目描述】
小杨同学想寻找一种名为B BB-smooth 数的正整数。
如果一个正整数的最大质因子不超过B BB，则该正整数为B BB-smooth 数。
小杨同学想知道，对于给定的n nn和B BB，有多少个不超过n nn的B BB-smooth 数。
【输入】
第一行包含两个正整数n nn和B BB，含义如题面所示。
【输出】
输出一个非负整数，表示不超过n nn的B BB-smooth 数的数量。
【输入样例】
10 3【输出样例】
7【算法标签】
《洛谷 B3969 [GESP202403 五级] B-smooth 数》 #素数判断,质数,筛法# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intn,B,ans,cnt;intmaxPrime[1000005],prime[1000005],notPrime[1000005];// 欧拉筛法预处理所有数的最大质因子voidgetPrime(){prime[1]=1;// 1不是质数maxPrime[1]=1;// 1的最大质因子设为1for(inti=2;i<=1000000;i++){if(!notPrime[i]){// 如果是质数prime[cnt++]=i;// 存入质数数组maxPrime[i]=i;// 质数的最大质因子是其本身}// 用当前数和已知质数筛去合数for(intj=0;j<cnt&&i*prime[j]<=1000000;j++){notPrime[i*prime[j]]=1;// 标记为合数// 计算i*prime[j]的最大质因子maxPrime[i*prime[j]]=max(prime[j],maxPrime[i]);// 关键优化：保证每个合数只被最小质因子筛一次if(i%prime[j]==0){break;}}}}intmain(){cin>>n>>B;// 输入范围n和阈值BgetPrime();// 预处理所有数的最大质因子// 统计1到n中最大质因子不超过B的数的个数for(inti=1;i<=n;i++){if(maxPrime[i]<=B){ans++;}}cout<<ans<<endl;// 输出结果return0;}#include<bits/stdc++.h>usingnamespacestd;intn,B,cnt,cur;intmaxPrime[1000005],prime[1000005];boolflag[1000005];// 埃拉托斯特尼筛法（埃氏筛）预处理最大质因子voidgetPrime(){memset(flag,true,sizeof(flag));// 初始化为true，表示都是质数flag[0]=flag[1]=false;// 0和1不是质数maxPrime[1]=1;// 1的最大质因子设为1for(inti=2;i<=n;i++){if(flag[i]){// 如果i是质数prime[++cur]=i;// 存入质数数组maxPrime[i]=i;// 质数的最大质因子是其本身// 标记i的所有倍数为合数for(intj=2*i;j<=n;j+=i){flag[j]=false;// 标记为合数maxPrime[j]=i;// 更新其最大质因子为i}}}}intmain(){cin>>n>>B;// 输入范围n和阈值BgetPrime();// 预处理最大质因子// 统计1到n中最大质因子不超过B的数的个数for(inti=1;i<=n;i++){if(maxPrime[i]<=B){cnt++;}}cout<<cnt<<endl;// 输出结果return0;}【运行结果】
10 3 7
)
