第 1 题

“没有上司的舞会”中，f[x][1] 表示 x 参加时子树的最大快乐值，f[x][0] 表示 x 不参加时的最大快乐值，y 是 x 的儿子。f[x][0] 的转移是（　　）

{{ select(1) }}

• f[x][0] = Σ f[y][0]
• f[x][0] = Σ max(f[y][0], f[y][1])
• f[x][0] = Σ f[y][1]
• f[x][0] = r[x] + Σ f[y][0]

---

第 2 题

“选课”用树上背包：f[x][j] 表示在 x 的子树里选 j 门课（x 必须选）的最大学分。合并儿子 y 时写成

for (int j = n + 1; j >= 2; j--)
    for (int k = 1; k <= j - 1; k++)
        f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);

其中 j 从大到小枚举的原因是（　　）

{{ select(2) }}

• 让程序跑得更快
• 防止数组下标越界
• 保证 f[x][0] 的值正确
• 保证同一棵子树 y 只被用一次（和 01 背包倒序是同一个道理）

---

第 3 题

状压 DP 中，用二进制数 S 表示一行里哪些格子放了东西。“这一行没有两个相邻的格子都放了东西”的判断是（　　）

{{ select(3) }}

• (S & (S << 1)) == 0
• (S | (S << 1)) == 0
• (S ^ (S >> 1)) == 0
• (S & (S - 1)) == 0

---

第 4 题

“最短 Hamilton 路径”n = 20，开数组 int f[1 << 20][20]，这个数组大约占（　　）内存

{{ select(4) }}

• 8 MB
• 20 MB
• 80 MB
• 800 MB

---

第 5 题

“互不侵犯”中，国王会攻击周围 8 个格子。上一行状态 a、这一行状态 b，两行之间互不攻击的条件是（　　）

{{ select(5) }}

• (a & b) == 0
• (a & b) == 0 && (a & (b << 1)) == 0 && (a & (b >> 1)) == 0
• (a | b) == 0
• (a & (b << 1)) == 0 && (a & (b >> 1)) == 0

---

第 6 题

数位 DP 求区间 [X, Y] 里满足条件的数有多少个。设 calc(n) 表示 [0, n] 里满足条件的个数，答案是（　　）

{{ select(6) }}

• calc(Y) - calc(X - 1)
• calc(Y) - calc(X)
• calc(Y - X)
• calc(Y) - calc(X) + 1

---

第 7 题

统计 Windy 数（相邻两位数字之差至少为 2）时要单独处理前导零。原因是（　　）

{{ select(7) }}

• 前导零会让数组越界
• 不处理的话会把 0 算进答案
• 例如 13 补成 013 后，0 和 1 相差 1，会被误判成不是 Windy 数
• 前导零会让答案多出一倍

---

第 8 题

“奶牛玩杂技”：每头牛有体重 w 和力量 s，叠成一列，一头牛的压扁指数 = 它上面所有牛的体重和 − 它的 s。要让最大的压扁指数最小，从上到下的顺序应该是（　　）

{{ select(8) }}

• 按 w 从小到大
• 按 s 从大到小
• 按 w + s 从小到大
• 按 w − s 从小到大

---

第 9 题

“任务与期限”：n 个任务都要做，第 i 个耗时 a[i]、期限 d[i]，完成时刻为 f 时得 d[i] − f 分（可以是负数），求总分最大。正确的贪心是（　　）

{{ select(9) }}

• 按期限 d 从小到大做
• 按耗时 a 从小到大做
• 按 d − a 从大到小做
• 按耗时 a 从大到小做

---

第 10 题

“无法组成的最小金额”：硬币面值是 1、2、4、9（每种一枚），不能凑出的最小正整数金额是（　　）

{{ select(10) }}

• 3
• 5
• 7
• 8