3、18 贡献法学习

贡献法
计算每一个字符对答案的贡献，然后进行地推求解即可；

题目：

https://www.acwing.com/problem/content/5157/

计算贡献

1、当[变化]的对象存在两个时 尝试[固定]一者
可以发现 对于ρ(“TCG”,”GCA”)而言 三轮操作中的每轮操作是等价的 每轮(第一层循环左移)对结果的贡献是一致的 因此只需要考虑一轮即可
即可以固定s 而只看t的变化

2、当不易思考整体变化时 对[单体]采用[贡献法]思考
可以发现对于t中的每个元素 在左移0 ~ n - 1的全局操作中 其实就是和s中的每一个字符匹配一次
因此若t中的某个字符为’A’ 那么其对结果的贡献即为s中含有的’A’的数量
因此为了使得结果最大 t中的元素因尽可能为s中个数最多的元素
————————————————————————————————————————————————————————————————————————————————————————————————
思路

3、问题即转换为 找到s中个数最多的元素 让t中的每个元素都赋值为该元素即可

当s中最多的元素个数为1个时 只能将所有t中的元素都赋值为该元素 答案为1^n
当s中最多的元素个数为2个时 t中的每个元素都有两种选择 任选其一均可 答案为2^n
当s中最多的元素个数为3个时 t中的每个元素都有三种选择 任选其一均可 答案为3^n
当s中最多的元素个数为4个时 答案为4^n

//题目问的是在出现最多重复元素之和下的字符串的数量；
#include<bits/stdc++.h>
const int N=100010;
const int MOD = 1e9+7; 
using namespace std;
int n;
char str[N];
int cnt[100];
int main()
{
    cin>> n;
    cin >>str;
    // ct 存储最大元素的个数
    // mx 存储最大元素的大小 
    int ct=1,mx=0;
    for (int i = 0; i < n; i ++ ){
        int t=++cnt[str[i]];
        if(t>mx){
            mx=t;
            ct=1;
        }
        else if(mx==t){
            ct++;
        }
    }
    // 贡献法求出最大元素个数的n次方；
    // 具体见      3、思路转换
    long long res=1;
    for (int i = 0; i < n; i ++ ){
        res=(long long )res*ct%MOD;
    }
    cout<< res;
}

题目二：

https://www.acwing.com/problem/content/description/2871/

首先求出左右两边不相等字符的位置，然后根据递推公式：pre[i]*next[j]求出每一个字符的贡献；
注意左右两端无相等字符的情况
相似的分析过程如：

分为三种情况：
1.左右相邻处都有H牛 pre*nest；（两者相乘就是需要丢弃的照片个数）
2.当左边没有H牛时，只计算右边有多少H nest-1；
3.右边没有H牛时，只计算左边有多少H pre-1；
其中 pre 表示的是前面有多少H牛

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
char str[N];
int pre[N],next_1[N],h[26];
int t;
int main(){
    cin >> str+1;
    long long res=0;
    int len=strlen(str+1);
    for (int i=1;i<=len;i++){
        int t=str[i]-'a';
        pre[i]=h[t]-i-1;
        h[t]=i;
    }
    for(int i=0;i<26;i++){
            h[i]=len+1;
        }
    for (int i=len;i>=1;i--){
        int t=str[i]-'a';
        next_1[i]=i-h[t]-1;
        h[t]=i;
    }
    for (int i = 1; i <= len; i ++ ){
        
        res+=(long long)(pre[i]+1)*(next_1[i]+1);
    }
    cout << res;
}