二（A了）

思路

差分数组

代码

#include<iostream>
#include <vector>

using namespace std;
const int MAX = 100000;

int main() {
    int n, h, l, r, cnt = 0, end = 0;
    cin >> n >> h;
    vector<int> df(MAX, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> l >> r;
        df[l]++;
        df[r]--;
        end = max(end, r);
    }
    for (int i = 1; i < end; ++i) {
        df[i] += df[i - 1];
        cnt += df[i] >= h;
    }
    cout << cnt;
    return 0;
}

三（没来得及提交，不知道思路对不对）

思路

计算每个周期子串0~p位置上26个字母出现的次数。依题意可知周期子串也是回文串，所以再用双指针l、r从计数数组两端往中心走，确保每次选择使得所有周期子串在位置l和r上的改动次数最少

代码

#include<iostream>
#include <vector>

using namespace std;

int main() {
    int t, n, p;
    string str;
    cin >> t;
    while (t--) {
        cin >> n >> p;
        cin >> str;
        int ans = 0;
        vector<vector<int>> cnt(p, vector<int>(26, 0));
        for (int i = 0; i < p; ++i) {
            for (int j = 0; j < n / p; ++j) {
                cnt[i][str[j * p + i] - 'a']++;
            }
        }
        int l = 0, r = p - 1;
        while (l <= r) {
            int ml = 0, mr = 0;
            int cl, cr; // 从中选出要保留的字母
            for (int i = 0; i < 26; ++i) {
                if (cnt[l][i] > ml) {
                    ml = cnt[l][i];
                    cl = i;
                }
                if (cnt[r][i] > mr) {
                    mr = cnt[r][i];
                    cr = i;
                }
            }
            int nl = 0, nr = 0; // 需要改动的次数
            for (int i = 0; i < 26; ++i) {
                if (i != cl) {
                    if (l == r)nl += cnt[l][i];
                    else nl += cnt[l][i] + cnt[r][i];
                }
                if (i != cr) {
                    if (l == r)nr += cnt[l][i];
                    else
                        nr += cnt[l][i] + cnt[r][i];
                }
            }
            ans += min(nl, nr);
            ++l, --r;
        }
        cout << ans << endl;
    }
}