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

01 前缀和原理和特点

02 实现前缀和

03 例题讲解

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

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