【ACM】—蓝桥杯大一暑期集训Day4

古城微笑少年丶 2024-04-17 10:12 67阅读 0赞

> ?欢迎来到本文?  
> ?个人简介：[陈童学哦][Link 1]，目前学习C/C++、算法、Python、Java等方向，一个正在慢慢前行的普通人。  
> ?系列专栏：[陈童学的日记][Link 2]  
> ?其他专栏：[C++STL][C_STL]，感兴趣的小伙伴可以看看。  
> ?希望各位→点赞? + 收藏⭐️ + 留言?  
> ⛱️学习应使你快乐！望与诸君共勉！

![在这里插入图片描述][35ce84ce0aa84c02907c38d771b998e1.png]

#### Day4集训 ####

*  A - 医院设置
 *   *  解题思路
     *  示例代码
 *  B - Destroyer
 *   *  解题思路
     *  示例代码
 *  C - 单源最短路径（弱化版）
 *   *  解题思路
     *  示例代码
 *  D - 某最短路
 *   *  解题思路
     *  示例代码
 *  E - Sasha and Array Coloring
 *   *  解题思路
     *  示例代码
 *  总结

## A - 医院设置 ##

**来源：**[洛谷P1364 医院设置][P1364]  
算法标签：`动态规划,dp、树形数据结构、广度优先搜索,BFS、最短路`  
![在这里插入图片描述][b0fccf1c8a3040be8d631dc84534db69.png]  
![在这里插入图片描述][74f73fae1f5e4743ba82f97424e19b5c.png]

### 解题思路 ###

这题是一道最短路问题，先用邻接矩阵建一棵树，然后用Floyd（弗洛伊德）算法求任意两点间的最短路，然后再遍历所有节点看看在哪个节点距离和最小

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int a[105],g[105][105]; 
    int main()
    {
        
    	int n,l,r,minn,sum;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=1;j<=n;j++)
    			g[i][j]=0x3f3f3f3f;
    	}
    	for(int i=1;i<=n;i++)
    	{
        
    		g[i][i]=0;
    		cin>>a[i]>>l>>r;
    		if(l>0)
    			g[i][l]=g[l][i]=1;
    		if(r>0)
    			g[i][r]=g[r][i]=1;
    	}
    	//Floyd求最短路
    	for(int k=1;k<=n;k++)
    	{
        
    		for(int i=1;i<=n;i++)
    		{
        
    			if(i!=k)
    			{
        
    				for(int j=1;j<=n;j++)
    				{
        
    					if(i!=j&&k!=j&&g[i][k]+g[k][j]<g[i][j])
    						g[i][j]=g[i][k]+g[k][j];
    				}
    			}
    		}
    	}
    	minn=0x7fffffff;
    	for(int i=1;i<=n;i++)
    	{
        
    		sum=0;
    		for(int j=1;j<=n;j++)
    			sum+=g[i][j]*a[j];
    		if(sum<minn)
    			minn=sum;
    	}
    	cout<<minn;
    }

## B - Destroyer ##

**来源：**[Codeforces A. Destroyer][]  
![在这里插入图片描述][97dedd5202cf4955beb37bedf681512a.png]  
![在这里插入图片描述][2b221a43f60c46a0b7b422848ef4d6c4.png]  
![在这里插入图片描述][1be433fc80424d95a757a3d223fa810a.png]

### 解题思路 ###

统计每个数出现的次数，只需满足a\[i\]<=a\[i-1\]即可

### 示例代码 ###

#include <bits/stdc++.h>
    using namespace std;
    void solve() 
    {
        
    	int n,num; 
    	cin>>n;
    	int a[105]={
        0};
    	//memset(a,0,sizeof a);
    	for(int i = 1 ; i <=n  ; i++)
    	{
        
    		cin>>num;
    		a[num]++;
    	}
    	int judge = 1;
    	for(int i=1;i<105;i++)
    	{
        
    		if(a[i] > a[i-1])
    		{
        
    			judge = 0;
    			break;
    		}
    			
    	}
    	if(judge)
    		cout<<"YES\n";
    	else
    		cout<<"NO\n";
    }            
    int main() 
    {
        
        int t;
    	cin>>t;
        while(t--)
        {
        
        	solve();
        }
        return 0;
    }

## C - 单源最短路径（弱化版） ##

**来源：**[洛谷P3371 【模板】单源最短路径（弱化版）][P3371]  
算法标签：`图论、最短路、O2优化`  
![在这里插入图片描述][6c765c82e7db4e51b23a52b0a3e4e7d6.png]  
![在这里插入图片描述][b04b4a849bb343a18978e3716450ed92.png]

### 解题思路 ###

这题的数据用邻接矩阵的话好像过不了，我不会做（手动流泪），我看有大佬们有用`Floyd优化的、Dijkstra+堆优化、SPFA优化`等，我这里参考了一位用`链式向前星储存图+Dijkstra`的大佬的代码。真难啊家人们。

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1000010;
    int head[N],cnt;
    ll ans[N];
    bool visit[N];
    int n,m,s;
    struct node
    {
        
    	int to;
    	int nextt;
    	int wei;
    }edge[N];
    void addedge(int x,int y,int z)
    {
        
    	edge[++cnt].to=y;
    	edge[cnt].wei=z;
    	edge[cnt].nextt=head[x];
    	head[x]=cnt;
    }
    int main()
    {
        
    	cin>>m>>n>>s;
    	for(int i=1;i<=n;i++)
    		ans[i]=2147483647;
    	ans[s]=0;
    	int a,b,c;
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>a>>b>>c;
    		addedge(a,b,c);
    	}
    	int position=s;
    	while(visit[position]==0)
    	{
        
    		ll minn =2147483647;
    		visit[position]=1;
    		for(int i=head[position];i!=0;i=edge[i].nextt)
    		{
        
    			if(!visit[edge[i].to]&&ans[edge[i].to]>ans[position]+edge[i].wei)
    				ans[edge[i].to]=ans[position]+edge[i].wei;
    		}
    		for(int i=1;i<=m;i++)
    		{
        
    			if(ans[i]<minn&&visit[i]==0)
    			{
        
    				minn=ans[i];
    				position=i;
    			}
    		}
    	}
    	for(int i=1;i<=m;i++)
    		cout<<ans[i]<<" ";
    }

## D - 某最短路 ##

**来源：**[洛谷B3647 【模板】Floyd 算法][B3647 _Floyd]  
算法标签：`最短路`

![在这里插入图片描述][53ec3f389b854d2993ea42eef996729b.png]

### 解题思路 ###

要求任意两点之间的距离，数据也不是很大，这题用Floyd跑一遍就OK了

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int n,m;
    int u,v,w;
    int g[105][105];
    int main()
    {
        
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    		{
        
    			if(i==j)
    				g[i][j]=0;
    			else
    				g[i][j]=1e9;
    		}
    			
    	for(int i=1;i<=m;i++)
    	{
        
    		cin>>u>>v>>w;
    		g[u][v]=g[v][u]=w;
    	}
    	for(int k=1;k<=n;k++)
    	{
        
    		for(int i=1;i<=n;i++)
    		{
        
    			for(int j=1;j<=n;j++)
    			{
        
    				if(g[i][j]>g[i][k]+g[k][j])
    					g[i][j]=g[i][k]+g[k][j];
    			}
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=1;j<=n;j++)
    			cout<<g[i][j]<<" ";
    		cout<<endl;
    	}
    }

## E - Sasha and Array Coloring ##

**来源：**[CodeforcesA. Sasha and Array Coloring][]  
![在这里插入图片描述][2b4d309e80d041aba2c669428244fd34.png]  
![在这里插入图片描述][438cb1e8fa034283adf5afa44852bf22.png]  
![在这里插入图片描述][56d2fdfec2564439962f247e53655608.png]

### 解题思路 ###

这题模拟一下，要得到最大值，采用贪心策略，先对数组进行排序，然后每次用末尾数减去首位数，全部相加即可求解

### 示例代码 ###

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
    	int t;	
    	cin>>t;
    	while(t--)
    	{
        
    		int n;
    		cin>>n;
    		int a[105],sum=0;
    		for(int i=0;i<n;i++)
    			cin>>a[i];
    		sort(a,a+n);
    		int i=0,j=n-1;
    		while(i<j)
    		{
        
    			sum+=a[j]-a[i];
    			i++;
    			j--;
    		}
    		cout<<sum<<endl;
    	}
    }

## 总结 ##

Day4的题主要考察最短路径、图论问题，这类题较难。  
算法：`贪心、Floyd、Dijkstra、SPFA、DFS、BFS、dp`  
感悟：图论最短路的题比较难，有时难得我头炸裂（哭脸）  
总结：对于求最短路的各类算法还不是太熟练，还需多加练习加以掌握

[Link 1]: https://blog.csdn.net/H1727548?type=blog
[Link 2]: https://blog.csdn.net/h1727548/category_12342877.html?spm=1001.2014.3001.5482
[C_STL]: https://blog.csdn.net/h1727548/category_12319887.html?spm=1001.2014.3001.5482
[35ce84ce0aa84c02907c38d771b998e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/c2f15cac20334a04a41489a85684c8a7.png
[P1364]: https://www.luogu.com.cn/problem/P1364
[b0fccf1c8a3040be8d631dc84534db69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/68a312ece72b4577ad20adf37fc0496d.png
[74f73fae1f5e4743ba82f97424e19b5c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/33bdf49be2d2461dbdcf799e2227b67c.png
[Codeforces A. Destroyer]: https://codeforces.com/contest/1836/problem/A
[97dedd5202cf4955beb37bedf681512a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/4bb280ab661a4ab7baa41552f971a752.png
[2b221a43f60c46a0b7b422848ef4d6c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/e76afc29cb714748ba90c79cb1478870.png
[1be433fc80424d95a757a3d223fa810a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/6024c0f141c54c649313daa7c08fc604.png
[P3371]: https://www.luogu.com.cn/problem/P3371
[6c765c82e7db4e51b23a52b0a3e4e7d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/ef20637535ba453297c11616e1edb93e.png
[b04b4a849bb343a18978e3716450ed92.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/af4ef2d0787b4e5fb8eef1bebf649c9e.png
[B3647 _Floyd]: https://www.luogu.com.cn/problem/B3647
[53ec3f389b854d2993ea42eef996729b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/f8207a6f229647f8a3207819bc2f6ff0.png
[CodeforcesA. Sasha and Array Coloring]: https://codeforces.com/problemset/problem/1843/A
[2b4d309e80d041aba2c669428244fd34.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/11f2d92ce83b4d62a28b2e0aee3329ff.png
[438cb1e8fa034283adf5afa44852bf22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/40f36d0cac9443d3bad30efd32f421f5.png
[56d2fdfec2564439962f247e53655608.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/33940e4849f1437c800b77891c48d92e.png