2022.3.21 贝壳笔试
第一题：这题python3会被卡常，所以转用cpp，怀疑出题人没用其他语言测过。。
#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])第三题：可以字符串hash或者kmp都是O(n^2)复杂度，但实际python3暴力可过，数据过水。。。
#贝壳笔试##笔试题目##贝壳找房##投票#
