Siyuan

「Codeforces 1152D」Neko and Aki's Prank
「Codeforces 1152D」Neko and Aki's Prank
扫描右侧二维码阅读全文
30
2019/04

「Codeforces 1152D」Neko and Aki's Prank

题目链接:Codeforces 1152D

Neko 把所有长度为 $2n$ 的合法括号序列插入到一棵 $\text{Trie}$ 树中,接着 Aki 向他提出了一个有趣的问题:在这个 $\text{Trie}$ 树中的最大匹配(找到最大的一组边,使得没有两条边具有公共顶点)的大小是多少?答案对 $10 ^ 9 + 7$ 取模。

数据范围:$1 \le n \le 1000$。


Solution

可以把最大匹配转化为:所有深度为奇数的点的数量(特殊地,定义 $\text{Trie}$ 树中根节点的深度为 $0$),具体构造方法就是对于每个深度为奇数的点,选择其下方的任意一条边。

我们可以直接 $\text{DP}$ 所有前缀的数量,设 $f(i, j)$ 表示有 $i$ 个左括号,$j$ 个右括号的前缀数量。转移方程非常简单:

$$ f(i, j) = f(i - 1, j) + f(i, j - 1) \quad (i \ge j) $$

那么答案就是 $\sum_{2 \not \mid i + j} f(i, j)$。

时间复杂度:$\mathcal O(n ^ 2)$。


Code

#include <cstdio>

const int N = 1e3 + 5;
const int P = 1e9 + 7;

int n, f[N][N];

void add(int &x, int y) {
    (x += y) >= P && (x -= P);
}
int main() {
    scanf("%d", &n);
    f[0][0] = 1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            f[i][j] = (f[i - 1][j] + f[i][j - 1]) % P;
            if ((i + j) & 1) add(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}
最后修改:2019 年 06 月 28 日 01 : 12 PM

发表评论