题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010;
int n, m;
int sum[26][N];
char a[N];

int main()
{
    int T;
    cin >> T;
    memset(sum, 0, sizeof sum);
    for (int C = 1; C <= T; C ++)
    {
        cin >> n >> m;
        cin >> a + 1;
        for (int i = 1; i <= n; i ++)
        {
            char c = a[i];
            for (int j = 0; j < 26; j ++) sum[j][i] = sum[j][i - 1] + (c - 'A' == j);
        }

        int res = 0;
        for (int i = 1; i <= m; i ++)
        {
            int l, r;
            cin >> l >> r;

            bool st = true;
            int odd = 0;
            for (int i = 0; i < 26; i ++)
            {
                int cnt = sum[i][r] - sum[i][l - 1];
                if (cnt % 2 == 1) odd ++;
                if (odd > 1) 
                {
                    st = false;
                    break;
                }
            }
            if (st) res ++;
        }
        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla