T1

Counting Binary Trees

题目描述

Given n nodes, how many shapes of binary trees can them form?
For example: If n = 1, there’s only 1 type of binary tree.
If n = 2, there are two types of binary trees:
and
If n = 3, there are 5 types of binary trees:
and
Please write a function, given N, output the result of tree shape count.

输入

Input is an integer smaller than 30000, indicating how many nodes are there in the binary tree.

输出

Output is an integer, indicating how many shapes of binary trees are there given the input node count.

样例输入

3

样例输出

5

算法

卡特兰数，高精度，压位

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

const int N = 60010, seg = 10000;

int n;
int sum[N];
int primes[N], cnt;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i ++ ) {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int get_exp(int a, int p) {
    int ret = 0;
    while (a) {
        ret += a / p;
        a /= p;
    }
    return ret;
}

vector<int> mul(vector<int> &A, int b) {
    vector<int> ret;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ ) {
        t += A[i] * b;
        ret.push_back(t % seg);
        t /= seg;
    }

    while (t) {
        ret.push_back(t % seg);
        t /= seg;
    }

    return ret;
}

int main() {
    cin >> n;

    if (n <= 0) cout << 0;
    else {
        get_primes(2 * n);

        for (int i = 0; i < cnt; i ++ )
            sum[i] = get_exp(2 * n, primes[i]) - get_exp(n, primes[i]) - get_exp(n + 1, primes[i]);

        vector<int> C = {1};
        for (int i = 0; i < cnt; i ++ )
            for (int j = 0; j < sum[i]; j ++ )
                C = mul(C, primes[i]);

        cout << C.back();
        for (int i = C.size() - 2; i >= 0; i -- ) printf("%04d", C[i]);
    }

    return 0;
}

T2

Zero Dominate Number

题目描述

Given a number n and convert it to binary representation, if there are as many or more zeros than it has ones, the number is called a “Zero Dominate Number”, abbreviation as ZDN. For example, binary form of number ten is 1010; as there are two zeros and two ones, ten is a ZDN; binary form of number 27 is 11011, since it has one zero and four ones, it’s not a ZDN.
Given a start number and an end number, please write a function to output number of ZDN’s between them (1 <= start < end <= 2000000000).

输入

Two comma-separated integers, respectively start and end.

输出

A single integer indicating the count of ZDN in the inclusive range [start, end]

样例输入

2,12

样例输出

6

算法

数位DP

C++ 代码

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 70;

int l, r;
int f[N][N];

void init() {
    for (int i = 0; i <= N; i ++ )
        for (int j = 0; j <= N; j ++ )
            if (j == 0) f[i][j] = 1;
            else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}

int dp(int n) {
    if (!n) return 1;

    vector<int> nums;
    while (n) nums.push_back(n % 2), n /= 2;

    int ret = 0, last = 0;
    for (int i = nums.size() - 2; i >= 0; i -- ) {
        int x = nums[i];
        if (x) {
            int k = (nums.size() + 1) / 2 - last - 1;
            k = k < 0 ? 0 : k;
            for (int j = k; j <= i; j ++ )
                ret += f[i][j];
        } else {
            last ++ ;
        }
    }

    for (int i = 1; i < nums.size(); i ++ )
        for (int j = (i + 1) / 2; j < i; j ++ )
            ret += f[i - 1][j];

    return ret;
}

int main() {
    init();
    scanf("%d,%d", &l, &r);
    cout << dp(r) - dp(l - 1);
    return 0;
}