题解

思路

可达前缀

若某个整数 $x$ 能在当前若干次操作后被染色，那么任意不大于 $x$ 的整数也能被染色。因此，只需记录当前能够染色的最右位置 $f$。

使用一项 $(a_i,b_i)$ 时：

• 可以直接染到 $a_i$；
• 若此前的最右位置为 $f$，可以借助不超过 $a_i$ 的位置，染到 $\min(f,a_i)+b_i$。

所以使用该项后的最右位置为

$$\max\bigl(f,a_i,\min(f,a_i)+b_i\bigr).$$

颜色 $1$ 放在最后不会更劣。若 $a_1\ge k$，答案立即为 YES；若 $a_1+b_1<k$，答案一定为 NO。其余情况下，只需让颜色 $2\sim n$ 先到达足够靠右的位置 $f$，最后检查

$$\min(f,a_1)+b_1\ge k.$$

子任务 1：枚举排列

枚举颜色 $2\sim n$ 的所有排列，按上述转移模拟最右位置，再检查颜色 $1$。复杂度为 $O(n!)$。

子任务 2：子集动态规划

令 $dp[S]$ 表示恰好使用集合 $S$ 中颜色后，最右位置的最大值。枚举下一个加入的颜色，并按可达前缀转移。因为转移关于旧的 $f$ 单调，只保留最大值不会丢失最优方案。

复杂度为 $O(n2^n)$，空间复杂度为 $O(2^n)$。

做法

满分算法

将颜色 $2\sim n$ 按 $a_i$ 从小到大排序，记排序后的项为 $(A_i,B_i)$。令 $f_i$ 表示只使用前 $i$ 项时能到达的最右位置。

第一项只能直接给出

$$f_1=A_1.$$

加入第 $i$ 项时，有四种必要候选：

1. 不使用新项扩张，保留 $f_{i-1}$；
2. 新项直接染到 $A_i$；
3. 先处理前缀，再用新项扩张到 $\min(f_{i-1},A_i)+B_i$；
4. 先用第 $i$ 项直接染到 $A_{i-1}$，再用第 $i-1$ 项扩张到 $A_{i-1}+B_{i-1}$。

于是

$$f_i=\max\left(f_{i-1},A_i,A_{i-1}+B_{i-1},\min(f_{i-1},A_i)+B_i\right).$$

正确性说明

考虑一个最优操作顺序。若相邻两项满足较小的 $a$ 在较大的 $a$ 之后，可以交换这两项；除“较大 $a$ 的项先提供跳板、较小 $a$ 的项随后使用自己的 $b$”这一情形外，交换不会使最右位置变差。这个唯一例外恰好产生候选 $A_{i-1}+B_{i-1}$。因此，前 $i$ 项的最优结果完全由上述四个候选覆盖，递推得到全局最优最右位置。

最后让颜色 $1$ 执行操作，判定 $\min(f,a_1)+b_1\ge k$ 即可。

复杂度

每组测试数据排序耗时 $O(n\log n)$，递推耗时 $O(n)$，空间复杂度为 $O(n)$。所有测试数据中 $n$ 的总和不超过 $10^5$。