【AtCoder Grand Contest 016 E】Poor Turkeys | Mrsrz's blog

DP，倒推。

题目大意：

有 $n$ 只鸡和 $m$ 个人，每个人有 $x_i$ 和 $y_i$。

对于一个人 $i$：

• 若鸡 $x_i$ 和 $y_i$ 都活着，则等概率选择一只杀了。
• 若鸡 $x_i$ 和 $y_i$ 只有一只活着，则杀了活着的那只。
• 若鸡 $x_i$ 和 $y_i$ 都死了，则什么都不干。

人会按照编号顺序行动。

问有多少对 $(i,j)$ 满足 $i\lt j$ 且最后编号为 $i$ 和 $j$ 的鸡有可能同时存活。

题解：

我们先钦定一只鸡 $i$ 必须活着，然后尝试推出到每一步时，要使鸡最终活着，还需要哪些鸡必须活着。

考虑倒推，令 $f_{i,j}$ 表示要使鸡 $i$ 活着，鸡 $j$ 是否必须活着。

一开始的状态为 $f_{i,i}=1$。

然后倒着枚举每一个人，并考虑以下情况：

• $f_{i,x_i}$ 和 $f_{i,y_i}$ 都为 $0$，即这个人操作后这两只鸡的死活和最终状态无关。那么之前也无关。
• $f_{i,x_i}$ 和 $f_{i,y_i}$ 中的一个位 $0$。那么这个人只能杀了另一个，所以令另一个为 $1$。
• $f_{i,x_i}$ 和 $f_{i,y_i}$ 都为 $1$。那么出现矛盾，说明鸡 $i$ 不可能活到最后。

我们发现，这些死亡是有先后顺序的，所以两只鸡的集合如果有交的话，这两只鸡不能同时存活。

然后，我们枚举两只能活到最后的鸡，看下是否无交即可。可以用 bitset 优化。

时间复杂度 $O(nm+\frac{n^3}\omega)$。

Code：

#include<bitset>
#include<iostream>
using namespace std;
const int N=405;
bitset<N>f[N],g;
int n,m,U[N*N],V[N*N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i)cin>>U[i]>>V[i];
    for(int i=1;i<=n;++i){
        f[i].set(i);
        for(int j=m;j;--j)
        if(f[i].test(U[j])&&f[i].test(V[j])){g.set(i);break;}else
        if(f[i].test(U[j]))f[i].set(V[j]);else
        if(f[i].test(V[j]))f[i].set(U[j]);
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    if(!g[i])
    for(int j=i+1;j<=n;++j)
    if(!g[j]&&(f[i]&f[j]).none())++ans;
    cout<<ans;
    return 0;
}