首页 > 其他 > 详细

AGC016E Poor Turkeys

时间:2019-04-21 22:01:14      阅读:105      评论:0      收藏:0      [点我收藏+]

题意简述:有\(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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!