前两题十分顺利，第三题磕绊但也完成（题目也没卡我dfs），第四题思路大部分正确，可惜思考时间太久。

3821. 二进制中恰好K个1的第N小整数

题目简短，却蕴含技巧。

前置知识：组合数

并非讲什么是组合数，而是讲如何求组合数，毕竟使用公式需要用到阶乘，十分容易溢出。我们利用组合数递推式：

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

开一个二维数组 C[][] ，其中 C[i][j] 表示 $\binom{i}{j}$ ，然后利用递推式进行预处理。哦对，记得开long long类型。

for (int i = 0; i <= 60; ++i) { // i的上界不要太大，不然溢出，根据题意而定
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
}

思路

从高位到低位枚举，填 1 后我们就可以确定剩下的位数中 1 的个数，然后计算出有多少种组合数，如果小于 n 则说明第 n 小的数不在这些组合中，我们将该位填 0 并继续往低位枚举，否则将该位填 1 并更新 n 。

long long nthSmallest(long long n, int k) {
    long long result = 0;
    for (int i = 49; i >= 0; --i) {
        if (k == 0)
            break;                 // 如果已经填满k个1，直接退出
        long long count = C[i][k]; // 计算剩余i位中选k个1的组合数
        if (count < n) {
            n -= count;           // 第n小不在这些组合中，更新n
            result |= (1LL << i); // 将该位填1
            k--;                  // 还需要填k-1个1
        }
    }
    return result;
}

最后代码就是这么短，我也不知道为什么赛时思考路径会那么复杂。感觉还是个冒充hard的medium题。

3820. 树上的勾股距离节点

再讲一个典型的思考问题的方式，有点像昨天笔记提到的那个 2026 。这道题就是暴力搜索，没有捷径，但是搜索的对象有大大的“捷径”。

思路

正常暴力我们肯定想搜索每个节点，然后再进行dfs/bfs来确定到三个目标点的路径，判断是否勾股，但这个时间复杂度是必然爆炸的。

我们换种思路，对三个目标节点进行全图的dfs/bfs，将它们到每个节点的距离存入数组，这样我们就能在 $O(1)$ 的时间内获取每个节点到目标节点的距离，从而判断是否满足勾股条件。而搜索过程也只是三个节点的dfs/bfs的时间复杂度。

下面贴出丑丑的赛时代码

class Solution {
public:
    using ll = long long;
    ll dx[100024], dy[100024], dz[100024];
    int specialNodes(int n, vector<vector<int>>& edges, int x, int y, int z) {
        vector<vector<int>> G(n);
        for (auto &v : edges) {
            G[v[0]].push_back(v[1]);
            G[v[1]].push_back(v[0]);
        }
        vector<bool> visited(n, false);
        auto dfs = [&](auto&& self, int u, ll du[], int d) -> void {
            du[u] = d;
            visited[u] = true;
            for (auto v : G[u]) {
                if (visited[v] == true) continue;
                self(self, v, du, d + 1);
            }
        };
        dfs(dfs, x, dx, 0);
        visited.assign(n, false);
        dfs(dfs, y, dy, 0);
        visited.assign(n, false);
        dfs(dfs, z, dz, 0);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            vector<ll> t = {dx[i], dy[i], dz[i]};
            sort(t.begin(), t.end());
            if (t[0] * t[0] + t[1] * t[1] == t[2] * t[2]) {
                ans++;
            }
        }
        return ans;
    }
};