AGC016E Poor Turkeys

题意简述：有\(N(2<=N<=400)\)只火鸡, 编号为1到N , 有\(M(1<=M<=10^5)\)个人, 每人指定了两只火鸡\((x,y)\)：
1.若\(x,y\)都活着, 那么这个人将会等概率地随机吃掉一只
2.若\(x,y\)恰好活着一只, 那么这个人将会吃掉活着的这只
3.若\(x,y\)都已经死亡, 那么只好什么都不做
求有多少个\((i,j)(1<=i<j<=N)\)满足在最终时刻第\(i\)只火鸡和第\(j\)只火鸡都还活着

又是一道比较巧妙的题。

我们可以考虑反着来考虑，假设在当前时刻要使第\(i\)只鸡活着应该怎么办。那我们考虑要使这只鸡活着，一定会杀掉别的鸡，那么我们对于每只鸡记录一个集合，表示要使\(i\)活着，要杀的鸡有哪些。然后如果存在一个人要杀的鸡已经被杀完了或只剩\(i\)，那么第\(i\)只鸡必死，因为每只鸡只能杀一次，我们又是从后往前考虑，那么在原序列中后面的就无法替\(i\)去死就先被杀了。

最后因为一只鸡不能死两次，我们再对所有的能活下来的鸡进行集合判交就可以啦。

#include<cstdio>
#include<bitset>
using namespace std;
const int N=410,M=1e5+10;
int n,m,ans;
int x[M],y[M],die[N];
bitset<N> s[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=n;i++){
        s[i][i]=1;
        for(int j=m;j;j--)
            if(s[i][x[j]]&&s[i][y[j]]){die[i]=1;break;}
            else if(s[i][x[j]])s[i][y[j]]=1;
            else if(s[i][y[j]])s[i][x[j]]=1;
    }
    for(int i=1;i<=n;i++)
        if(!die[i])
            for(int j=i+1;j<=n;j++)
                if(!die[j]&&(s[i]&s[j]).none())++ans;
    printf("%d\n",ans);
}

AGC016E Poor Turkeys

原文：https://www.cnblogs.com/yxc2003/p/10747233.html