UR#6题解

【智商锁】
【懒癌】
神题一道。
题意简化版是有一个N户人家的村庄,每户人家养有一只doge,现在每个人都已知有至少1条狗患病。他们每天早上都会出去查看其它人家的狗是否患病,且如果推断出自己家狗患病会在当天下午6点枪毙了它。人们一旦听到枪声就不再戮杀可爱的doge。请问有多少只狗死了以及开枪在哪一天。人与人之间最基本的信任呢?村民间相互是否能看见其他狗患病构成一张有向图,并且所有人都知道这一张有向图。

对于完全图,如果有K只狗患病,那么将在第K天下午这K只狗一同丧命归西。

对于任意有向图,我们令为患病集合为i时最早响枪时间。那么枚举i中的每位患病狗主人,他肯定会对自己无法看见的狗且自己狗不生病的的所有情况进行枚举,从中取得最大值,实质是最长链。即是

时间复杂度.

显然这是不能通过全部测试点的。我们寻找更加有效的多项式算法。

我们将原图的补图进行处理,将所有点数大于1的强连通分量及其出、入边删掉,这样剩下一个DAG。
对于这个DAG来说,有一些点被染上黑色,其余点是白色。每次可以将一个黑色节点洗白,且可以将与其相连的节点染黑。这个模型与原问题等价。每一次操作实质是DP中转移的一条边,而最终状态是全为0,每次操作可以染白一个黑点,操作次数最大即取得最大值,也是染黑节点数最大。

所以问题转化为一个点集在DAG中最多能够到达的点数。

第一问。算单点贡献,所有子集中只有包含能到达i的点就能计入贡献,所以i的贡献为
第二问。死狗数量等价于开枪的主人数量,如果有能到达某点i的患病狗主人在熄灭i点后才进行操作,那么先熄灭i点一定没取min,所以我们选择一个患病状态集合中,没有其他患病点能够到达的点作为起始点进行操作,对应着一个开枪的狗主人。所以最后答案为

最后用bitset压位DP可以AC。