题目理解

Gleb 有 $P$ 本护照，要参加 $N$ 场训练营，每场训练营在不同国家。他需要在训练营开始前获得对应国家的签证。

关键约束：

• 申请签证当天必须在 Innopolis（不能在外出期间申请）
• 签证处理需要 $t_i$ 天
• 护照必须在手中（不能正在办理签证时使用）
• 训练营时间不重叠

问题转化

这是一个状态压缩动态规划问题，我们需要为每个训练营分配护照和申请时间。

设：

• $l[i] = s_i$（开始日期）
• $r[i] = s_i + len_i - 1$（结束日期）
• $t[i]$（签证处理时间）

状态：$dp[mask]$ 表示完成 $mask$ 集合中的训练营所需的最早完成时间。

状态设计

$dp[mask]$：处理完 $mask$ 中的训练营后，最早的可用时间。

转移：对于每个未处理的训练营 $j$，计算最早可以开始申请的时间，然后加上处理时间 $t[j]$。

关键算法

时间计算

对于当前状态 $i$ 和时间 $nowt$，要找到能申请训练营 $jj$ 的最早时间：

1. 跳过已占用的时间：

   • 跳过正在进行的训练营
   • 跳过训练营后的间隔期

2. 贪心推进时间：

   while (1) {
       int lst = nowt;
       // 跳过已开始的训练营
       while (le < n && r[idl[le]] < nowt) le++;
       while (lef < n && (!((i & (1 << idl[lef])) || idl[lef] == jj) || l[idl[lef]] < nowt))
           lef++;
       
       if (le < n && l[idl[le]] <= nowt)
           nowt = r[idl[le]] + 1;
       if (lef < n && l[idl[lef]] <= nowt + t[jj])
           nowt = r[idl[lef]] + 1;
       
       if (lst == nowt) break;
   }
   

状态转移

if (nowt + t[jj] < l[jj] && nowt + t[jj] < dp[i | (1 << jj)]) {
    dp[i | (1 << jj)] = nowt + t[jj];
    fro[i | (1 << jj)] = jj;
}

代码实现解析

预处理

// 按开始时间排序
sort(idl, idl + n, cmp1);
// 按处理时间排序（贪心优化）
sort(idt, idt + n, cmp2);

单本护照情况

if (p == 1) {
    if (dp[W] > 2e9) puts("NO");
    else {
        puts("YES");
        solve(W);  // 回溯方案
        for (int i = 0; i < n; i++)
            printf("1 %d\n", ans[i]);
    }
}

两本护照情况

for (int i = 0; i <= W; i++) {
    if (dp[i] > 2e9 || dp[W ^ i] > 2e9) continue;
    // 找到可行的分割方案
    solve(i); solve(W ^ i);
    puts("YES");
    // 分配护照
    for (int j = 0; j < n; j++) {
        if (i & (1 << j)) printf("1 %d\n", ans[j]);
        else printf("2 %d\n", ans[j]);
    }
    return 0;
}
puts("NO");

算法复杂度

• 状态数：$O(2^N)$
• 每个状态的转移：$O(N^2)$（由于内层循环）
• 总复杂度：$O(2^N \cdot N^2)$

对于 $N \leq 22$，状态数约 $4 \times 10^6$，在可接受范围内。

优化技巧

1. 状态压缩：用 bitmask 表示已处理的训练营
2. 贪心排序：按处理时间排序优化转移顺序
3. 时间跳跃：快速跳过不可用时间段
4. 两本护照分割：枚举所有可能的分割方案

算法标签

• 状态压缩动态规划
• 贪心算法
• 位运算
• 回溯构造

代码总结

核心思想是通过状态压缩DP计算最早完成时间，然后回溯得到具体方案。对于两本护照的情况，枚举所有可能的分割方式，检查是否都能完成。

该解法充分利用了$N \leq 22$的条件，通过状态压缩在合理时间内解决问题。