【题解】Atcoder AGC#16 E-Poor Turkeys
2021-07-03 07:05
标签：getch define else efi == 解法 names 不能 getchar %拜！颜神怒A此题，像我这样的渣渣只能看看题解度日╭(╯^╰)╮在这里把两种做法都记录一下吧~ 题解做法：可以考虑单独的一只鸡 u 能否存活。首先我们将 u 加入到集合S。然后我们按照时间倒序往回推，如果在时间 t 的时候发现有 u 和 v 同时被抉择，为了保证 u 的存活我们只能杀掉 v，也就是说在 t - 1的时刻 v 必须存活。这时我们将 v 加入到集合 S 中，再继续进行这个过程。如果在某个时刻我们发现 u 和 v 同时被抉择，可 u 和 v 都已经在集合中出现过了（要求在这个时刻一并存活），这样显然是非法的。所以可以判定 u 没有存活的可能。 如果一只鸡 u 能够存活，我们把这个过程中获得的 S 集合称作 \(S_{u}\) 。u 和 v 能够共存的充要条件即为 u 和 v 均有存活的可能，且 \(S_{u}\) 和 \(S_{v}\) 两个集合不存在交集。为什么呢？因为一只鸡在 t 时刻出现在了 S 集合中，说明它将在 t 时刻被杀掉。如果两个集合中 x 出现的时间不同，那么出现了冲突；但它们又不可能在同一个时间出现，因为一个时间节点只有唯一的一个抉择，反推回去也必然都是一样的，但开始的节点一个是 u，一个是 v，所以不可能。得证。 代码： 下面是颜神的解法（并没有代码...）也非常的妙，而且复杂度比题解还低……可以考虑建出一张图，在这张图上面所有有连边的鸡均无法共存来获得答案。那么如何建出这张图？一个人选择了 u 和 v 这两只鸡，那么这两只鸡是一定不可能共存的。假设我们在 t - 1 时刻建出的图满足在 t - 1 时刻及之前出现的所有抉择所限制不能共存的鸡均有连边，那么考虑加入t时刻的抉择之后会对这张图产生什么影响。 考虑 u 和 v 的抉择，会使哪些原本可以和 u 共存的鸡不能再和 u 共存？如果图中的一只鸡 x 与 u 没有连边，也与 v 没有连边，那么它与 u 的生死无关；如果一只鸡 x 与 v 有连边，而与 u 没有连边，说明 u 和 x 不能共存，我们添加一条从 u 到 x 的边。因为 x 与 v 不能共存，所以若 x 存活，v 一定死亡。那么新的 u,v 边一定会导致 u 的死亡；若 x 死亡，那么 u 可能依然存活，也可能已经死亡；但在这两种情况下，x 都不能与 u 共存。对于 v 我们也是一样的添边。 最后检查一下哪些节点是可以共存的即可。 【题解】Atcoder AGC#16 E-Poor Turkeys 标签：getch define else efi == 解法 names 不能 getchar 原文地址：https://www.cnblogs.com/twilight-sx/p/9901626.html#include
文章标题：【题解】Atcoder AGC#16 E-Poor Turkeys
文章链接：http://soscw.com/index.php/essay/101150.html