A

#include <bits/stdc++.h>
using namespace std;

int n, q, a[300010], s[300010];

int main() {
    cin >> n >> q;
    string str; cin >> str;

    for (int i = 0; i < n - 1; i++) {
        if (str[i] == str[i + 1]) {
            a[i + 1] = 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }

    while (q--) {
        int l, r; cin >> l >> r;
        cout << s[r - 1] - s[l - 1] << endl;
    }

    return 0;
}

B

#include <bits/stdc++.h>
using namespace std;

int ans[26];

int main() {
    int n; cin >> n;
    string s; cin >> s;

    int i = 0;
    while (i < n) {
        int j = i + 1;
        while (j < n && s[j] == s[i]) j++;
        int c = s[i] - 'a';
        ans[c] = max(ans[c], j - i);

        i = j;
    }

    int res = 0;
    for (int i = 0; i < 26; i++) res += ans[i];
    cout << res << endl;

    return 0;
}

C

##include <bits/stdc++.h>
using namespace std;

int n, a[300010];
string s;

// cl[i][j] 前 i 个字符中 a 数组值为 j 的 'M' 的数量
// cr[i][j] 后 i 个字符中 a 数组值为 j 的 'X' 的数量
int cl[300010][5], cr[300010][5];

int mex(int a, int b, int c) {
    for (int i = 0; i < 3; i++) {
        if (i != a && i != b && i != c) return i;
    }
    return 3;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> s;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) cl[i + 1][j] = cl[i][j];
        if (s[i] == 'M') ++cl[i + 1][a[i]];
    }

    for (int i =  n - 1; i >= 0; i--) {
        for (int j = 0; j < 3; j++) cr[i][j] = cr[i + 1][j];
        if (s[i] == 'X') ++cr[i][a[i]];
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'E') {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    ans += (long long)cl[i][j] * cr[i + 1][k] * mex(j, a[i], k);
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}

D

#include <bits/stdc++.h>
using namespace std;

int n, k, s[100010], ans;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        if (s[i] == 0) {
            cout << n << endl;
            return 0;
        }
    }

    int i = 1, j = 0;
    long long t = 1;
    while (i <= n) {
        while (j + 1 <= n && t * s[j + 1] <= k) {
            j++;
            t *= s[j];
        }

        ans = max(ans, j - i + 1);
        
        if (i <= j) t /= s[i];
        i++;
    }

    cout << ans << endl;

    return 0;
}

E

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int h, w, k, s[15][1010], ans = 1e9;
char g[15][1010];
bool flag[15];

int f() {
    int last = 1, cnt = 0;
    for (int i = 1; i <= w; i++) {
        int tot = 0;
        for (int j = 1; j <= h; j++) {
            tot += s[j][i] - s[j][last - 1];
            if (last == i && tot > k) {
                return INF;
            }
            if (tot > k) {
                cnt++;
                last = i;
                tot = 0;
            }
            if (flag[j]) tot = 0;
        }
    }

    return cnt;
}

int main() {
    cin >> h >> w >> k;
    for (int i = 0; i < h; i++) cin >> g[i];

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            s[i + 1][j + 1] = s[i + 1][j] + g[i][j] - '0';
        }
    }

    for (int i = 0; i < 1 << (h - 1); i++) {
        int res = __builtin_popcount(i);

        memset(flag, false, sizeof flag);
        for (int j = 1; j < h; j++) {
            if (i & (1 << (j - 1))) {
                flag[j] = true;
            }
        }

        res += f();

        ans = min(ans, res);
    }

    cout << ans << endl;

    return 0;
}