[每日一题]AcWing4261.孤独的照片

题意

AcWing4261.孤独的照片 - acwing.com

给出一个只包含'H'以及'G'的字符串，认为至少长度为3的子串，且'H'或者'G'有一个是单个的，这代表这张照片是孤独的需要丢弃，求需要丢弃多少张这样的照片。

思路

我写的比较复杂...
首先看单H的情况存在，枚举如果遇到s[i]=='H'则进行计算贡献：

需要找到这样的GGGGHGGG

H(pre)左边的个数是L=pre-l+1个
H(pre)右边边的个数是R=r-pre+1个

那么首先能得到的包含H的子串个数是 $L\times R$ （原因是左侧有 $L$ 个选法,右侧有 $R$ 个选法，根据乘法原理就是 $L\times R$ 种）

那么一定是这样的吗？有特例，因为上述算出的贡献是包括所有子串的，也就是会有HG这样的，也会有H，同样也会有GH这样的情况，所以一定要减去 $1$ （单个H），还需要判断左侧是否有，右侧是否有。

也就是res += (pre-l+1)*(r-pre+1)-1-(pre>l)-(r>pre);

那么对于第一次遇见的H不管，在字符串后面强行加上一个H用来计算最后一次的贡献（因为从上图的i可以看出，每次遇到一个H都是计算前一个H的贡献）

上述是单个H的情况，还有G的情况。

代码

inline int calc(string s, char c)
{
    bool on = false;
    int pre = 0, l = 0, res = 0, n = s.size();
    for (int i=0;i<n;i++)
        if (s[i]==c)
            {
                if (!on) on = true, pre = i;
                else 
                {
                    int r = i-1;
                    int m = r-l+1;
                    if (m>=3)
                        res += (pre-l+1)*(r-pre+1)-1-(pre>l)-(r>pre);
                    l = pre+1;
                    pre = i;
                }
            }
    return res;
}
inline void Case_Test()
{
    string st;
    cin>>n>>st;
    cout<<calc(st+'H', 'H') + calc(st+'G', 'G')<<endl;
}