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$ ，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
```
分析

$10^9$ 的输入可以被 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(); //去掉前导0for(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 ≤ $10^6$ .

对于 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，输出即可，否则就是不存在，输出-1LL 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;
}