大模拟？小 2-SAT

Rosmist · 2024-11-10 22:21:13 · 题解

不是纯模拟题，怎么会呢？

当没有 TRIGGER 和 TOGGLETRIGGERREPLACE 指令时，这道题就是一道很容易的模拟题。

我们记 f_i 为 i 号机器人的「指令」的编号，初始时，令 f_i=i。

接着，按顺序处理每一条「指令」的输出信息。根据输出信息，我们得知该「指令」的编号为 f_{\text{id}}，并据此完善该「指令」的类型、左手/右手等信息。然后，如果该「指令」是 SWAP，我们交换 f_{\text{id2}} 和 f_{\text{id3}}；如果是 MOVE，也进行相应的修改。

最后，按顺序输出初始时 i 号机器人的「指令」（即编号为 i 的「指令」）的详细信息。若仍有不确定的信息，说明该信息是无关紧要的，随意输出一个合理值即可。

而 TRIGGER 和 TOGGLETRIGGERREPLACE 指令使问题复杂起来。

首先，TOGGLETRIGGERREPLACE 指令产生的两条新「指令」，我们用和其他「指令」不同的编号表示它们。被 TOGGLETRIGGERREPLACE 指令「切换」的「指令」前后大部分信息相同而编号不同，这些信息可以记录在同一个地方，以避免两条「指令」的信息的不同步。

对于 TRIGGER，容易知道，TRIGGER 指令的触发和非 TRIGGER 指令的执行可能产生相同的输出信息，因此输出信息为 <COMMANDNAME> 的「指令」有 TRIGGER <ANOTHERCOMMANDNAME>: <COMMANDNAME> 或 <COMMANDNAME> 两种可能的形式。

具体地，我们发现：

• 只有「当一个其他机器人『执行』完一条『指令』之后，且『右手』指向自己的时候」，自己的 TRIGGER 指令才可能被触发。
  • 从而，一条「指令」最多触发一条 TRIGGER 指令。
  • TRIGGER <COMMANDNAME（非 TRIGGER）> 指令的上一条执行的「指令」一定是 <COMMANDNAME> 或 TRIGGER <ANOTHERCOMMANDNAME>: <COMMANDNAME> 指令。
  • 输出信息为 <COMMANDNAME> 的「指令」的下一条执行的「指令」如果是 TRIGGER，则下一条「指令」要么是 TRIGGER <COMMANDNAME>，要么是 TRIGGER TRIGGER。
  • 一个机器人「执行」完一条输出信息为 <COMMANDNAME> 的「指令」之后，若这是最后一条「指令」或「右手」不指向下一条「指令」的执行者，
    • 若这不是最后一条「指令」，则下一条「指令」一定不是 TRIGGER 指令；
    • 若「右手」不指向它自己，则其「右手」指向的机器人的「指令」一定不是 TRIGGER <COMMANDNAME> 指令。

对于每条「指令」，我们根据上述结论维护「若这条『指令』是 TRIGGER <COMMANDNAME>，<COMMANDNAME> 可能的选择集合」。

假如一条「指令」是 TRIGGER，而且根据上述「选择集合」，它既可能是 TRIGGER <COMMANDNAME（非 TRIGGER）>，又可能是 TRIGGER TRIGGER，那么这条「指令」一定可以是前者，不必额外考虑后者的情况。

假如一条「指令」是 TRIGGER，但是根据上述「选择集合」，它只可能是 TRIGGER TRIGGER，由于在处理输出信息的过程中，我们并不知道每条「指令」是否一定是 TRIGGER，从而不能确定触发这条「指令」的「指令」是否都是 TRIGGER，因此我们需要再进行一遍处理：

• TRIGGER TRIGGER 指令的上一条执行的「指令」一定是 TRIGGER 指令。
  • 非 TRIGGER 指令的下一条执行的「指令」一定不是 TRIGGER TRIGGER 指令。
• 一个机器人「执行」完 TRIGGER 指令之后，若这是最后一条「指令」或「右手」不指向下一条「指令」的执行者，且「右手」不指向它自己，则其「右手」指向的机器人的「指令」不是 TRIGGER TRIGGER 指令。

因为这样的「指令」如果是 TRIGGER，则一定是 TRIGGER TRIGGER，所以可以直接据此判断其是否可以是 TRIGGER。

我们再配合另外的限制：

• 若对一条「指令」维护的「选择集合」是空集，则这条「指令」不是 TRIGGER 指令。
• 被 TOGGLETRIGGERREPLACE 指令「切换」的「指令」前后有且仅有一个是 TRIGGER 指令。

对于每条「指令」是否是 TRIGGER 指令，我们根据上述有关限制建立 2-SAT 模型并求解，根据结果输出即可。

总的流程是：

1. 遍历并处理每一条「指令」的输出信息。
   1. 完善该「指令」的信息。
   2. 根据该「指令」和上一条「指令」之间的关系，维护「选择集合」。
   3. 实现该「指令」本身执行时的效果。
2. 注意处理最后一条「指令」对「选择集合」的影响。
3. 根据有关限制建立 2-SAT 模型。
   • TOGGLETRIGGERREPLACE 指令的限制可以直接在遍历时处理。
4. 求解 2-SAT。
5. 输出结果。
   • 注意某些无关紧要的信息，如 TOGGLETRIGGERREPLACE h <COMMANDNAME> <NEWCOMMAND> 对 TRIGGER 指令「切换」时 <COMMANDNAME> 的内容，任意「指令」名称都是可以的。

代码丑。