蓝桥杯刷题冲刺 | 倒计时26天
作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾
文章目录
- 1.路径
- 2.特别数的和
- 3.MP3储存
- 4.求和
1.路径
-
题目
链接： 路径 - 蓝桥云课 (lanqiao.cn)
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。
-
第一次
#include<bits/stdc++.h> using namespace std; const int N=2030; int g[N][N]; int gcd(int a,int b) { return b?gcd(b,a%b):a; } int gcs(int a,int b) { return a*b/gcd(a,b); } int main() { for(int i=1;i<2019;i++) for(int j=i+1;j<=2019;j++) { if(j-i>21) g[i][j]=-1; else g[i][j]=gcs(i,j); } // 只会一个存储，emmm ，这个周末补上 图论 算法 return 0; } -
正确题解
#include<iostream> #include<cstring> //memset()原型 using namespace std; const int N=3000; const int INF=0x3f; //这里可以理解为无穷大 int graph[N][N]; //邻接矩阵存储图 int dist[N]; //记录最短路径值 bool visited[N]; //判断节点是否访问 int gcd(int a,int b){ //最大公约数 return b==0?a:gcd(b,a%b); } int lem(int a,int b){ //最小公倍数 return a*b/gcd(a,b); } int dijkstra(int n){ //初始化 memset(dist,INF,sizeof(dist)); memset(visited,false,sizeof(visited)); dist[1]=0; for(int i=1;i<=n;++i){ int k=-1; for(int j=1;j<=n;++j){ //获取距离源点最近点 if(!visited[j]&&(k==-1||dist[j]<dist[k])){ k=j; } } visited[k]=true; for(int j=1;j<=n;++j){ if(dist[k]+graph[k][j]<dist[j]){ dist[j]=dist[k]+graph[k][j]; } } } if(dist[n]==INF) return -1; return dist[n]; } int main(){ int n=2021; //节点数 //初始化 memset(graph,INF,sizeof(graph)); //构图 for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(abs(i-j)<=21){ graph[i][j]=lem(i,j); } } } //求出最短路径，输出结果 cout<<dijkstra(n)<<endl; return 0; } -
反思
掌握了 新的方法来求解 最大公约数
到后面 ，看题解，有点看不懂了,没有学 图论 ，真是走不动路啊
2.特别数的和
-
题目
链接： 特别数的和 - 蓝桥云课 (lanqiao.cn)
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
输入描述
输入一行包含一个整数n（1≤n≤ 1 0 4 10^4 104）。
输出描述
输出一行，包含一个整数，表示满足条件的数的和。
示例
输入
40输出
574 -
我的题解
#include<bits/stdc++.h> using namespace std; int check(int x) { int t=x; while(t>0) { int k=t%10; if(k==2||k==0||k==1||k==9) return x; t/=10; } return 0; } int main() { int n; cin>>n; int sum=0; for(int i=1;i<=n;i++) { sum+=check(i); } cout<<sum; return 0; } -
反思
希望在 蓝桥杯 可以遇到 这么简单的题 qwq
3.MP3储存
-
题目
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如果一个 MP3 文件占用磁盘的大小是 4MB，小蓝的硬盘还剩下 100GB 的空间，请问他还可以放多少个这样的 MP3 文件？
-
我的题解
#include<bits/stdc++.h> using namespace std; int main() { cout<<1024*100/4; return 0; } -
知识补充
1B(Byte 字节)=8bit，
1KB (Kilobyte 千字节)=1024B，
1MB (Megabyte 兆字节 简称“兆”)=1024KB，
1GB (Gigabyte 吉字节 又称“千兆”)=1024MB，
1TB (Trillionbyte 万亿字节 太字节)=1024GB，其中1024=2^10 ( 2 的10次方) -
反思
补充一下很基础的计算机知识，有点陌生了
4.求和
-
题目
链接： 求和 - 蓝桥云课 (lanqiao.cn)
给定 n 个整数 a*1,a2,⋅⋅⋅,*a n ，求它们两两相乘再相加的和，即：
S=a1⋅a2+a1⋅a3+⋯+a n−2⋅a n−1++ a n−1⋅a n
输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数 a*1,a2,⋯,*a n。
输出格式
输出一个整数 S*，表示所求的和。请使用合适的数据类型进行运算。
样例输入
4 1 3 6 9样例输出
117 -
第一次
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2*1e6+10; int a[N]; int main() { LL sum=0; int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) sum+=a[i]*a[j]; cout<<sum; return 0; }简单暴力，只能过 60%
-
第二次，优化
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2*1e6+10; int a[N]; int main() { LL sum=0,ans=0; int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; } for(int i=0;i<n;i++) { sum-=a[i]; //“a[1]*a[2]"到"a[n]*(a[n-1]+a[n-2]+....+a[1])"求和 ans+=a[i]*sum; //在这里优化：运用乘法分配律 } cout<<ans; return 0; } -
反思
学会 连乘的优化
