UOJ Round#6 懒癌

题目大意

有\(n\)条狗，其中至少有一条得了懒癌。每个人可以看到一部分狗的情况，并且每天进行一轮推断

当它推断出自己的狗一定有懒癌时，就会将自己的狗枪毙，并且所有人停止推断。如果有多个人同时推断出则同枪毙

求在所有\(2^n-1\)种情况中，所有有狗被杀的情况中，一共过了多少天，枪毙了多少狗。

分析

首先考虑用状压\(dp\)来模拟所有的情况和转移，设\(dp_{S}\)表示集合\(S\)中的狗得了懒癌时的最小推断步数

我们考虑通过反推的方式进行转移，显然一个没有懒癌的狗永远不会被枪毙。

1. 边界条件：当一个人能看到所有狗，并且其他狗都没有懒癌时，直接枪毙，\(dp_S=1\)

2. 反证法：

   对于一个有懒癌的狗\(i\)进行反证

   1. 先假设自己的狗没有病
   2. 枚举所有可能的状态，即枚举所有看不到的狗是否得了病，得到后继状态集合\(\text{next}(S,i)\)
   3. 如果\(k\)步以内所有可能情况均已经达成了结束，在这个状态却没有，说明假设不成立，在\(k+1\)天就会枪毙自己的狗。

   此时，设所有可能状态集合为\(\text{next}(S,i)\)，则答案为\(dp_{S,i}=\max_{T\in\text{next}(S,i)}\{dp_T\}+1\)

3. 总转移：\(\displaystyle dp_{S}=\min_{i\in S} \{\max_{T\in\text{next}(S,i)}\{dp_T\}+1\}\)

所有不会成环的状态均有结束状态（这里并没有处理枪毙了多少狗）

简化转移

从上面的转移式中容易看出：

对于\(U\subseteq V\)，一定有\(dp_{U}\leq dp_V\)

故在转移时，不再需要枚举看不到的狗是否得了病，只需要考虑它们全部得病的情况。

转移出现环的性质

对于每个\(i\)看不到\(j\)的关系（\(i\ne j\)），从\(i\)向\(j\)连一条边，如果第\(i\)条狗有懒癌，则第\(i\)个点为黑点，否则为白点。

考虑简化之后的转移的过程，转移后继有着怎样的特点：

1. 选择了一个\(S\)中的元素\(i\)，并且将其删除；将\(i\)出边的所有点加入\(S\)
2. \(S\)中的元素均没有出边时，才能够保证到达边界状态

故在建成的图上，对于一个大小\(>1\)的强连通分量（也就是存在环的分量）

一旦其中出现了黑点，该状态就永远无法到达边界状态

同样的，如果一个点能够到达一个环，那么这个点也不能是黑点

将这些非法点剔除之后，设新的图为包含\(n\)个节点的\(\text{DAG}\)

在\(\text{DAG}\)上统计答案

上文已经提到了转移过程在\(\text{DAG}\)上的体现，那么考虑一个状态如何到达边界：

1. 选择某一个 没有其他黑点能到达 的黑点，将它删掉，加入它的出边

2. 当\(\text{DAG}\)上不存在黑点时，状态结束，1过程进行的次数就是答案

• 第一问

  只需要考虑每个点被进行1操作的次数。

  容易发现，如果有一个黑点能够到达\(i\)，\(i\)就会被操作一次。

  故只需要统计出有多少点能够到达\(i\)（包括\(i\)自己），设为\(f_i\)，答案就是\(\sum (2^{f_i}-1)2^{n-f_i}\)

• 第二问

  显然我们需要统计每一条狗被枪毙的次数。

  考虑上面的转移对应着一个怎样的推导过程：

  1. 在一开始的集合枚举了一个点\(i\)，得到一个后继状态
  2. 经过一系列后继状态的转移到达边界，发现矛盾
  3. 一开始被枚举的那个\(i\)被枪毙

  那么被枪毙的狗，实际上就是 某一个 没有其他黑点能到达 的黑点（也就是一开始的转移式中枚举的每一个最优的\(i\)）。

  容易发现答案就是\(\sum 2^{n-f_i}\)