目录
- 引言
- 概念
- 一、孤独的照片
- 二、牛的基因学
- 三、字串分值
引言
关于这个贡献法考的不是很多，主要题型是出现在需要枚举每一个组合这类题，出现的次数较多。没有固定的模板，就是一种思想，跟贪心一样，每个题都是不一样的，还是要具体问题具体分析，所以 见题是很重要的，本文章也是从讲题的方式来讲解。
概念
贡献法：从枚举的思路改为每个元素能为总和贡献多少，跟贪心一样是一种思想，没有固定的模板和套路，只能因题而异。
一、孤独的照片
标签：贡献法
思路：这道题如果用暴力也就是
O
(
N
2
)
O(N^2)
O(N2) 的做法，肯定是超时的，能过
5
12
\frac{5}{12}
125 的数据，我就不写了。题目可以简化为，一个字符串中个数大于等于
3
3
3 的子串中只有一个不同字符的数量（字符串中只有两种字符）。我们可以枚举每一个牛，看这个牛能为最终答案贡献多少种可能。有三种情况，如下图，第一种，左右两边至少有一头牛，拿左边连续的不同的牛的数量乘以右边连续的不同的牛的数量，第二、三种，只有一边有连续的不同的牛，拿该数量减一与
0
0
0 取最大值即可，把枚举的所有值相加即可。关于如果求左右两边不同的连续牛的个数，见代码。
题目描述：
Farmer John 最近购入了 N 头新的奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。
奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。
然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的
牛会感到孤立和不自然。
在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛
的照片，都扔掉了。
给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。
如果两张照片以不同位置的奶牛开始或结束，则认为它们是不同的。
输入格式
输入的第一行包含 N。
输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛，则字符串的第 i 个字符为 G。否则，第
i 头奶牛是荷斯坦牛，该字符为 H。
输出格式
输出 Farmer John 会扔掉的孤独的照片数量。
数据范围
3≤N≤5×105
输入样例：
5
GHGHG
输出样例：
3
样例解释
这个例子中的每一个长为 3 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片，并会被 Farmer
John 扔掉。
所有更长的子串（GHGH、HGHG 和 GHGHG）都可以被接受。
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5+10;
int n;
char str[N];
int l[N], r[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> str;
for(int i = 0, sg = 0, sh = 0; i < n; ++i)
{
if(str[i] == 'G') l[i] = sh, sg++, sh = 0;
if(str[i] == 'H') l[i] = sg, sh++, sg = 0;
}
for(int i = n - 1, sg = 0, sh = 0; i >= 0; --i)
{
if(str[i] == 'G') r[i] = sh, sg++, sh = 0;
if(str[i] == 'H') r[i] = sg, sh++, sg = 0;
}
LL res = 0;
for(int i = 0; i < n; ++i)
{
res += (LL)l[i] * r[i] + max(0, l[i] - 1) + max(0, r[i] - 1);
}
cout << res << endl;
return 0;
}
二、牛的基因学
标签：贡献法
思路：首先要求最大的值，也就是该子串跟另一个子串嵌套循环各移动
n
n
n 次，比较同一位置的字符是否相同，求另一个字符串的组合有多少可能。最大值问题可以转换为第一个字符串不动，第二个字符串中的每个字符都跟第一个字符串的字符比较一次，求最大值，如下图所示，所以我们把
t
t
t 中的所有字符都成为
s
s
s 中出现次数最多的那个字符，这样最大值就是
n
n
n 倍的该数出现的次数。可能性取决于出现次数最多的数可能有多个，所以从
s
s
s 中找出出现次数最多的数的个数
c
t
ct
ct ，t中的每个字符都有
c
t
ct
ct 中选法，最终答案就是
c
t
n
ct ^ n
ctn。
题目描述：
贝茜最近正在学习基因学，具体来说她正在研究 DNA 序列比对。
DNA 序列字符串是指由字符 A、C、G、T 组成的字符串。
设字符串 s 和 t 是两个长度为 n 的 DNA 序列字符串。
将函数 h(s,t) 定义为在字符串 s 和 t 中，字符相同的位置数量。
利用函数 h(s,t) 进一步定义 DNA 距离函数 ρ(s,t)：
ρ(s,t)=∑i=0n−1∑j=0n−1h(shift(s,i),shift(t,j))其中，shift(s,i) 表示将字符串 s 循环左移 i 位后得到的字符串。
例如：
ρ(“TCG”,”GCA”)=h(“TCG”,”GCA”)+h(“TCG”,”CAG”)+h(“TCG”,”AGC”)+
h(“CGT”,”GCA”)+h(“CGT”,”CAG”)+h(“CGT”,”AGC”)+
h(“GTC”,”GCA”)+h(“GTC”,”CAG”)+h(“GTC”,”AGC”)=
1+1+0+0+1+1+1+0+1=6
现在，给定一个长度为 n 的 DNA 序列字符串 s，请你统计一共有多少个长度为 n 的 DNA 序列字符串 t 与字符串 s 的 DNA 距
离达到最大可能值。
更形象地说，请你计算一共有多少个长度为 n 的 DNA 序列字符串 t 满足：ρ(s,t)=maxu:|u|=|s|ρ(s,u)。
由于结果可能很大，你只需要输出对 109+7 取模后的结果。
输入格式
第一行包含整数 n。
第二行包含一个长度为 n 的由字符 A、C、G、T 组成的字符串，表示字符串 s。
输出格式
一个整数，表示对 109+7 取模后的结果。
数据范围前 3 个测试点满足 1≤n≤3。
所有测试点满足 1≤n≤105。
输入样例1：
1
C
输出样例1：
1
输入样例2：
2
AG
输出样例2：
4
输入样例3：
3
TTT
输出样例3：
1
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10, MOD = 1e9+7;
int n;
char str[N];
int cnt[100];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> str;
int mx = 0, ct = 0;
for(int i = 0; i < n; ++i)
{
int t = ++cnt[str[i]];
if(t > mx) mx = t, ct = 0;
if(t == mx) ct++;
}
LL res = 1;
for(int i = 0; i < n; ++i)
{
res = res * ct % MOD;
}
cout << res << endl;
return 0;
}
三、字串分值
标签：贡献法
思路：如果按常规思路就是枚举每个子串，然后判断每个子串中恰好出现一次字符的个数，时间复杂度都为
O
(
N
3
)
O(N^3)
O(N3) 了，而
N
=
1
0
5
N = 10 ^ 5
N=105，明显超超时了，所以得换一种思路。我们可以枚举每一个字符的贡献程度，最后相加即可。每个字符的贡献程度，可以算出该字符左边和右边第一次出现的位置，然后根据排列组合可以得出总共可以有多少个有效子串的组合，由图可以得出计算公式应为
(
i
−
l
[
i
]
)
∗
(
r
[
i
]
−
i
)
(i - l[i]) * (r[i] - i)
(i−l[i])∗(r[i]−i) ，然后遍历所以字符即可。
题目描述：
对于一个字符串 S，我们定义 S 的分值 f(S) 为 S 中恰好出现一次的字符个数。
例如 f(“aba”)=1，f(“abc”)=3, f(“aaa”)=0。
现在给定一个字符串 S[0…n−1]（长度为 n），请你计算对于所有 S 的非空子串 S[i…j](0≤i≤j<n)， f(S[i…j]) 的和是多少。
输入格式
输入一行包含一个由小写字母组成的字符串 S。
输出格式
输出一个整数表示答案。
数据范围
对于 20% 的评测用例，1≤n≤10；
对于 40% 的评测用例，1≤n≤100；
对于 50% 的评测用例，1≤n≤1000；
对于 60% 的评测用例，1≤n≤10000；
对于所有评测用例，1≤n≤100000。
输入样例：
ababc
输出样例：
21
样例说明
所有子串 f 值如下：
a 1
ab 2
aba 1
abab 0
ababc 1
b 1
ba 2
bab 1
babc 2
a 1
ab 2
abc 3
b 1
bc 2
c 1
示例代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int n;
char str[N];
int l[N], r[N], p[26];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> str + 1;
n = strlen(str+1);
for(int i = 1; i <= n; ++i)
{
int t = str[i] - 'a';
l[i] = i - p[t];
p[t] = i;
}
for(int i = 0; i < 26; ++i) p[i] = n + 1;
for(int i = n; i > 0; --i)
{
int t = str[i] - 'a';
r[i] = p[t] - i;
p[t] = i;
}
LL res = 0;
for(int i = 1; i <= n; ++i)
{
res += (LL)l[i] * r[i];
}
cout << res << endl;
return 0;
}
