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

日付: 11月 07, 2018

## Problem
定义字符'G'出现次数为$k$次以上的字符串为完美串。给定一个字符串$S$，求这样的四元组$(a,b,c,d)$的个数：$S$的$[a,b]$和$[c,d]$子串相连组成完美串。

数据范围：$|S| \le 3000$
## Solution
这个题就是个比较简单的dp，思路很容易就想到了，然而华丽踩坑疯狂WA😱

因为$|S|$比较小，复杂度可以是$O(N^2)$。枚举右子串$[c,d]$，然后把$[1,c-1]$区间内满足条件的左子串$[a,b]$加起来就可以了。分情况讨论：
1. $[c,d]$本身已经是完美串，那么$[1,c-1]$区间的所有子区间都满足条件，答案加上$\frac{c(c-1)}{2}$
2. $[c,d]$不是完美串

2.1 $[a,b]$是完美串，并且在区间$[0,c-1]$内      
  2.2 $[a,b]$*不是完美串*，但$[a,b]$全为'G'的后缀和$[c,d]$全为'G'的前缀长度和大于等于$k$

在枚举$[c,d]$时，需要维护两个值，从$c$开始全部是'G'的前缀长度$pref$以及$[c,d]$中最长连续的'G'的长度$cont$。定义$F(i,j)$为在区间$[1,i]$内，全为'G'的后缀长度*至少*为$j$的*非完美串*的数量。定义$H(i)$为区间$[1,i]$内完美串的数量。有了$F$和$H$，情况2的答案就是$F(c-1,k-pref)+H(c-1)$。

$F$和$H$可以用dp计算，一个比较坑的地方就是$F$计数的时侯，不仅要排除后缀已经达到$k$的，还要排除连续出现的'G'已经达到$k$的。计算$H$时，可以先计算出以$i$结尾的完美串数$H'(i)$，然后求前缀和。计算$F$时，可以先计算出以$i$结尾并且后缀长度为$j$的非完美串数量$F'(i,j)$，然后分别对$i$和$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+前缀和)

コメント

コメントを投稿