作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

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≤ $10^4$）。

  输出描述

  输出一行，包含一个整数，表示满足条件的数的和。

  示例

  输入

  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;
  }
  

• 反思

  学会 连乘的优化