CF1877E Autosynthesis

发布时间 2023-10-13 17:30:21作者: ydtz

总结题目约束其实就是,所选数下标组成的集合和未选数值组成的集合相同。

我们发现该约束把值和下标联系在了一起,所以我们不妨考虑建出图来显式地表示二者,即,我们由 \(i\)\(a_i\) 连边,然后考虑整张图。

首先这肯定是个内向基环树森林,然后我们要对其黑白染色,设黑色表示选择,白色表示未选择,则题目约束可转化为:

  • 对于一个白色点,其后继节点必须为黑色点。
  • 对于一个黑色点,其必然存在一个前驱节点为白色点。

故对于前驱节点集合没有白色节点的点,一定为白色;否则一定为黑色。

拓扑排序把所有链处理了,再在每个环上判一圈即可。如果判到矛盾即为无解。

对于模糊的约束,我们一定要尽可能地将其显式化,这关乎代码是否能清晰地一遍写对。