B. 攻防演练 题解(思维+倍增)

题目链接

题目思路

对于(l-1)找到它(m)个字母最接近的位置的最远位置

然后进行倍增即可

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int m,n,q;
int nxt[maxn][35];
char s[maxn];
int dp[maxn][35];
signed main(){
    scanf("%d%d",&m,&n);
    scanf("%s",s+1);
    for(int i=1;i<=m;i++){
        nxt[n+1][i]=n+1;
    }
    for(int i=0;i<=30;i++){
        dp[n+1][i]=n+1;
    }
    for(int i=n;i>=0;i--){
        for(int j=1;j<=m;j++){
            nxt[i][j]=nxt[i+1][j];
        }
        for(int j=1;j<=m;j++){
            dp[i][0]=max(dp[i][0],nxt[i][j]);
        }
        if(i==0) continue;
        nxt[i][s[i]-'a'+1]=i;
    }
    for(int j=1;j<=30;j++){
        for(int i=0;i<=n;i++){
            dp[i][j]=dp[dp[i][j-1]][j-1];
        }
    }
    scanf("%d",&q);
    for(int i=1,l,r;i<=q;i++){
        scanf("%d%d",&l,&r);
        int now=l-1,ans=1;
        for(int i=30;i>=0;i--){
            if(dp[now][i]&&dp[now][i]<=r){
                ans+=(1<<i);
                now=dp[now][i];
            }
        }
        printf("%d
",ans);
    }
    return 0;
}