# C

# 题目大意

初始时，有 $n$ 个苹果，我要吃 $k$ 个苹果
每次我可以花费 $1$ 把一堆苹果分成 $\lfloor{\frac{x}{2}}\rfloor$ 和 $\lceil{\frac{x}{2}}\rceil$，如果恰好出现了 $k$，则我就会吃，问我的最小花费

# 数据范围

• $1 \le n, k \le 10^9$

# 题解

可以发现，每一层都是递减的，也就是说，$i$ 层的最小值不会小于 $i-1$ 层的最大值，所以我们可以从顶层往下遍历，维护每层最小值 $l$ 和最大值 $r$，直到搜到 $k$ 或 $l, r$ 搜完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void solve() {
    cin >> n >> k;

    if (n == k) {
        cout << 0 << '\n';
        return;
    }

    int l = n, r = n;

    for (int i = 1; i <= 30; i++) {
        l = l / 2, r = (r + 1) / 2;

        if (l <= k && k <= r) {
            cout << i << '\n';
            return;
        }
    }

    cout << -1 << '\n';
}

# D

# 题目大意

给定整数 $n,~n = 2^d$，其中 $d$ 是非负整数，可以任意从中选取一个整数 $x$
现在有两种操作

1. $x = x / 2$，仅当 $x$ 是偶数时候可以进行此操作
2. $x = x - 1$，随意操作
   请问 $1->n$ 中，有多少个 $x$，在经过 $k$ 次操作时候，仍不未 $0$（操作人绝顶聪明）

# 数据范围

• $1 \le n,k \le 10^9$

# 题解

对于绝顶聪明的操作者来说，$x$ 想要变成 $0$，最优的操作肯定是
$\lfloor{\log_2 x}\rfloor + popcount(x)$
也就是能减半就减半，不能减半的就是 $x$ 中的二进制表达形式中 $1$ 的个数（也就是说，一个数的操作次数是这个数在二进制下的位数加二进制下 $1$ 的数量再 $-1$）

那么我们可以去枚举 $len_2(x)$ 和 $cnt_1$
$n$ 是 $2$ 的 $d$ 次方，二进制是 $10..0$，其中 $0$ 有 $d$ 个
那我们不妨先对 $d - 1$ 去做，然后再特判下 $n$

对于 $1 \to (n - 1)_2(1..1)$，长度是 $d$
我们可以枚举长度 $len$，和 $1$ 的个数 $1 \to len$，然后要让第一个是 $1$，所以如果 $len + cnt_1 - 1 > k$，那么答案就加上 $C_{len - 1}^{cnt_1 - 1}$

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

void solve() {
    cin >> n >> k;

    int len = 0, nn = n, res = 0;
    while (nn)
        len++, nn >>= 1;

    for (int l = 1; l < len; l++) {
        for (int cnt1 = 1; cnt1 <= l; cnt1++)
            if (l + cnt1 - 1 > k)
                res += C[l - 1][cnt1 - 1];
    }

    cout << res + (len > k) << '\n';
}

这里学到了个初始化组合数（小范围）的新方法

1
2
3
4
5

for (int i = 0; i < 30; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
        C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}