2022.3.21 贝壳笔试

#include <bits/stdc++.h>
using namespace std;
int pre[26][4000];
int dp[4000];
char s[4000];

int get(int l,int r,int c){
    if(!l)
        return pre[c][r];
    return pre[c][r]-pre[c][l-1];
}

int main() {
    int n;
    scanf("%d",&n);
    scanf("%s",s);
   
    pre[s[0]-'a'][0]=1;
    for(int i=1;i<n;i++){
        for(int j=0;j<26;j++){
            int d=(s[i]-'a')==j?1:0;
            pre[j][i]=pre[j][i-1]+d;
        }
    }
    dp[0]=-1;
    for(int i=1;i<n;i++){
        int v=0;
        for(int c=0;c<26;c++){
            if(!get(0,i,c))
                continue;
            if(get(0,i,c)&1)
                v-=1;
            else
                v+=1;
        }
        dp[i]=v;
        for(int j=0;j<i;j++){
            int v=0;
            for(int c=0;c<26;c++){
                if(!get(j+1,i,c))
                    continue;
                if(get(j+1,i,c)&1)
                    v-=1;
                else
                    v+=1;
            }
            dp[i]=max(dp[i],dp[j]+v);
        }
    }
    printf("%d\n", dp[n-1]);
    return 0;
}

t=eval(input())
pre=[0]*1000001
idx=1
while idx<=1000000:
    cnt=0
    temp=idx
    while temp:
        cnt+=temp%10
        temp//=10
    d=1 if idx%cnt==1 else 0
    pre[idx]=pre[idx-1]+d
    idx+=1
for i in range(t):
    l,r=map(eval,input().split())
    print(pre[r]-pre[l-1])