CodeForces 451D Count Good Substrings：壓縮回文串計數

CodeForces 451D Count Good Substrings：壓縮回文子串計數

題目大意：給定只含 'a'、'b' 的字符串，將相鄰相同字符壓縮為一個（如 "aaabba" → "aba"）。若壓縮後的子串為回文，則稱原子串為「好子串」。統計好子串中長度為偶數與奇數的個數。

核心洞察

壓縮後字符串必為交替序列（如 "ababab..."）。對於交替序列，只要首尾字符相同，整個串必為回文。因此，以位置 i 為左端點的好子串個數，等於其右側相同字符的個數。
長度奇偶性判斷：若 i 與匹配位置 j 同奇偶（均為奇數下標或均為偶數下標），則原子串長度為奇數；否則為偶數。

算法流程

1. 預處理：從右向左掃描，維護 sum[c][parity][i] 表示位置 i 右側（含 i+1）字符 c 在奇/偶位置的個數。
2. 遍歷每個位置 i：
   奇數長度貢獻 += sum[ch[i]][i%2][i]
   偶數長度貢獻 += sum[ch[i]][(i%2)^1][i]
3. 單字符子串（長度 1）均為好子串，初始奇數計數 = n。

核心代碼

const int N = 100010;
char str[N];
int ch[N];
int sum[2][2][N]; // sum[char][parity][i]
long long ans[2]; // ans[0]:偶數, ans[1]:奇數

int main() {
    while (scanf("%s", str) == 1) {
        int len = strlen(str);
        for (int i = 0; i < len; i++) ch[i] = str[i] - 'a';
        memset(sum, 0, sizeof(sum));
        ans[0] = 0; ans[1] = len; // 長度1的子串全是奇數好子串
        for (int i = len - 2; i >= 0; i--) {
            sum[0][0][i] = sum[0][0][i+1];
            sum[0][1][i] = sum[0][1][i+1];
            sum[1][0][i] = sum[1][0][i+1];
            sum[1][1][i] = sum[1][1][i+1];
            sum[ch[i+1]][(i+1)%2][i]++;
        }
        for (int i = 0; i < len; i++) {
            int p = i % 2;
            ans[1] += sum[ch[i]][p][i];
            ans[0] += sum[ch[i]][p^1][i];
        }
        printf("%lld %lld\n", ans[0], ans[1]);
    }
    return 0;
}

複雜度

• 時間 O(n)，空間 O(n)，n ≤ 100,000，極快。