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