OI

优美的树 shu

Description

众所周知，树是 n 个节点 n-1 条边的结构，而所谓的优美的树需要满足如下条件：

  1. 这是一棵有根二叉树；
  2. 非叶节点需有两个儿子；
  3. 不可以变换为 k-左偏树。

所谓的 k-左偏树是指一棵有 k 个叶子的树，每个非叶节点的右儿子均为叶子且均有左儿子。

所谓的变换指的是经过若干次如下两种变换：

  1. 删去一个节点的两个儿子；
  2. 用一个节点的某个儿子替换该节点。

如下图，若 k=3 则这不是一棵优美的树。

NOT

现在给你 k 和 n，想要你求出叶子数为 1,2,3…n 的优美的树分别有多少。

Input

一行两个整数 k 和 n。

Output

n 行第 i 行一个正整数表示叶子数为 i 时的答案。答案很大所以对 1,000,000,009 取模。

Sample Input and Output

shu.inshu.out4 51 1 2 4 87 61 1 2 5 14 42

HINT

对于 30%的数据 n,k<=500；

对于另外 40%的数据 k<=20；

对于 100%的数据 n,k<=5,000。

Solution

实际上不能有k-左偏树就是让你从根走到每个叶子经过左儿子个数<k (根算左孩子)

我们把n个叶子扒掉，剩下n-1个节点，那么我们只需从根走到每个儿子都不经过大于等于k-1个左儿子即可

考虑按照先续遍历填入n-1个点，填入i+1个点的时候：

  1. 将其填在i个点的左儿子 \( f_{i,j} \rightarrow f_{i+1,j+1}\)
  2. 将其填在i个点的右儿子 \( f_{i,j} \rightarrow f_{i+1,j}\)
  3. 将其填在祖先的某个节点的右儿子（因为是先序遍历，左儿子已经填过了） \( f_{i,j} \rightarrow f_{i+1,j-k},k \gt 0\)

这个dp可以后缀和优化， \( O(n^2) \) 即可通过这道题目。

巧妙之处：

  1. 用先序遍历，不重不漏；
  2. 预先去掉所有叶子，去掉每个非叶子节点有两个孩子这个限制；
  3. 后缀和优化。

std值得一看。。。

Code

我的。。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <map>
#include <queue>
#include <set>
//#define OJ
#define PROB "shu"
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1000000009;
const int maxn = 100005;

//struct edge_T {int to, next;} edge[maxn<<1];

inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
    while ('0' <= c && c <= '9') {r = r * 10 + (c - '0'); c = getchar();}
    if (b) return r;
    return -r;
}

int n, k, f[5005][5005], g[5005][5005];

int main() {
#ifndef OJ
    freopen(PROB".in", "r", stdin);
    freopen(PROB".out", "w", stdout);
#endif

    k = getint(); n = getint();
    f[1][1] = 1;
    g[1][1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < k; ++j)
            f[i][j] = g[i-1][j-1];
        for (int j = k-1; j >= 1; --j)
            g[i][j] = (g[i][j+1] + f[i][j]) %  INF;
    }

    for (int i = 1; i <= n; ++i) printf("%d\n", g[i][1]);

    fclose(stdin);
    fclose(stdout);

    return 0;
}

std!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <algorithm>
#include <cstdio>
using namespace std;
const int N=5005,Mod=1e9+9;
int k,n,f[N][N];
int main(){
    freopen("shu.in","r",stdin);
    freopen("shu.out","w",stdout);
    scanf("%d%d",&k,&n);
    f[1][1]=1;
    for(int i=2;i<=n;i++)
        for(int j=k-1;j;j--)
            f[i][j]=(f[i][j+1]+f[i-1][j-1])%Mod;
    for(int i=1;i<=n;i++) printf("%d\n", f[i][1]);
    return 0;
}