P7993解题报告

· · 题解

这题窝想了 2h 才出正解

大致思路是这样的：扫描每一头牛，计算出这头牛是“孤独的”的照片有多少张，加到 ans 里头去。最后输出 ans。有人担心这种方法会重复计算，实际上是不会的。因为每张照片都只会有唯一的一只牛是“孤独的”，也就是说这张照片只会被这只“孤独的”牛计算一遍。

那么重点来了，怎么算呢？？

我们可以再计算前先处理四个数组：LG[],RG[],LH[],RH[]。这四个数组的第 i 位分别表示：第 i 头牛左边有几头连续的更赛牛，第 i 头牛右边有几头连续的更赛牛，第 i 头牛左边有几头连续的荷斯坦牛，第 i 头牛右边有几头连续的荷斯坦牛。在计算答案时，对于每头牛（假设这头牛是更赛牛，荷斯坦牛类似），考虑以下两种情况：

  1. 这头牛是在照片里的最左边或最右边。这种情况可以加上 LH[i]?LH[i-1]:0+RH[i]?RH[i+1]:0（-1 或 +1 是为了避免 len==2 的情况），画图如下：

  1. 这头牛实在照片里的中间。这种情况可以加上 LH[i]*RH[i]，画图如下：

将这两个加起来就行了。

AC Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=500001;
int n,l=1,r=1,ans,LG[N],RG[N],LH[N],RH[N];
string s;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> s;s=" "+s;
    for(int i=2;i<=n;i++)
        LG[i]=s[i-1]=='G'?LG[i-1]+1:0;
    for(int i=n-1;i>=1;i--)
        RG[i]=s[i+1]=='G'?RG[i+1]+1:0;
    for(int i=2;i<=n;i++)
        LH[i]=s[i-1]=='H'?LH[i-1]+1:0;
    for(int i=n-1;i>=1;i--)
        RH[i]=s[i+1]=='H'?RH[i+1]+1:0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='H')
        {
            if(LG[i])ans+=LG[i-1];
            if(RG[i])ans+=RG[i+1];
            ans+=LG[i]*RG[i];
        }
        else
        {
            if(LH[i])ans+=LH[i-1];
            if(RH[i])ans+=RH[i+1];
            ans+=LH[i]*RH[i];
        }
//      cout << ans << endl;
    }
    cout << ans << endl;
    return 0;
}