首页 > 其他分享 >CF1877E Autosynthesis

CF1877E Autosynthesis

时间:2023-10-13 17:35:30浏览次数:35  
标签:黑色 白色 CF1877E 约束 Autosynthesis 节点

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

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

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

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

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

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

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

标签:黑色,白色,CF1877E,约束,Autosynthesis,节点
From: https://www.cnblogs.com/ydtz/p/17762661.html

相关文章