51Nod 1313. 完美数(dp+前缀和)

日付: 11月 07, 2018

## Problem
定义字符'G'出现次数为<math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k次以上的字符串为完美串。给定一个字符串<math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S，求这样的四元组<math><semantics><mrow><mo>(</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo separator="true">,</mo><mi>c</mi><mo separator="true">,</mo><mi>d</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">(a,b,c,d)</annotation></semantics></math>(a,b,c,d)的个数：<math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math>S的<math><semantics><mrow><mo>[</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[a,b]</annotation></semantics></math>[a,b]和<math><semantics><mrow><mo>[</mo><mi>c</mi><mo separator="true">,</mo><mi>d</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[c,d]</annotation></semantics></math>[c,d]子串相连组成完美串。

数据范围：<math><semantics><mrow><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi><mo>≤</mo><mn>3000</mn></mrow><annotation encoding="application/x-tex">|S| \le 3000</annotation></semantics></math>∣S∣≤3000
## Solution
这个题就是个比较简单的dp，思路很容易就想到了，然而华丽踩坑疯狂WA😱

因为<math><semantics><mrow><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">|S|</annotation></semantics></math>∣S∣比较小，复杂度可以是<math><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>N</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(N^2)</annotation></semantics></math>O(N2)。枚举右子串<math><semantics><mrow><mo>[</mo><mi>c</mi><mo separator="true">,</mo><mi>d</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[c,d]</annotation></semantics></math>[c,d]，然后把<math><semantics><mrow><mo>[</mo><mn>1</mn><mo separator="true">,</mo><mi>c</mi><mo>−</mo><mn>1</mn><mo>]</mo></mrow><annotation encoding="application/x-tex">[1,c-1]</annotation></semantics></math>[1,c−1]区间内满足条件的左子串<math><semantics><mrow><mo>[</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[a,b]</annotation></semantics></math>[a,b]加起来就可以了。分情况讨论：
1. <math><semantics><mrow><mo>[</mo><mi>c</mi><mo separator="true">,</mo><mi>d</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[c,d]</annotation></semantics></math>[c,d]本身已经是完美串，那么<math><semantics><mrow><mo>[</mo><mn>1</mn><mo separator="true">,</mo><mi>c</mi><mo>−</mo><mn>1</mn><mo>]</mo></mrow><annotation encoding="application/x-tex">[1,c-1]</annotation></semantics></math>[1,c−1]区间的所有子区间都满足条件，答案加上<math><semantics><mrow><mfrac><mrow><mi>c</mi><mo>(</mo><mi>c</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mn>2</mn></mfrac></mrow><annotation encoding="application/x-tex">\frac{c(c-1)}{2}</annotation></semantics></math>2c(c−1)
2. <math><semantics><mrow><mo>[</mo><mi>c</mi><mo separator="true">,</mo><mi>d</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[c,d]</annotation></semantics></math>[c,d]不是完美串

2.1 <math><semantics><mrow><mo>[</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[a,b]</annotation></semantics></math>[a,b]是完美串，并且在区间<math><semantics><mrow><mo>[</mo><mn>0</mn><mo separator="true">,</mo><mi>c</mi><mo>−</mo><mn>1</mn><mo>]</mo></mrow><annotation encoding="application/x-tex">[0,c-1]</annotation></semantics></math>[0,c−1]内 
 2.2 <math><semantics><mrow><mo>[</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[a,b]</annotation></semantics></math>[a,b]*不是完美串*，但<math><semantics><mrow><mo>[</mo><mi>a</mi><mo separator="true">,</mo><mi>b</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[a,b]</annotation></semantics></math>[a,b]全为'G'的后缀和<math><semantics><mrow><mo>[</mo><mi>c</mi><mo separator="true">,</mo><mi>d</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[c,d]</annotation></semantics></math>[c,d]全为'G'的前缀长度和大于等于<math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k

在枚举<math><semantics><mrow><mo>[</mo><mi>c</mi><mo separator="true">,</mo><mi>d</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[c,d]</annotation></semantics></math>[c,d]时，需要维护两个值，从<math><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c开始全部是'G'的前缀长度<math><semantics><mrow><mi>p</mi><mi>r</mi><mi>e</mi><mi>f</mi></mrow><annotation encoding="application/x-tex">pref</annotation></semantics></math>pref以及<math><semantics><mrow><mo>[</mo><mi>c</mi><mo separator="true">,</mo><mi>d</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[c,d]</annotation></semantics></math>[c,d]中最长连续的'G'的长度<math><semantics><mrow><mi>c</mi><mi>o</mi><mi>n</mi><mi>t</mi></mrow><annotation encoding="application/x-tex">cont</annotation></semantics></math>cont。定义<math><semantics><mrow><mi>F</mi><mo>(</mo><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">F(i,j)</annotation></semantics></math>F(i,j)为在区间<math><semantics><mrow><mo>[</mo><mn>1</mn><mo separator="true">,</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[1,i]</annotation></semantics></math>[1,i]内，全为'G'的后缀长度*至少*为<math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j的*非完美串*的数量。定义<math><semantics><mrow><mi>H</mi><mo>(</mo><mi>i</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">H(i)</annotation></semantics></math>H(i)为区间<math><semantics><mrow><mo>[</mo><mn>1</mn><mo separator="true">,</mo><mi>i</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[1,i]</annotation></semantics></math>[1,i]内完美串的数量。有了<math><semantics><mrow><mi>F</mi></mrow><annotation encoding="application/x-tex">F</annotation></semantics></math>F和<math><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math>H，情况2的答案就是<math><semantics><mrow><mi>F</mi><mo>(</mo><mi>c</mi><mo>−</mo><mn>1</mn><mo separator="true">,</mo><mi>k</mi><mo>−</mo><mi>p</mi><mi>r</mi><mi>e</mi><mi>f</mi><mo>)</mo><mo>+</mo><mi>H</mi><mo>(</mo><mi>c</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow><annotation encoding="application/x-tex">F(c-1,k-pref)+H(c-1)</annotation></semantics></math>F(c−1,k−pref)+H(c−1)。

<math><semantics><mrow><mi>F</mi></mrow><annotation encoding="application/x-tex">F</annotation></semantics></math>F和<math><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math>H可以用dp计算，一个比较坑的地方就是<math><semantics><mrow><mi>F</mi></mrow><annotation encoding="application/x-tex">F</annotation></semantics></math>F计数的时侯，不仅要排除后缀已经达到<math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k的，还要排除连续出现的'G'已经达到<math><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math>k的。计算<math><semantics><mrow><mi>H</mi></mrow><annotation encoding="application/x-tex">H</annotation></semantics></math>H时，可以先计算出以<math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i结尾的完美串数<math><semantics><mrow><msup><mi>H</mi><mo mathvariant="normal">′</mo></msup><mo>(</mo><mi>i</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">H&#x27;(i)</annotation></semantics></math>H′(i)，然后求前缀和。计算<math><semantics><mrow><mi>F</mi></mrow><annotation encoding="application/x-tex">F</annotation></semantics></math>F时，可以先计算出以<math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i结尾并且后缀长度为<math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j的非完美串数量<math><semantics><mrow><msup><mi>F</mi><mo mathvariant="normal">′</mo></msup><mo>(</mo><mi>i</mi><mo separator="true">,</mo><mi>j</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">F&#x27;(i,j)</annotation></semantics></math>F′(i,j)，然后分别对<math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i和<math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>j求前缀和。

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
#define FD(i,b,a) for(int i=(b);i>=(a);--i)

const int N = 3005;
int n, k, F[N][N], H[N];
char S[N];

void calc() {
 for (int i = 1; i <= n; i++) {
 for (int j = i, suf = 0, flag = 1, cont = 0; j >= 1; j--) {
 if (S[j] != 'G') flag = 0;
 if (flag && S[j] == 'G') suf++;
 if (S[j] != 'G') cont = cont < k ? 0 : k;
 else cont++;
 if (cont >= k) H[i]++;
 else if (suf < k) F[i][suf]++;
 }
 }
 FI(i, 1, n) FD(j, k - 1, 1) F[i][j] += F[i][j + 1];
 FI(i, 1, n) FI(j, 1, k - 1) F[i][j] += F[i - 1][j];
 FI(i, 1, n) H[i] += H[i - 1];
}
int main() {
 scanf("%d%s", &k, S + 1);
 n = strlen(S + 1);
 calc();
 LL ans = 0;
 for (int c = 2; c <= n; c++) {
 for (int d = c, cont = 0, pref = 0, flag = 1; d <= n; d++) {
 if (S[d] != 'G') flag = 0;
 if (flag && S[d] == 'G') pref++;
 if (S[d] != 'G') cont = cont < k ? 0 : k;
 else cont++;
 if (cont >= k) ans += c * (c - 1) / 2;
 else ans += H[c - 1] + F[c - 1][k - pref];
 }
 }
 printf("%lld\n", ans);
 return 0;
}
```

KONGROOの基地

このブログを検索

51Nod 1313. 完美数(dp+前缀和)

コメント

コメントを投稿