算法学习系列（四十）：贡献法

目录

• 引言
• 概念
• 一、孤独的照片
• 二、牛的基因学
• 三、字串分值

  引言

  关于这个贡献法考的不是很多，主要题型是出现在需要枚举每一个组合这类题，出现的次数较多。没有固定的模板，就是一种思想，跟贪心一样，每个题都是不一样的，还是要具体问题具体分析，所以 见题是很重要的，本文章也是从讲题的方式来讲解。

  ---

  概念

  贡献法：从枚举的思路改为每个元素能为总和贡献多少，跟贪心一样是一种思想，没有固定的模板和套路，只能因题而异。

  ---

  一、孤独的照片

  标签：贡献法

  思路：这道题如果用暴力也就是 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 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 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 
  示例代码：
   
  #include 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;
  }