AcWing 733. 构建回文
原题链接
简单
作者:
别期待太多
,
2024-07-27 12:40:53
,
所有人可见
,
阅读 3
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
char str[N];
int A[26][N];
int main()
{
int T, older = 0;
scanf("%d", &T);
while(T --)
{
int n, q, sum = 0;
scanf("%d %d", &n, &q);
scanf("%s", str + 1); //读入字符数组
for(int i = 0; i < 26; i ++)
for(int j = 1; j <= n; j ++)
{
if(i == str[j] - 'A')//初始化差分数组(0 和 1)
A[i][j] = 1;
else
A[i][j] = 0;
A[i][j] += A[i][j-1]; //初始化前缀和数组
}
while(q --)
{
int l, r, cnt = 0;
bool status = true;
scanf("%d %d", &l, &r);
for(int i = 0; i < 26; i ++)
{
if((A[i][r] - A[i][l-1]) % 2 != 0 && cnt == 0)
cnt ++;
else if((A[i][r] - A[i][l-1]) % 2 != 0 && cnt >= 1)
{
status = false;
break;
}
}
if(status)
sum ++;
}
older++;
printf("Case #");
printf("%d",older);
printf(": %d\n",sum);
}
return 0;
}
嗯,注意最后的输出是英文冒号+空格。。。