孤独的照片_(贡献法）

原题链接：4261. 孤独的照片 - AcWing题库

题意：有两种元素，要找到每三及以上的连续元素中，其中一种元素只有一个的 元素组合个数

思路

贡献法

思想方法

思维

主要在于转换思维

当发现要求解问题太过复杂，直接正向的思路行不通，可以将思路转换一下，看看关键的分界点，或是每个要素对于求解整个问题有什么贡献。

即从要素来看，问题要怎么求解，每个要素组成了问题的哪一部分

Link to original

对于这个问题来说：

原本是枚举每个区间来看这个区间是否符合要求 发现时间复杂度太高

从贡献法的角度出发，可以转换思路为： 每头孤独的牛对这样的区间有什么贡献？

即每头牛可以组成多少个这样的区间？

发现对于孤独的牛而言，其左边若是有，右边也有，那就是可以任意划分，有$L\times R$ 的区间 若是只有一边，由于要三只以上 ，则有 $L-1$ 个区间

实现

屎一样的实现：

#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
typedef long long LL;
 
const int N = 5e5 + 10;
 
int niu[N];
LL c[2];
 
int main()
{
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    for(int i = 1; i <= n; i ++)
    {
        //处理01串
        niu[i] = s[i-1] - 'G';
    }
    
    LL ans = 0;
    //int cnt = 0;
    int flag = 0;
    for(int i = 1; i <= n; i ++)
    {
        //c[0] = c[1];
        //如果是第一次枚举左边
        if(flag == 0)
        {
            flag = 1;
            while(niu[i] && i <= n)
            {
                c[0] ++;
                i ++;
            }
         
            //如果一直枚举到出界
            if(i > n && c[0] > 0)
            {
                ans = 0;
                continue;
            }
            i ++;
        }
        else c[0] = c[1];
        
        c[1] = 0;
        //cout << niu[i] << endl;
        //枚举右边
        while(niu[i]&& i <= n)
        {
            c[1] ++;
            i ++;
        }
        
        //cout << c[0] << c[1] << endl;
        
        if(c[0] > 0 && c[1] > 0)
        {
            ans += c[0] * c[1];
            ans += max((LL)0, c[0] - 1);
            ans += max((LL)0, c[1] - 1);
        }
        else ans += max((LL)0, c[0] + c[1] - 1);
    }
	//处理另一类牛
    flag = 0; c[0] = c[1] = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(flag == 0)
        {
            flag = 1;
            while(!niu[i]&& i <= n)
            {
                c[0] ++;
                i ++;
            }
           // cout << c[0] << i << endl;
            if(i > n && c[0] > 0)
            {
                ans = 0;
                continue;
            }
            i ++;
        }
        else c[0] = c[1];
        
        c[1] = 0;
        
        while(!niu[i]&& i <= n)
        {
            c[1] ++;
            i ++;
        }
        
        //cout << c[0] << c[1] << endl;
        if(c[0] > 0 && c[1] > 0)
        {
            ans += c[0] * c[1];
            ans += max((LL)0, c[0] - 1);
            ans += max((LL)0, c[1] - 1);
        }
        else ans += max((LL)0, c[0] + c[1] - 1);
    }
    //cout << c[0] << c[1] << endl;
    
    cout << ans << endl;
    
    return 0;
}

实现上其实要求抽象思维的提高，可以一边累计一边遍历

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 5e5 + 10;
 
typedef long long LL;
 
LL l[N], r[N];
 
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    //这样就记录下了第i个的左边与右边分别有多少
    for(int i = 0, sg = 0, sh = 0; i < n; i ++)
        //如果是G，H就断掉，不再计数
        if(s[i] == 'G') sg ++, l[i] = sh, sh = 0;
        else sh ++, l[i] = sg, sg = 0;
    
    
    for(int i = n - 1, sg = 0, sh = 0; i >= 0; i --)
        if(s[i] == 'G') sg ++, r[i] = sh, sh = 0;
        else sh ++, r[i] = sg, sg = 0;
    
    LL ans = 0;
    for(int i = 0; i < n; i ++)
        ans += l[i] * r[i] + max((LL)0, l[i] - 1) + max(r[i] - 1, (LL)0);
        
    cout << ans << endl;
    
    return 0;
}