题目描述
安娜有N个方块排成一排,每一方块都写着一个大写字母(A-Z中的一个)。这些方块从左到右依次编号为1,2,…,N。现在,她正在学习回文。如果一个字符串不论是从左向右看,还是从右向左看,内容都一样,那么这个字符串就是一个回文字符串。
例如,ANNA,RACECAR,AAA和X都是回文字符串,而AB,FROG和YOYO则不是。鲍勃想要测试一下安娜是否完全理解了回文这一概念,所以向她提出了Q个相关问题。其中的第i个问题是:安娜能否使用从Li号到Ri号(包括端点方块)的所有方块,经过一系列排列使得它们构成一个回文结构?如果可以,则回答“是”,如果不可以,则回答“否”。在每个问题解答完毕之后,安娜都会把方块放回原来的位置。请你帮助安娜求出,这些问题中有多少个问题可以回答“是”。
输入格式
第一行包含整数T,表示共有T组测试数据。
每组数据第一行包含两个整数N和Q,表示方块数量和问题数量。
第二行包含一个长度为N的由大写字母构成的字符串。
接下来Q行,每行包含两个整数Li和Ri,用来描述一个问题。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为“Case #x: y”,其中x是组别编号(从1开始),y是可以回答“是”的问题数量。
数据范围
1≤T≤100,
1≤Li≤Ri≤N,
1≤N,Q≤105
样例
输入:
2
7 5
ABAACCA
3 6
4 4
2 5
6 7
3 7
3 5
XYZ
1 3
1 3
1 3
1 3
1 3
输出:
Case #1: 3
Case #2: 0
算法 前缀和
算法思路:
对于可以变成回文串的区间需要满足的条件:
该区间内每个字母出现的次数最多只能有一个为奇数次。
所以可以预处理出每个字母在字符串中出现的次数。这个时间复杂度是O(26n)
然后对于每个区间,可以用前缀和O(1)求出该字母在区间内出现的次数。
时间复杂度分析:O(n)
C++ 代码
#include<iostream>
using namespace std;
const int maxn = 100010;
char str[maxn];
int s[26][maxn];
int n, m;
int main()
{
int t;
cin >> t;
for(int C = 1; C <= t; C ++)
{
cin >> n >> m;
scanf("%s", str + 1);
for(int i = 1; i <= n; i ++)
for(int j = 0; j < 26; j ++)
if(str[i] == j + 'A') 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", C, res);
}
return 0;
}
强
大佬s数组不清空不会错吗