蓝桥杯练习题——贡献法（隔板法）

1.孤独的照片

在这里插入图片描述

思路

孤独的区间一定有一头孤独的牛，考虑每头牛对区间的贡献是多少
在这里插入图片描述

#include<iostream>
using namespace std;
const int N = 5e5 + 10;
int n;
string s;

int main(){
    cin>>n>>s;
    long long res = 0;
    for(int i = 0; i < n; i++){
        int l = i - 1, r = i + 1;
        // 向左扩展
        while(l >= 0 && s[l] != s[i]) l--;
        // 向右扩展
        while(r < n && s[r] != s[i]) r++;
        // 更新左右部分
        int L = i - l - 1, R = r - i - 1;
        res += 1ll * L * R;
        if(L >= 1) res += L - 1;
        if(R >= 1) res += R - 1;
    }
    cout<<res;
    return 0;
}

2.子串分值

在这里插入图片描述

思路

考虑每一个字符对答案的贡献
在这里插入图片描述

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int w[26], l[N], r[N];
char s[N];

int main(){
	// 下标从 1 开始
    cin>>(s + 1);
    int n = strlen(s + 1);
    // 统计左边的边界
    for(int i = 0; i < 26; i++) w[i] = 0;
    for(int i = 1; i <= n; i++){
        int t = s[i] - 'a';
        l[i] = w[t];
        w[t] = i;
    }
    
    // 统计右边的边界
    for(int i = 0; i < 26; i++) w[i] = n + 1;
    for(int i = n; i >= 1; i--){
        int t = s[i] - 'a';
        r[i] = w[t];
        w[t] = i;
    }
    long long res = 0;
    for(int i = 1; i <= n; i++) res += 1ll * (i - l[i]) * (r[i] - i);
    cout<<res;
    return 0;
}