ACM-蓝桥杯训练第一周

怼烎@ 2024-04-24 23:20 7阅读 0赞

> 🚀write in front🚀  
> 📝个人主页：[认真写博客的夏目浅石.CSDN][.CSDN]  
> 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝  
> 📣系列专栏：[ACM周训练题目合集.CSDN][ACM_.CSDN]  
> 💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🖊  
> ✉️为什么我们不知疲倦，因为我们都在做自己所热爱的事 ♐

#### 文章目录 ####

*  前言
 *  A - \[例题\]一维前缀和
 *  B - 二分查找
 *  C - 一维差分
 *  D - 快速幂
 *  E - 质数筛
 *  F - 最短路径
 *  G - 结构体排序
 *  H - sort
 *  I - 二维前缀和
 *  总结

--------------------

![在这里插入图片描述][f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]

## 前言 ##

本周进行了一些特别基础的练习来巩固知识，写成博客方便我去复习使用。

--------------------

## A - \[例题\]一维前缀和 ##

![在这里插入图片描述][5624e4412770499496eff3b717ff10f0.png]  
思路：基础的前缀和模板题目，会公式即可。详细可以看我写的博客

#include<iostream>
    #include<cstdio>
    
    using namespace std;
    
    typedef long long ll;
    ll n,q;
    ll sum[100010];
    
    
    
    int main()
    {
        
        cin>>n>>q;
        
        for(int i=1;i<=n;i++)
        {
        
            ll tmp;
            cin>>tmp;
            sum[i]=sum[i-1]+tmp;
        }
        
        while(q--)
        {
        
            ll l,r;
            cin>>l>>r;
            printf("%lld\n",sum[r]-sum[l-1]);
            
        }
        return 0;
    }

## B - 二分查找 ##

![在这里插入图片描述][42536fd1e0804d6ab2b5f73758b450bd.png]  
思路：基础的二分模板题目，详细可以看二分模板那篇博客。

#include<iostream>
    
    using namespace std;
    
    #define N 1000010
    
    int a[N],n,m,q;
    
    int main()
    {
        
        cin>>n>>m;
        for(int i=0;i<n;++i) cin>>a[i];
        
        for(int i=0;i<m;++i)
        {
        
        	cin>>q;
        	int l=0,r=n-1;
        	
        	while(l<r)
        	{
        
        		int mid=(l+r)/2;
        		if(a[mid]>=q) r=mid;
        		else l=mid+1;
    		}
        	if(a[l]!=q) cout <<"-1"<<" ";
        	else cout<<l+1<<" ";	
    	}
        
        return 0;
    }

## C - 一维差分 ##

![在这里插入图片描述][3a3b832d03bf4486bbbfa75b5d87a8fc.png]  
思路：基础差分题目

#include<iostream>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    typedef long long ll;
    ll n,p,a[5000010];
    ll x,y,z,sum,b[5000010],mn=5000010,cnt;
    
    int main()
    {
        
    	cin>>n>>p;
    	
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>a[i];
    	}
    	
    	for(int i=0;i<p;i++)
    	{
        
    		cin>>x>>y>>z;
    		b[x]+=z;
    		b[y+1]-=z;
    	}
    	for(int i=1;i<=n;i++)
    	{
        
    		sum+=b[i];
    		cnt=sum+a[i];
    		mn=min(mn,cnt);
    	}
    	
    	cout<<mn<<endl;
    	return 0;
    }

## D - 快速幂 ##

![在这里插入图片描述][f1d73aa725e04c9c8b5504a87adb8d69.png]  
思路：[快速幂算法（全网最详细地带你从零开始一步一步优化）（转载）][Link 1]

#include<iostream>
    #include<cmath>
    
    using namespace std;
    typedef long long ll;
    
    ll a,b,m;
    
    int main()
    {
        
        cin>>a>>b>>m;
        ll result=1;
        
        while(b)
        {
        
            if(b%2==0)
            {
        
                b/=2;
                a=a*a%m;
            }
            else
            {
        
                b-=1;
                result=result*a%m;
                b/=2;
                a=a*a%m;
            }
        }
        
        cout<<result<<endl;
        return 0;
    }

## E - 质数筛 ##

![在这里插入图片描述][cb7bae2d74084dc09bad47f2335fd25d.png]  
思路：暴力求素数

#include<iostream>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    typedef long long ll;
    
    int n;
    int a[100010];
    
    int main()
    {
        
        cin>>n;
        
        for(int i=0;i<n;i++)
        {
        
            cin>>a[i];
        }
        int j=0;
        for(int i=0;i<n;i++)
        {
        
            for(j=2;j*j<=a[i];j++)
            {
        
                if(a[i]%j==0) break;
            }
            if(j>a[i]/j&&a[i]>=2) cout<<a[i]<<" ";
        }
        
        return 0;
    }

## F - 最短路径 ##

![在这里插入图片描述][22e1e35a680745159b1bbeb2d86e6f76.png]  
思路：最短路的基础模板题目

#include<algorithm>
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    int n,m;
    int u,v,w;
    int g[110][110];
    int path[110][110];
    const int maxx=99999999;
    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]=maxx;
            }
        }
        
        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++)
            {
        
                printf("%d ",g[i][j]);
            }
            cout<<endl;
        }
    
        
        return 0;
    }

## G - 结构体排序 ##

![在这里插入图片描述][cc1f508b27e54f118c8bef0669925a45.png]  
思路：我其实我对于结构体题目不是很熟悉，正好借这一个题目学到很多东西，语法题，重要的在于结构体格式

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    struct Stu 
    {
        
    	int math;
    	int chinese;
    	int english;
    	int sum;
    	int id;
    }stu[350];
    
    int cmp(Stu a,Stu b)
    {
        
    	if (a.sum==b.sum)
    	{
        
    		if (a.chinese==b.chinese)
    			return a.id<b.id;
    		else return a.chinese>b.chinese;
    	}
    	else return a.sum>b.sum;
    }
    
    int main()
    {
        
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>stu[i].chinese>>stu[i].math>>stu[i].english;
    		stu[i].id=i;
    		stu[i].sum=stu[i].chinese+stu[i].math+stu[i].english;
    	}
    	
    	sort(stu+1,stu+n+1,cmp);
    	
    	for(int i=1;i<=5;i++)
    	{
        
    		cout<<stu[i].id<<" "<<stu[i].sum<<endl;
    	}
    	
    	return 0;
    }

## H - sort ##

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

#include<algorithm>
    
    #include<iostream>
    using namespace std;
    
    int main()
    {
        
        int n;
        cin>>n;
        int arr[100010];
        
        for(int i=0;i<n;i++)
        {
        
            cin>>arr[i];
        }
        sort(arr,arr+n);
        
        for(int i=0;i<n;i++) cout<<arr[i]<<" ";
        cout<<endl;
        
        return 0;
    }

## I - 二维前缀和 ##

![在这里插入图片描述][76d5980fbc0a41429e2778a63457cee9.png]  
思路：二维前缀和公式： `g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1]`;

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    
    using namespace std;
    
    int g[1010][1010];
    int T,n,m,x,y;
    
    int main()
    {
        
        cin>>T;
        
        while(T--)
        {
        
            memset(g,0,sizeof(g));
            
            int res=0;
            cin>>n>>m>>x>>y;
            
            for(int i=1;i<=n;i++)
            {
        
                for(int j=1;j<=m;j++)
                {
        
                    cin>>g[i][j];
                    
                    g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
                    if(i>=x&&j>=y)
                    {
        
                        res=max(g[i][j]-g[i-x][j]-g[i][j-y]+g[i-x][j-y],res);
                    }
                }
            }
            cout<<res<<endl;
        }
        
        return 0;
    }

--------------------

## 总结 ##

本周复习了基础的模板题目，重在查漏补缺。  
复习：前缀和，二维前缀和，差分，二分查找，sort排序，质数筛，结构体排序  
学习：最短路问题，快速幂  
我需要加强学习的：二维前缀和，结构体排序，质数筛的埃式筛选法。

[.CSDN]: https://blog.csdn.net/congfen214?type=blog
[ACM_.CSDN]: https://blog.csdn.net/congfen214/category_12101464.html?spm=1001.2014.3001.5482
[f4e0159841ab450d861dde9e8fb5ba0d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/c91e4add38c74b2492536bd3e39cdac9.gif
[5624e4412770499496eff3b717ff10f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/dc2c6af9c0914403a8aca710023c47be.png
[42536fd1e0804d6ab2b5f73758b450bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/022dc6bbe98f486ab6c1a12eff1287bf.png
[3a3b832d03bf4486bbbfa75b5d87a8fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/10479f5dba374fac9de358f018d56b61.png
[f1d73aa725e04c9c8b5504a87adb8d69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/081fd14c112d4e8884f9b9fee66a75ee.png
[Link 1]: https://blog.csdn.net/qq_19782019/article/details/85621386
[cb7bae2d74084dc09bad47f2335fd25d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/da45b031005e4570a164fbc1f65acf24.png
[22e1e35a680745159b1bbeb2d86e6f76.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/0cd5431312274df7b40bc03f58e1b855.png
[cc1f508b27e54f118c8bef0669925a45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/ab7c3d7c53514b628d72607e8e1beb84.png
[e98e70c630124750a3ee0b401f0e3660.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/50d8f881cd5b46e6be2fbc09a8f82bbb.png
[76d5980fbc0a41429e2778a63457cee9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/8d9114820350470e8ff3fcbf59efd400.png