USACO历年青铜组真题解析 | 2021年12月Lonely Photo

【题目描述】

Farmer John 最近购入了 N 头新的奶牛（3≤N≤5×10^5），每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。 在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。

给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。如果两张照片以不同的奶牛开始或结束，则认为它们是不同的。

【输入】

输入的第一行包含 N。

输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛，则字符串的第 i 个字符为 G。否则，第 i 头奶牛是荷斯坦牛，该字符为 H。

【输出】

输出 Farmer John 会扔掉的孤独的照片数量。

【输入样例】

5
GHGHG

【输出样例】

3

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, cntg=0, cnth=0;
int g[500005]={0}, h[500005]={0}, cntg1[500005]={0}, cnth1[500005]={0};
long long ans=0;
int main()
{
    cin >> n;  // 输入n
    for (int i=1; i<=n; i++) {  // for循环遍历n个字符
        char tmp;
        cin >> tmp;
        if (tmp=='G') cntg++;  // 如果输入为G，cntg自增1
        else cnth++;  // 如果输入为H，cnth自增1
        g[i] = cntg, h[i] = cnth;  // g和h数组为前缀和数组，记录第i位置时G和H的总数
    }
    // for (int i=0; i<=n; i++) {  // 保留二维前缀和计算过程
    //     for (int j=i+3; j<=n; j++) {
    //         if (g[j]-g[i]==1 || h[j]-h[i]==1) {
    //             // cout << "g " << g[j]-g[i] << endl;
    //             // cout << "h " << h[j]-h[i] << endl;
    //             ans++;
    //         }
    //     }
    // }
    for (int i=0; i<=n; i++) {  //前缀和优化为模板（从O(n²)降至O(n)，尝试记忆！！！）
        cntg1[g[i]]++;  // cntg1和cnth1，下标为前缀和，值为该前缀的个数
        cnth1[h[i]]++;
        if (g[i+3]>=1) ans += cntg1[g[i+3]-1];  // 更新cntg1和cnth1之后，计算ans。对于i+3的位置，如果前缀和大于等于1，则统计前缀和-1之后的值（作为cntg1或cnth1的下标），在cntg1或cnth1中的个数，加到ans中
        if (h[i+3]>=1) ans += cnth1[h[i+3]-1];  // 同上
    }
    cout << ans << endl;  // 打印结果
    return 0;
}

【运行结果】

5
GHGHG
3