题目分析

这是一个带有时间限制的 恰好装满的 0/1 背包问题。

对于每个查询 $(m, k, s)$，我们需要判断是否存在物品子集：

1. 总价值 恰好等于 $k$
2. 所有选中物品在时间区间 $[m, m+s]$ 内全程可用：
   • 放入时间 $a_i \le m$（在闯入时已放入）
   • 取回时间 $b_i > m + s$（在离开前未被取走）

核心思路

1. 离线处理

• 将物品按放入时间 $a_i$ 升序排序
• 将查询按闯入时间 $m_j$ 升序排序
• 使用 双指针 维护当前可用的物品集合

2. 动态规划状态设计

定义状态： [ f[k] = \text{在总价值恰好为k时，所选物品中最小的}b_i\text{的最大值} ]

解释：在能凑出价值 $k$ 的所有方案中，最晚的取回时间。

初始值：

• $f[0] = +\infty$（凑出价值 $0$ 总是可行）
• $f[k] = 0$，$k > 0$（初始不可行）

3. 状态转移

当加入物品 $(c_i, a_i, b_i)$ 时：

for k from 100000 down to c_i:
    if f[k-c_i] > 0:  // 说明k-c_i可行
        new_time = min(f[k-c_i], b_i)
        f[k] = max(f[k], new_time)

含义：

• min(f[k-c_i], b_i)：新方案的最晚取回时间受限于当前物品的 $b_i$ 和之前方案的最晚时间
• max(f[k], ...)：保留所有方案中最优的（最晚的）取回时间

4. 查询判断

对于查询 $(m, k, s)$：

• 如果 $f[k] > m + s$，说明存在方案能在 $m+s$ 时刻前完成
• 输出 TAK，否则输出 NIE

算法流程

1. 输入与排序

   • 读入 $n$ 个物品，按 $a_i$ 排序
   • 读入 $Q$ 个查询，按 $m_j$ 排序

2. 双指针处理

   j = 1  // 物品指针
   for i = 1 to Q:  // 遍历查询
       while j <= n and t[j].a <= q[i].m:
           将物品t[j]加入DP
           j++
   

3. DP更新

   • 使用上述状态转移方程更新 $f$ 数组

4. 查询回答

   • 检查 $f[k]$ 是否满足 $f[k] > m + s$

复杂度分析

• 时间复杂度：$O(n \cdot K + Q \log Q)$
  • $n$ 次物品加入，每次 $O(K)$，$K = 100,000$
  • 排序 $O(n \log n + Q \log Q)$
• 空间复杂度：$O(K + Q)$

样例验证

输入：

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

处理过程：

输出：

TAK
NIE
TAK
TAK
NIE

关键优化点

1. 离线处理：避免对每个查询重新计算背包
2. 状态设计：$f[k]$ 同时记录可行性和时间约束
3. 双指针：线性处理物品和查询的添加
4. 贪心思想：记录最晚取回时间，为后续查询提供更多可能性

总结

这种解法充分利用了：

• $n$ 较小 ($\le 1000$) 而 $Q$ 很大 ($\le 10^6$) 的特点
• $k_j$ 范围有限 ($\le 10^5$) 的条件
• 通过巧妙的 DP 状态设计同时处理了 价值要求 和 时间约束