AcWing 733. 构建回文
原题链接
简单
作者:
刘帅哥
,
2023-07-16 15:48:55
,
所有人可见
,
阅读 193
//733
//结构
#include <bits/stdc++.h>
using namespace std;
int n,m;
char str[100010];
int s[26][100010];
int main(){
int a;
cin >> a;
for(int q = 1; q <= a;q++)
{
cin >> n >> m;
scanf("%s",str + 1);
for (int i = 1; i <=n ; i++)
for (int j = 0; j < 26;j++)
if(str[i] == 'A' + j)
s[j][i] = s[j][i-1] + 1;
else s[j][i] = s[j][i-1];
int res = 0;
while(m--)
{
int l , r;
cin >> l >> r;
int cnt = 0;
for(int i = 0 ; i < 26;i++)
{
int sum = s[i][r] - s[i][l-1];
if (sum % 2 == 1) cnt++;
}
if(cnt <= 1) res++;
}
printf("Case #%d: %d\n",q,res);
}
return 0;
}