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

---

前言

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

---

A - [例题]一维前缀和

思路：基础的前缀和模板题目，会公式即可。详细可以看我写的博客

#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 - 二分查找

思路：基础的二分模板题目，详细可以看二分模板那篇博客。

#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 - 一维差分

思路：基础差分题目

#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 - 快速幂

思路：快速幂算法（全网最详细地带你从零开始一步一步优化）（转载）

#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 - 质数筛

思路：暴力求素数

#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 - 最短路径

思路：最短路的基础模板题目

#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 - 结构体排序

思路：我其实我对于结构体题目不是很熟悉，正好借这一个题目学到很多东西，语法题，重要的在于结构体格式

#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

#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 - 二维前缀和

思路：二维前缀和公式： 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排序，质数筛，结构体排序
学习：最短路问题，快速幂
我需要加强学习的：二维前缀和，结构体排序，质数筛的埃式筛选法。