Skip to content

14011: 【原4011】k树

题目

题目描述

author: yura 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4011

Description

丁姐在幼儿园里发现了一颗奇怪的树，她觉得自己发现了一个伟大的新物种并给它取名叫k树。k树满足如下性质：

  1. 根节点至多可以长出k个子节点

  2. 每个节点的第i个子节点(i=0,1,2...k-1)上至多可以长出k-i个子节点

丁姐想知道，当这棵树长到h(h>1，根节点记做第一层)层那么高的时候，树上至多可以有多少片叶子。

Input Format

两个整数 k h

50%数据: \(2 \leq k \leq 10 , 2 \leq h \leq 10 \)

80%数据: \(2 \leq k \leq 20 , 2 \leq h \leq 20 \)

100%数据: \(2 \leq k \leq 50 , 2 \leq h \leq 50 \)

Output Format

最大叶子数

Sample Input

3 3

Sample Output

6

Limits

时间限制：1000ms

ligongzzz's solution 

#include "iostream"
#include "cstring"
#include "cmath"
#include "algorithm"

using namespace std;

//常数
constexpr auto maxNum = 10000;
constexpr auto intMax = 20;

//新无符号大整数类
class unsignedBigInt {
private:
    bool del = false;
public:
    char* ch;
    int startNum = 0;
    int len = 0;

    //初始化
    unsignedBigInt(const char* input) {
        if (del)
            delete[] ch;

        len = (strlen(input) + 1) * 2;
        startNum = strlen(input);
        ch = new char[len];
        memset(ch, 0, len);
        for (int i = 0; i < strlen(input); i++)
            ch[i + startNum] = input[i];

        del = true;
    }
    unsignedBigInt(int num) {
        if (del)
            delete[] ch;

        //临时数组
        int n = 0, temp[intMax];
        if (num == 0) {
            n = 1;
            temp[0] = 0;
        }
        else
            for (; num > 0; num /= 10)
                temp[n++] = num % 10;


        len = (n + 1) * 2;
        startNum = n;
        ch = new char[len];
        memset(ch, 0, len);

        for (int i = 0; i < n; i++)
            ch[startNum + i] = temp[n - i - 1] + '0';

        del = true;
    }
    unsignedBigInt(void) {
        if (del)
            delete[] ch;

        len = 1;
        startNum = 0;
        ch = new char[len];
        memset(ch, 0, len);

        del = true;
    }
    unsignedBigInt(int num, int sizen) {
        if (del)
            delete[] ch;

        len = (sizen + 1) * 2;
        startNum = sizen;
        ch = new char[len];
        memset(ch, 0, len);

        if (num >= 0) {
            int n = 0, temp[intMax];
            if (num == 0) {
                n = 1;
                temp[0] = 0;
            }
            else
                for (; num > 0; num /= 10)
                    temp[n++] = num % 10;

            for (int i = 0; i < n; i++)
                ch[startNum + i] = temp[n - i - 1] + '0';
        }

        del = true;
    }

    //析构
    ~unsignedBigInt() {
        if (del)
            delete[] ch;
    }

    //计算真实长度
    int realLength(const unsignedBigInt & b) {
        return strlen(b.ch + b.startNum);
    }

    //复制构造函数
    unsignedBigInt(const unsignedBigInt & b) {
        if (del)
            delete[] ch;

        len = b.len;
        startNum = b.startNum;
        ch = new char[len];
        for (int i = 0; i < len; i++)
            ch[i] = b.ch[i];

        del = true;
    }

    //输入输出
    friend ostream & operator<<(ostream & output, const unsignedBigInt & bi);
    friend istream & operator>>(istream & input, unsignedBigInt & bi);

    //赋值
    unsignedBigInt & operator=(const unsignedBigInt & b) {
        //检查自身赋值
        if (this == &b)
            return *this;

        if (del)
            delete[] ch;

        len = b.len;
        startNum = b.startNum;
        ch = new char[len];
        for (int i = 0; i < len; i++)
            ch[i] = b.ch[i];

        del = true;
        return *this;
    }

    unsignedBigInt & operator=(int num) {
        if (del)
            delete[] ch;

        //临时数组
        int n = 0, temp[intMax];
        if (num == 0) {
            n = 1;
            temp[0] = 0;
        }
        else
            for (; num > 0; num /= 10)
                temp[n++] = num % 10;


        len = (n + 1) * 2;
        startNum = n;
        ch = new char[len];
        memset(ch, 0, len);

        for (int i = 0; i < n; i++)
            ch[startNum + i] = temp[n - i - 1] + '0';

        del = true;
        return *this;
    }

    //比较符
    //大于
    bool operator>(const unsignedBigInt & b) {
        return (strcmp(ch + startNum, b.ch + b.startNum) > 0 && strlen(ch + startNum) == strlen(b.ch + b.startNum)) || strlen(ch + startNum) > strlen(b.ch + b.startNum) ? true : false;
    }
    //运算符
    //加号
    unsignedBigInt operator+(const unsignedBigInt & b) {
        unsignedBigInt temp(-1, max(realLength(*this), realLength(b)) + 2);
        int jw = 0;
        int test = realLength(*this);

        for (int i = 0; realLength(*this) > i || realLength(b) > i || jw != 0; i++) {
            //判断加数
            int j1 = realLength(*this) <= i ? 0 : ch[startNum + strlen(ch + startNum) - i - 1] - '0';
            int j2 = realLength(b) <= i ? 0 : b.ch[b.startNum + strlen(b.ch + b.startNum) - i - 1] - '0';

            //运算
            temp.ch[--temp.startNum] = (j1 + j2 + jw) % 10 + '0';
            jw = (j1 + j2 + jw) / 10;
        }

        //返回
        return temp;
    }
};


//输入输出流重载
//无符号大整数
ostream& operator<<(ostream & output, const unsignedBigInt & bi) {
    output << bi.ch + bi.startNum;
    return output;
}
istream& operator>>(istream & input, unsignedBigInt & bi) {
    char ch[maxNum];
    input >> ch;
    bi = unsignedBigInt(ch);
    return input;
}

unsignedBigInt numData[51][51];
int k, h;
void cnt(int num, int depth) {
    if (depth == 1) {
        numData[num][depth] = 1;
        return;
    }
    if (numData[num][depth] > 0)
        return;
    //遍历
    for (int i = 0; i < num; i++) {
        cnt(k - i, depth - 1);
        numData[num][depth] = numData[num][depth] + numData[k - i][depth - 1];
    }
    return;
}

int main() {
    cin >> k >> h;
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= h; j++)
            numData[i][j] = 0;
    cnt(k, h);

    cout << numData[k][h];

    return 0;
}

Neight99's solution 

#include <iostream>

using namespace std;

const int maxN = 10000;

class bigint {
   private:
    long long data[20];
    const long long base = 1e8;

   public:
    bigint(int x = 0);
    bigint& operator=(const bigint&);
    bigint operator+(const bigint&) const;
    bool operator==(const int) const;
    void output() const;
};

bigint::bigint(int x) {
    for (int i = 0; i < 20; i++) {
        data[i] = 0;
    }
    data[0] = x;
}

bigint& bigint::operator=(const bigint& right) {
    for (int i = 0; i < 20; i++) {
        data[i] = right.data[i];
    }

    return *this;
}

bigint bigint::operator+(const bigint& right) const {
    bigint ans(0);
    long long carry = 0;

    for (int i = 0; i < 20 && (carry || data[i] || right.data[i]); i++) {
        ans.data[i] = data[i] + right.data[i] + carry;
        carry = ans.data[i] / base;
        ans.data[i] %= base;
    }

    return ans;
}

bool bigint::operator==(const int x) const {
    for (int i = 19; i > 0; i--) {
        if (data[i] != 0) {
            return 0;
        }
    }

    return data[0] == x;
}

void bigint::output() const {
    int i = 19;
    while (data[i] == 0) {
        i--;
    }

    printf("%lld", data[i]);
    i--;
    for (; i >= 0; i--) {
        printf("%08lld", data[i]);
    }

    return;
}

bigint dp[maxN][maxN];

bigint DP(int, int, int);

int main() {
    int k, h;
    bigint ans;

    scanf("%d%d", &k, &h);
    ans = DP(k, h, k);

    ans.output();

    return 0;
}

bigint DP(int a, int b, int k) {
    if (!(dp[a][b] == 0)) {
        return dp[a][b];
    } else if (b == 2) {
        dp[a][b] = a;
        return dp[a][b];
    } else {
        for (int i = 0; i < a; i++) {
            dp[a][b] = dp[a][b] + DP(k - i, b - 1, k);
        }
        return dp[a][b];
    }
}

q4x3's solution 

/**
 * 一道简单的dp
 * 难就难在大整数。。。
 **/
#include <iostream>
#include <cstring>

using namespace std;

class bigint {
    public:
    char dt[100];

    bigint():dt("0") {}
    bigint &operator=(const bigint &obj) {
        strcpy(dt, obj.dt);
        return *this;
    }
    bigint &operator=(const int &obj) {
        dt[0] = obj + '0';
        dt[1] = 0;
        return *this;
    }
    friend ostream& operator<<(ostream &os, const bigint &obj);
    friend bigint operator+(const bigint &i1, const bigint &i2);
};

ostream& operator<<(ostream &os, const bigint &obj) {
    for(int i = strlen(obj.dt) - 1;i >= 0;-- i) cout << obj.dt[i];
}

bigint operator+(const bigint &i1, const bigint &i2) {
    int carry = 0;
    int len = max(strlen(i1.dt), strlen(i2.dt));
    bigint tmp;
    for(int i = 0;i < len;++ i) {
        int tmp1, tmp2;
        if(i >= strlen(i1.dt)) tmp1 = 0;
        else tmp1 = i1.dt[i] - '0';
        if(i >= strlen(i2.dt)) tmp2 = 0;
        else tmp2 = i2.dt[i] - '0';
        int sum = tmp1 + tmp2 + carry;
        tmp.dt[i] = sum % 10 + '0';
        carry = sum / 10;
    }
    if(carry) {
        tmp.dt[len] = '1';
        tmp.dt[len + 1] = 0;
    } else {
        tmp.dt[len] = 0;
    }
    return tmp;
}

bigint a[60][60];
int k, h;

int main() {
    scanf("%d%d", &k, &h);
    for(int j = 1;j <= k;++ j) a[1][j] = 1;
    for(int i = 2;i <= h;++ i) {
        for(int j = 1;j <= k;++ j) {
            a[i][j] = a[i][j - 1] + a[i - 1][k - j + 1];
        }
    }
    cout << a[h][k] << endl;
    return 0;
}

victrid's solution 

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
class ulll {
private:
    unsigned long long data[20];
    int getDigitNum(unsigned long long n) const {
        int dig = 1;
        if (n >= 10000000000000000ull) {
            n /= 10000000000000000ull;
            dig += 16;
        }
        if (n >= 100000000ull) {
            n /= 100000000ull;
            dig += 8;
        }
        if (n >= 10000ull) {
            n /= 10000ull;
            dig += 4;
        }
        if (n >= 100ull) {
            n /= 100ull;
            dig += 2;
        }
        while (n >= 10ull) {
            n /= 10ull;
            dig += 1;
        }
        return dig;
    }

public:
    operator bool() const {
        for (int i = 19; i >= 0; i--) {
            if (data[i] != 0)
                return true;
        }
        return false;
    }
    ulll() {
        for (int i = 0; i < 20; i++) {
            data[i] = 0;
        }
    }
    ulll(long long init) {
        for (int i = 1; i < 20; i++) {
            data[i] = 0;
        }
        data[0] = abs(init);
        return;
    }
    ulll& operator+=(const ulll& rhs) {
        for (int i = 0; i < 20; i++) {
            data[i] += rhs.data[i];
            while (i != 19 && data[i] >= 10000000000000000000ull) {
                data[i + 1] += 1;
                data[i] -= 10000000000000000000ull;
            };
        }
        return *this;
    }
    void print() const {
        bool nof = 0;
        if (!*this) {
            putchar('0');
            return;
        }
        for (int i = 19; i >= 0; i--) {
            if (!nof && data[i] == 0)
                continue;
            if (nof) {
                int p = 19 - getDigitNum(data[i]);
                while (p--)
                    putchar('0');
            }
            nof = 1;
            printf("%llu", data[i]);
        }
        return;
    }
};

ulll k_h[55][55];

ulll DP(int d, int h, int k) {
    if (k_h[d][h])
        return k_h[d][h];
    if (h == 2) {
        k_h[d][h] = d;
        return k_h[d][h];
    }
    for (int i = 0; i < d; i++) {
        k_h[d][h] += DP(k - i, h - 1, k);
    }
    return k_h[d][h];
}
int main() {
    int k, h;
    scanf("%d%d", &k, &h);
    for (int i = 0; i < 55; i++) {
        for (int j = 0; j < 55; j++) {
            k_h[i][i] = 0;
        }
    }
    DP(k, h, k).print();
    return 0;
}

WashSwang's solution 

#include <iostream>
#include <cstring>
#include <iomanip>

using namespace std;
const int p=1000000000;
//Same as 4152
class longint{

    long long num[3000];
    int len;
public:
    longint(){
        memset(num,0,sizeof(num));
        len=1;
    };

    longint(const char *s){
        memset(num,0,sizeof(num));
        int l=(strlen(s)-1)/9+1,length=strlen(s);
        for (int i=0;i<l;++i){
            for (int j=length-9*i-9;j<length-9*i;++j)
                if (j>=0)
                    num[i]=num[i]*10+s[j]-48;
        }
        len=l;
    }

    longint(int x){
        memset(num,0,sizeof(num));
        len=0;
        while (x!=0)
        {
            num[len++]=x%p;
            x/=p;
        }
    }

    longint(const longint &a):len(a.len){
        memset(num,0,sizeof(num));
        for (int i=0;i<a.len;++i)
            num[i]=a.num[i];
    }

    longint &operator=(const longint& a){
        memset(num,0,sizeof(num));
        len=a.len;
        for (int i=0;i<a.len;++i)
            num[i]=a.num[i];
        return *this;
    }

    friend longint operator+(const longint& a,const longint& b){
        long long c=0;
        longint r;
        r.len=max(a.len,b.len);
        for (int i=0;i<r.len;++i){
            r.num[i]=a.num[i]+b.num[i]+c;
            c=r.num[i]/p;
            r.num[i]%=p;
        }
        if (c>0) r.num[r.len++]=c;
        return r;
    }

    friend longint operator-(const longint& a,const longint& b){
        int c=0;
        longint r;
        r.len=max(a.len,b.len);
        for (int i=0;i<max(a.len,b.len);++i){
            r.num[i]=a.num[i]-b.num[i]-c;
            c=0;
            if (r.num[i]<0){
                r.num[i]+=p;
                c=1;
            }
        }
        while (r.len>1&&!r.num[r.len-1]) r.len--;
        return r;
    }

    friend longint operator*(const longint& a,const longint& b){
        long long c=0,pos;
        int x=0;
        longint r;
        for (int i=0;i<b.len;++i){
            x=i;
            c=0;
            longint tmp;
            for (int j=0;j<a.len;++j){
                pos=a.num[j]*b.num[i]+c;
                c=pos/p;
                tmp.num[x]=pos%p;
                x++;
            }
            tmp.len=x;
            if (c>0) tmp.num[tmp.len++]=c;
            r=r+tmp;
        }
        return r;
    }

    friend longint div(const longint& a){
        longint r;
        long long x=0;
        for (int i=a.len-1;i>=0;i--){
            x=x*p+a.num[i];
            r.num[i]=x/2;
            x%=2;
        }
        r.len=a.len;
        if (!r.num[r.len-1]) r.len--;
        return r;
    }

    friend bool operator>(const longint& a,const longint& b){
        if (a.len>b.len) return true;
        if (a.len<b.len) return false;
        for (int i=a.len-1;i>=0;--i){
            if (a.num[i]>b.num[i]) return true;
            if (a.num[i]<b.num[i]) return false;
        }
        return false;
    }

    friend ostream& operator<<(ostream& os,const longint &a){
        os.fill('0');
        os<<a.num[a.len-1];
        for (int i=a.len-2;i>=0;--i) {
            os<<setw(9)<<a.num[i];
        }
        return os;
    }

    friend bool odd(longint &a){
        return a.num[0]%2!=0;
    }
};
longint x[51][51];
int h,k;
int main() {
    cin>>k>>h;
    for (int i=0;i<=k-1;++i) x[1][i]=k-i;
    for (int i=2;i<=h-1;++i){
        for (int j=0;j<=k-1;++j)
            for (int l=0;l<k-j;++l) x[i][j]=x[i][j]+x[i-1][l];
    }
    cout<<x[h-1][0];
}