清除病毒

子任务 1：用位掩码表示感染区域的集合。枚举三个不同区域，清除相应的位，再计算午夜同时传播后的状态。从全部感染的状态开始 BFS，找到空集并还原路径。使用位运算计算转移，时间复杂度为 $O(2^N N^3)$，空间复杂度为 $O(2^N)$。下面的构造保证存在不超过 $N$ 天的方案，因此 BFS 得到的最短路径也满足要求。

完整解法：令 $X=N-2$。第 $k$ 天中午清除区域 $1,k+1,k+2$ 的病毒（）。

若 $N=3$，第一天即可清除全部病毒。否则，对于 $1 \leq k \leq N-3$，第 $k$ 天午夜后没有病毒的区域恰好是 $[2,k+1$。第一天中午清除 ，午夜时两端重新感染，只剩区域 。归纳地，前一天留下的干净区间为 ，再清除 ，中午就得到干净区间 。午夜只有两端与区间外的感染区域相邻，因此留下 。

第 $N-2$ 天清除剩余的区域 $1,N-1,N$ 后，所有区域都没有病毒，也不会再发生传播。输出的三个编号总是互不相同且合法，所用天数满足 $N-2 \leq N$。

输出所需的时间复杂度为 $O(N)$，除输出缓冲区外，额外空间复杂度为 $O(1)$。校验器逐日模拟，时间复杂度为 $O(NX)$，空间复杂度为 $O(N)$。由于 $$，每个输入文件最多进行 次区域更新。

Solution written by GPT