蓝桥杯省赛无忧第二章基础算法课件26 前缀和-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯省赛无忧第二章基础算法课件26 前缀和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

蓝桥杯省赛无忧第二章基础算法课件26 前缀和,蓝桥杯省赛无忧,蓝桥杯,算法,c语言,c++,前缀和

01 前缀和原理和特点

蓝桥杯省赛无忧第二章基础算法课件26 前缀和,蓝桥杯省赛无忧,蓝桥杯,算法,c语言,c++,前缀和

02 实现前缀和

蓝桥杯省赛无忧第二章基础算法课件26 前缀和,蓝桥杯省赛无忧,蓝桥杯,算法,c语言,c++,前缀和

03 例题讲解

蓝桥杯省赛无忧第二章基础算法课件26 前缀和,蓝桥杯省赛无忧,蓝桥杯,算法,c语言,c++,前缀和

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll p=1e9+7;
const int N=1e5+9;
ll a[6][N],prefix[6][N];
int main(){  //第一行n、m  第二行n个数据   余下m次l、r、k [l,r]  k倍
     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
     int n,m;cin>>n>>m;
     for(int i=1;i<=n;++i)cin>>a[1][i];
     
     for(int i=2;i<=5;++i)
         for(int j=1;j<=n;++j)
             a[i][j]=a[i-1][j]*a[1][j]%p;   //k倍   
             
              
    for(int i=1;i<=5;++i)
        for(int j=1;j<=n;++j)
            prefix[i][j]=(prefix[i][j-1]+a[i][j])%p;   //基于k倍求前缀和 
            
    
    while(m--){
        int l,r,k;cin>>l>>r>>k; //m次询问 
        cout<<(prefix[k][r]-prefix[k][l-1]+p)%p<<'\n';  
    }                      
   
   return 0;
    
}

蓝桥杯省赛无忧第二章基础算法课件26 前缀和,蓝桥杯省赛无忧,蓝桥杯,算法,c语言,c++,前缀和

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
char str[N];
int prefix[N];
int main()
{
    cin>>str;
    int ans = 0;
    int str_length=strlen(str);
    for(int i=0;i<str_length;i++)
    prefix[i]=prefix[i-1]+(str[i]=='L'?1:-1);
    for(int i=0;i<str_length;i++)
    {
        for(int j=i;j<str_length;j++)
        if(prefix[j]-prefix[i-1]==0)ans=max(ans,j-i+1);
    }
    cout << ans << endl;
}