Colton Star Blog

动态规划 — 能力闯关问题#

题目大意：初始有 $w$ 点能力值，$x$ 枚金币。依次闯过 $n$ 个关卡，每关包含课程和考试两个阶段：

• 学习课程需花费 $c_i$ 金币，获得 $\Delta w_i$ 能力值提升
• 考试得分 = 当前能力值

求在金币有限的前提下，最大化考试总得分。

赛时思路：用两个状态做滚动数组——选这门课 / 不选这门课，转移到下一门课。方向是对的，但当时没做出来。

问题分析：

每关的决策影响后续所有关卡的收益，这也是赛时卡住的核心——能力值是动态变化的，朴素 DP 需要同时记录「当前能力值」和「剩余金币」，维度太高。

关键转化：

总得分 = $\sum_{k=1}^{n}$（初始 $w$ + 第 $k$ 关之前所有已学课程的 $\Delta w$ 之和）

拆开来看，初始 $w$ 贡献固定为 $w \times n$。而每个课程 $\Delta w_i$ 的贡献取决于它被学完之后，后面还剩多少关考试——即每学一门课，它会在之后每一关都发挥作用。

因此第 $i$ 关的课程贡献 = $\Delta w_i \times (n - i)$。$(n - i)$ 其实就是后缀和——第 $i$ 关之后还剩多少关考试，这门课的提升会在之后每一关都生效。

这就转化成了 01 背包问题：

• 物品：每个关卡一门课
• 价值：$\Delta w_i \times (n - i)$（后缀关卡数）
• 重量：$c_i$
• 目标：背包容量 $x$ 内总价值最大

状态转移：

1
// dp[j] = 剩余 j 金币时的最大额外得分
2
int dp[x + 1] = {0};
3

4
for (int i = 0; i < n; i++) {
5
    int value = delta_w[i] * (n - i);  // 后续关卡数
6
    int cost = c[i];
7
    for (int j = x; j >= cost; j--) {
8
        dp[j] = max(dp[j], dp[j - cost] + value);
9
    }
10
}
11

12
int ans = w * n + dp[x];  // 基础分 + 额外分

反思：思路本身是对的（01 背包 + 滚动数组），赛时卡住的点在于没有把「能力值提升」正确换算成「总得分增量」。正确做法是算 $\Delta w_i \times$ 剩余关卡数，而不是在 DP 里维护能力值这个维度。

交互题 — 二进制数中 1 的个数#

题目大意：交互器生成一个长度为 $N$ 的二进制串（$N \le 2^{17}$）。你最多有 $17$ 次查询机会。每次查询选择一个下标集合 $S$，交互器返回：

其中 $\text{cnt}(X)$ 表示集合 $X$ 中值为 $1$ 的位数，$\complement S$ 是 $S$ 的补集。

目标：求出整个二进制串中 $1$ 的总数 $K$。

关键观察：

设总共有 $K$ 个 $1$，查询集合 $S$ 中有 $x$ 个 $1$，补集中有 $K-x$ 个 $1$。交互器返回：

这是一个关于 $x$ 的二次方程：$x^2 - Kx + P = 0$，解得：

即 $x$ 要么是某个值 $c$，要么是 $K - c$。

查询策略 — 为什么二进制分组可行：

将 $N$ 个位置从 $0$ 开始编号。第 $j$ 次查询（$0 \le j \le 16$）选择所有「下标第 $j$ 位为 $1$」的位置：

1
查询 j: 所有满足 (i >> j) & 1 == 1 的位置 i

核心思想：二进制位的正交性。

每个下标 $i$ 有一个唯一的 $17$ 位二进制表示。第 $j$ 位是 $1$ 还是 $0$，决定了 $i$ 是否进入第 $j$ 次查询的集合。这就像傅里叶变换里的 $\sin$ 和 $\cos$ 基函数——它们是正交的：

不同二进制位之间的 $0/1$ 标记天然构成了一组正交基。每一位的查询独立地刻画了全体 $1$ 在该位上的分布特征，互不干扰。

换个角度理解：对于任意两个不同的下标 $i \neq i'$，它们的二进制表示至少有一位不同，即至少存在一次查询 $j$，使得「$i$ 进入查询 $j$ 而 $i'$ 不进入」（或反之）。

这意味着：不存在两个下标在所有 $17$ 次查询里有完全相同的进出模式。每个位置的「$17$ 位查询签名」就是它自身编号的二进制表示，天然不重复。

这正是正交性的直观含义——每次查询在不同的「维度」上切分下标空间，$17$ 个维度互不重叠、互不包含，共同唯一确定了 $2^{17}$ 个位置。

信息论视角：

这个问题本质上是一个信息传输问题。二进制串有 $K$ 个 $1$，相当于要从 $N$ 个位置中恢复 $K$ 这个整数。$K$ 的取值范围是 $[0, N]$，用二进制表示需要 $\log_2(N+1)$ 比特的信息。

每次查询返回一个乘积 $P_j = c_j(K - c_j)$。由于我们不知道 $c_j$，单次查询并不能直接传递 $\log_2 N$ 比特——但 $P_j$ 本身是一个非负整数，且与 $K$ 和 $c_j$ 同时相关。在正确的分组策略下，每条查询提供了约 $1$ 比特的有效信息（确定 $c_j$ 在两个可能值中的哪一个），$17$ 条恰好传递 $17$ 比特，刚好覆盖 $\log_2 N \le 17$ 的信息量上限。

而模余数分组之所以失败，从信息论看是因为查询之间存在互信息（mutual information）：

嵌套结构导致后一条查询的信息大部分已被前一条包含，$17$ 次查询实际提供的独立信息远小于 $17$ 比特，不足以确定 $K$。二进制分组则保证了：

查询之间的互信息接近于零，每次查询的 $1$ 比特信息都是新鲜的——这就是正交性在信息论下的等价表述。

赛时为什么走了弯路：

我当时用的策略不是按二进制位分组，而是按模余数分组：

1
第 0 次查询: i % 2 == 1          （除以 2 余 1）
2
第 1 次查询: i % 4 == 1 或 2     （除以 4 余 1,2）
3
第 2 次查询: i % 8 ∈ {1,2,3,4}  （除以 8 余 1,2,3,4）
4
...

这个方案的问题在于：这些查询不是正交的。第 $j$ 次查询的集合并不能表示为「所有第 $j$ 位为 $1$ 的位置」——它们之间存在大量重叠和包含关系，导致不同查询给出的方程冗余，无法独立提供信息。

具体来说，按模 $2^k$ 分组时，第 $k$ 次查询的集合完整包含了第 $k-1$ 次查询的集合，形成了嵌套结构。这意味着：

• $c_0 \subseteq c_1 \subseteq c_2 \subseteq \dots$
• 各次查询高度耦合，信息量远不如二进制分组

而二进制分组保证了 $17$ 次查询完全独立——每次查询给出的 $P_j = c_j(K - c_j)$ 在信息论意义下是互不冗余的，这正是正交性的威力。

求解步骤（逐步详解）#

拿到 $17$ 个 $P_j$ 之后，怎么求出 $K$？分三步走。

第一步：写出每条查询提供的方程

对于第 $j$ 次查询，设集合内恰有 $c_j$ 个 $1$，则：

注意：$c_j$ 和 $K$ 都是未知数。一条二次方程有两个未知数，无法直接解出。但 $17$ 条方程共享同一个 $K$，这个公共约束就是突破口。

第二步：把每条方程改写成 $c_j$ 关于 $K$ 的表达式

将 $(1)$ 整理为标准二次形式：

用求根公式解出 $c_j$：

此时的未知数只剩 $K$。但直接解这 $17$ 个联立方程很麻烦，更简单的做法是——枚举 $K$，逐一验证。

第三步：枚举 $K$，验证自洽性

$K$ 的范围是 $[0, N]$。对每个候选 $K$，检查两条：

条件 A：$K^2 - 4P_j$ 必须是完全平方数。设 $s_j = \sqrt{K^2 - 4P_j}$，则 $s_j$ 必须是整数。

因为 $c_j$ 是 $1$ 的个数，必须是整数。而根据 $(2)$，$c_j$ 是整数当且仅当 $\sqrt{K^2 - 4P_j}$ 是整数。

条件 B：$c_j = (K - s_j)/2$ 必须在 $[0, K]$ 内。

取减号那支就够了——另一支 $(K + s_j)/2$ 其实就是 $K - c_j$，是同一个值从补集视角看。

如果 $17$ 条方程全部通过，这个 $K$ 就是答案。

为什么枚举可行？

枚举量是 $O(N)$，每条方程检查是 $O(1)$，总计 $O(17N)$。题目中 $N \le 2^{17} \approx 1.3 \times 10^5$，$17N \approx 2.2 \times 10^6$，完全在时限内。

可以加速：$P_0$ 的方程 $c_0(K - c_0) = P_0$ 已经大大限制了 $K$——不是每个 $K$ 都能让 $K^2 - 4P_0$ 成为完全平方。实际枚举时绝大多数 $K$ 在第一轮就因判别式不满足而被跳过。

代码对应关系：

1
// 对每个候选 K
2
for (int K = 0; K <= n; K++) {
3
    bool ok = true;
4
    for (int j = 0; j < 17; j++) {
5
        // 条件 A：判别式是完全平方
6
        long long disc = 1LL * K * K - 4 * P[j];
7
        if (disc < 0)      { ok = false; break; }  // 不含实根
8
        long long sq = sqrt(disc);
9
        if (sq * sq != disc) { ok = false; break; } // 不是完全平方
10

11
        // 条件 B：c_j 在合法范围内
12
        long long c = (K - sq) / 2;
13
        if (c < 0 || c > K)  { ok = false; break; }
14
    }
15
    if (ok) {
16
        cout << "! " << K << endl;  // ← 找到答案
17
        return 0;
18
    }
19
}

直观理解：

想象你手里有 $17$ 条「规则」，每条规则说「如果你告诉我总共有 $K$ 个 $1$，我就能告诉你第 $j$ 位为 $1$ 的那些位置里有多少个 $1$」。你挨个试 $K = 0, 1, 2, \dots, N$，看哪个 $K$ 能让所有 $17$ 条规则同时说得通。只有真正的 $K$ 能让所有方程同时给出整数解——这就是自洽性检验。

参考代码：

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int query(const vector<int>& s) {
5
    if (s.empty()) return 0;
6
    cout << "? " << s.size();
7
    for (int x : s) cout << " " << x;
8
    cout << endl;
9
    int ans; cin >> ans;
10
    return ans;
11
}
12

13
int main() {
14
    int n;
15
    cin >> n;  // 二进制串长度
16

17
    // 17 次查询：按二进制位分组
18
    vector<long long> P(17);
19
    for (int j = 0; j < 17; j++) {
20
        vector<int> s;
21
        for (int i = 0; i < n; i++) {
22
            if ((i >> j) & 1) s.push_back(i);
23
        }
24
        P[j] = query(s);
25
    }
26

27
    // 枚举 K（总共有 K 个 1），验证所有方程是否自洽
28
    for (int K = 0; K <= n; K++) {
29
        bool ok = true;
30
        for (int j = 0; j < 17; j++) {
31
            long long disc = 1LL * K * K - 4 * P[j];  // 判别式
32
            if (disc < 0) { ok = false; break; }
33
            long long sq = sqrt(disc);
34
            if (sq * sq != disc) { ok = false; break; }
35
            // c 必须是整数且在 [0, K] 范围内
36
            long long c = (K - sq) / 2;
37
            if (c < 0 || c > K || c * (K - c) != P[j]) {
38
                ok = false; break;
39
            }
40
        }
41
        if (ok) {
42
            cout << "! " << K << endl;
43
            return 0;
44
        }
45
    }
46
    return 0;
47
}

注意：实际交互中 $N$ 可能较大，枚举 $K$ 时可以利用「$P_0 = c_0(K - c_0)$ 且 $c_0$ 为整数」直接缩小 $K$ 的候选范围，避免 $O(N)$ 枚举。

二分答案 — 雪糕生产线#

这一题意难平。开赛时看到很多人都迅速过了，心想这题应该很简单，结果罚时两发，遗憾没有省一。

题意：有 $n$ 台机器，第 $i$ 台生产一根雪糕需要 $t_i$ 分钟。问生产 $m$ 根雪糕至少需要多少分钟。

本来思路（错）：算速度——拿 $1/t_i$ 表示第 $i$ 台机器每分钟能做多少根，然后累加求总速度。但这里有浮点陷阱：假如两台机器各每分钟做 $0.5$ 根，$0.5+0.5=1$，看起来一分钟能做一根。但实际上每台机器独立工作 1 分钟，第一根雪糕在哪台都没完成（$1 < t_i$），一根都出不来。

正解：二分时间 $T$，检验在 $T$ 分钟内能否生产 $\ge m$ 根。第 $i$ 台机器的产量 = $\lfloor T / t_i \rfloor$（整数除法）。

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
const int N = 1e6 + 5;
6
int n, m;
7
int t[N];
8

9
// 检查在 k 分钟内能否生产 m 根
10
bool check(ll k) {
11
    ll cnt = 0;
12
    for (int i = 0; i < n; i++) {
13
        cnt += k / t[i];
14
        if (cnt >= m) return true;    // 提前剪枝，防爆 long long
15
    }
16
    return cnt >= m;
17
}
18

19
int main() {
20
    cin >> n >> m;
21
    for (int i = 0; i < n; i++) cin >> t[i];
22

23
    ll l = 0, r = 1e18, ans = -1;     // r 开大：m 根 × 最慢机器
24
    while (l <= r) {
25
        ll mid = l + (r - l) / 2;
26
        if (check(mid)) {
27
            ans = mid;
28
            r = mid - 1;
29
        } else {
30
            l = mid + 1;
31
        }
32
    }
33
    cout << ans << "\n";
34
    return 0;
35
}