蓝桥杯刷题冲刺 | 倒计时20天
作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾
文章目录
- 1.铁路与公路
- 2.数字反转
- 3.奖学金
- 4.求阶乘
1.铁路与公路
-
题目
链接： 4074. 铁路与公路 - AcWing题库
某国家有 n 个城市（编号 1∼n）和 m 条双向铁路。
每条铁路连接两个不同的城市，没有两条铁路连接同一对城市。
除了铁路以外，该国家还有公路。
对于每对不同的城市 x,y，当且仅当它们之间没有铁路时，它们之间会存在一条双向公路。
经过每条铁路或公路都需要花费 1 小时的时间。
现在有一列火车和一辆汽车同时离开城市 1，它们的目的地都是城市 n。
它们不会在途中停靠（但是可以在城市 n 停靠）。
火车只能沿铁路行驶，汽车只能沿公路行驶。
请你为它们规划行进路线，每条路线中可重复经过同一条铁路或公路，但是为了避免发生事故，火车和汽车不得同时到达同一个城市（城市 n 除外）。
请问，在这些条件的约束下，两辆车全部到达城市 n 所需的最少小时数，即求更慢到达城市 n 的那辆车所需的时间的最小值。
注意，两辆车允许但不必要同时到达城市 n。
输入格式
第一行包含整数 n 和 m。
接下来 m 行，每行包含两个整数 u,v，表示城市 u 和城市 v 之间存在一条铁路。
输出格式
一个整数，表示所需的最少小时数。
如果至少有一辆车无法到达城市 n则输出 −1。
数据范围
前 6 个测试点满足 2≤n≤10，0≤m≤10。
所有测试点满足 2≤n≤400，0≤m≤ n ( n − 1 ) 2 n(n−1)^2 n(n−1)2，1≤u,v≤n。输入样例1：
4 2 1 3 3 4输出样例1：
2输入样例2：
4 6 1 2 1 3 1 4 2 3 2 4 3 4输出样例2：
-1输入样例3：
5 5 4 2 3 5 4 5 5 1 1 2输出样例3：
3 -
分析
-
可以发现一条性质：不用考虑那些约束条件，即 除了起点之外，汽车和火车到达某一城市的最短时间不相等。
-
为什么？
假设火车从城市1到城市 x的最短时间为 t，t=1时，即 城市 1和城市 x 之间存在直接的铁路，不存在公路，则汽车从 城市1 到城市 x 的最短时间必然大于 1；t>1时，即城市1到城市 n ，没有一条直通的铁路，则有公路，汽车可以直接到，最短时间为1； -
so 我们只需要求出两者最短路的max即可
-
-
第一次 通过了 6/20个数据
#include<bits/stdc++.h> using namespace std; const int INF=1e9; const int N=410; int n,m; int g[N][N],h[N][N]; void floyd(int d[N][N]) //默写一遍板子 { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][k]+d[k][j],d[i][j]); } int main() { scanf("%d%d",&n,&m); memset(g,0x3f,sizeof g); //初始化距离 memset(h,0x3f,sizeof h); //路径初始化 while(m--) { int a,b; scanf("%d%d",&a,&b); g[a][b]=1,g[b][a]=1; //g表示铁路 } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(g[i][j]==0&&i!=j) h[i][j]=1,h[i][j]=1; //h表示 公路 } floyd(g); floyd(h); if(max(g[1][n],h[1][n])>INF) puts("-1"); //判断输出 else printf("%d",max(g[1][n],h[1][n])); return 0; } -
第二次 通过了 19/20个数据
#include<bits/stdc++.h> using namespace std; const int N=410; int n,m; int g[N][N],h[N][N]; void floyd(int d[N][N]) { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][k]+d[k][j],d[i][j]); } int main() { scanf("%d%d",&n,&m); memset(g,0x3f,sizeof g); //距离初始化 自环没考虑 memset(h,0x3f,sizeof h); //路径初始化 while(m--) { int a,b; scanf("%d%d",&a,&b); g[a][b]=1,g[b][a]=1; //1表示铁路 双向 } //处理公路 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(g[i][j]!=1) h[i][j]=1,h[j][i]=1; } floyd(g); floyd(h); if(max(g[1][n],h[1][n])>=0x3f3f3f3f/2) puts("-1"); else printf("%d",max(g[1][n],h[1][n])); return 0; } -
第三次 AC 100%
#include<bits/stdc++.h> using namespace std; const int INF=1e9; const int N=410; int n,m; int dt[N][N]; int dg[N][N]; void floyd(int d[N][N]) { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } int main() { scanf("%d%d",&n,&m); //距离初始化 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) dt[i][j]=0,dg[i][j]=0,dt[j][i]=0,dg[j][i]=0; else dt[i][j]=INF,dg[i][j]=INF,dt[j][i]=INF,dg[j][i]=INF; //加边 while(m--) { int a,b; scanf("%d%d",&a,&b); dt[a][b]=1,dt[b][a]=1; //双向边 } //处理 公路数组 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dt[i][j]!=1) dg[i][j]=1; floyd(dt); floyd(dg); if(dt[1][n]>=INF/2||dg[1][n]>=INF/2) puts("-1"); else printf("%d",max(dt[1][n],dg[1][n])); return 0; } -
反思
写完第二次之后，敲了两遍板子
开始写 第三次 ，直接AC
- 路径初始化问题，要细心一点，数据范围比较小，可以使用 Floyd 算法
- 题目的有些条件，可通过模拟，举例，把条件解决掉
- 这个题，我觉的，双向和自环，不处理，应该问题也不大吧，不过保险起见，还是写上吧
2.数字反转
-
题目
链接： 数字反转 - C语言网 (dotcpp.com)
t题目描述
给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零。
输入
输入共 1 行，一个整数N。
-1,000,000,000 ≤ N≤ 1,000,000,000。输出
输出共 1 行，一个整数，表示反转后的新数。
样例输入
123样例输出
321 -
分析
1 0 9 10^9 109 的输入可以被 int 读进来
把每一位数字都用
push_back放进数组 vector 里面去， 去掉前导0，输出就行了 -
第一次 AC 50%
#include<bits/stdc++.h> using namespace std; //数字反转，存在vector int main() { int n; scanf("%d",&n); vector<int> a; while(n>0) { a.push_back(n%10); //把每个数 放进去 n/=10; } reverse(a.begin(),a.end()); //反转，为去前导0，做准备 while(a.size()>1&&a.back()==0) a.pop_back(); //去掉前导0 for(int i=a.size()-1;i>=0;i--) //倒序输出 { printf("%d",a[i]); } return 0; } -
第二次 AC 100%
#include<bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); if(n<0) //n为负数的时候 { cout<<'-'; n=-n; } if(n==0) //n为0的时候 { cout<<0; return 0; } vector<int> a; while(n!=0) //处理各个位上的数字 { a.push_back(n%10); n/=10; } int m=0; while(a[m]==0) //去掉前导0，优化，好方法——掌握住 { m++; } for(int i=m;i<a.size();i++) { printf("%d",a[i]); } return 0; } -
一种题解
#include<bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); int s=0; while(n!=0) { s=s*10+n%10; n/=10; } printf("%d",s); return 0; }怎么说？这显得我很呆诶
-
反思
对于题中给的数据范围，要分情况分析，尤其是含有负数、0、正数的情况
- 在调试过程中，多想几种情况
对于vector 里面的函数出现了混淆，重新复习，不断查漏补缺
处理数组前导 0 ，使用简单的指针操作，记住
避免简单题，复杂化
3.奖学金
-
题目
链接： 奖学金 - C语言网 (dotcpp.com)
题目描述
某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。
任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:
7 279
5 279
这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279
7 279
则按输出错误处理，不能得分。
输入格式
包含n+1行:
第1行为一个正整数n，表示该校参加评选的学生人数。
第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n (恰好是输入数据的行号减1)。
所给的数据都是正确的，不必检验。
50%的数据满足:各学生的总成绩各不相同；
100%的数据满足: 6<=n<=300。输出格式
共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。
样例输入
6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98样例输出
6 265 4 264 3 258 2 244 1 237 -
分析
想用三个数组，把他们存起来，然后 cmp sort 排序
-
第一次 WA
#include<bits/stdc++.h> using namespace std; const int N=410; int sum[N]; int yw[N]; int id[N]; bool cmp(int x,int y) { if(sum[x]!=sum[y]) return sum[x]>sum[y]; else { if(yw[x]!=yw[y]) return yw[x]>yw[y]; else return x<y; } } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) id[i]=i; for(int i=0;i<n;i++) { int b,c; scanf("%d%d%d",&yw[i],&b,&c); sum[i]=yw[i]+b+c; } sort(id,id+n,cmp); for(int i=0;i<5;i++) { printf("%d %d\n",id[i]+1,sum[i]); } return 0; }进行 sort 无法 保证，id数组的值 不改变
想把他们 三个数据 绑在一起 ，换成 结构体试试
-
第二次 AC 100%
#include<bits/stdc++.h> using namespace std; const int N=410; struct node{ int id; int yw; int sum; }stu[N]; bool cmp(node x,node y) { if(x.sum!=y.sum) return x.sum>y.sum; if(x.yw!=y.yw) return x.yw>y.yw; return x.id<y.id; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); stu[i].id=i; stu[i].sum=a+b+c; stu[i].yw=a; } sort(stu+1,stu+1+n,cmp); for(int i=1;i<=5;i++) { printf("%d %d\n",stu[i].id,stu[i].sum); } return 0; }用完结构体，思路清晰，一次 AC
-
反思
遇到捆绑问题+排序问题的时候，使用结构体处理数据
两组数据的时候，可以使用双重数组，里面有排序的话 ，拒绝数组
4.求阶乘
-
题目
链接： 蓝桥杯2022年第十三届省赛真题-求阶乘 - C语言网 (dotcpp.com)
题目描述
满足 N! 的末尾恰好有 K 个 0 的最小的 N 是多少?
如果这样的 N 不存在输出 −1。
输入格式
一个整数 K。
输出格式
一个整数代表答案。
样例输入
2样例输出
10提示
对于 30% 的数据，1 ≤ K ≤ 1 0 6 10^6 106 .
对于 100% 的数据，1 ≤ K ≤$ 10^{18} $.
-
第一次——过了一个数据
#include<bits/stdc++.h> using namespace std; int k; int fac(int t) { int res=1; for(int i=1;i<=t;i++) res*=i; return res; } bool check(int x) { int cnt=0; while(x!=0) { if(x%10!=0) return false; if(x%10==0) cnt++; if (cnt==k) return true; x/=10; } return false; } int main() { scanf("%d",&k); for(int i=1;i<100000000;i++) { int t=fac(i); if(check(t)) { cout<<i<<endl; return 0; } } return 0; }我想暴力枚举，把比较小的数据范围过了，但是就过了一个，我猜应该是样例，其他的都是TLE
还有就是数据很大，一律不用使用 int ，省的后期还得改 -
第二次
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL q(LL x) { LL res=0; while(x>0) { res+=x/5; x/=5; } return res; } int main() { LL k; scanf("%lld",&k); //利用 阶乘里面质因子5的个数，来确定前导0； //因为 数据范围是 10^18，枚举肯定不行，所以想到查找二分 //在 1~long long 数据范围上界之间，查找 x,它质因子5 的个数>=k //如果这个数的 质因子5的个数是k，输出即可，否则就是不存在，输出-1 LL l=1,r= 0x7fffffffffffffffL-5; //-5怕超范围 while(l<r) { LL mid=l+r>>2; if(q(mid)<k) l=mid+1; else r=mid; } cout<<q(l)<<endl; if(q(l)==k) printf("%lld",q(l)); else puts("-1"); return 0; }没有输出，还再进一步探索中
-
正确题解
#include <iostream> #define ll long long using namespace std; ll query(ll n) { ll ret = 0; while (n > 0) { ret += n / 5; n /= 5; } return ret; } int main() { ll k; cin >> k; ll l = 1, r = 0x7fffffffffffffffL; // long long的最大 while (l < r) { ll mid = l + (r - l >> 1); if (query(mid) < k) l = mid + 1; else r = mid; } ll ret = query(l); if (ret == k) cout << l; else cout << -1; return 0; }
