AT2389 [AGC016E] Poor Turkeys解题报告

解题报告

AT2389 [AGC016E] Poor Turkeys解题报告：

更好的阅读体验

题意

• 给定$n$只火鸡，$m$个操作，每次操作会选择两只火鸡$a,b$；
• 如果两只都活着，那么任意吃一只；如果只活了一只，那么吃剩下一只；如果两只都死了，那么不吃；
• 求数对$(i,j)$满足$i<j$且存在一种情况$i$和$j$同时活着的数量。
• 数据范围：$1\leqslant n\leqslant 400,1\leqslant m\leqslant 10^5$。

分析

神仙题。

我们设$f_{i,j}=1$（$i\ne j$）表示：如果$i$要活着，那么以后$j$一定要为$i$“抵命”。

可以用一个倒推的dp来$O(n^2)$求出$f$数组，具体地说：

• 枚举以后要存活的火鸡$i$，首先设边界$f_{i,i}=1$（很显然）。
• 然后，我们倒序枚举每一个操作$(a,b)$：
• • 如果$f_{i,a}=1$且$f_{i,b}=1$，那么意味着$a$和$b$以后一定要为$i$“抵命”，在这里不能死去，而这里有一次$(a,b)$操作，因此$a$和$b$一定不能两个同时存活，那么$i$以后一定活不了。
• • 如果$f_{i,a}=1$或$f_{i,b}=1$，那么不妨设$f_{i,a}=1$（如果$f_{i,b}=1$那么交换$a,b$），因为$a$以后要为$i$抵命，所以$b$一定得现在死来保护$a$。
• • 如果$f_{i,a}=0$且$f_{i,b}=0$，那么操作$(a,b)$与$i$无关，不需要考虑。

设$S(i)$为必须死去来抵$i$一命的集合。

然后，我们枚举点对$(i,j)$（$i<j$），首先判断$i,j$是不是一定得死去，如果不是，那么很显然只有$S(i)\cap S(j)=\varnothing$才能让$i$和$j$同时存活（一只火鸡不能同时给$i$和$j$抵命）。

题解

#include<stdio.h>
#include<bitset>
using namespace std;
const int maxn=405,maxm=100005;
int n,m,ans;
int a[maxm],b[maxm],no[maxn];
bitset<maxn>keep[maxn];
int main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&a[i],&b[i]);
    for(int i=1;i<=n;i++){
        keep[i][i]=1;
        for(int j=m;j>=1;j--){
            if(keep[i][a[j]]&&keep[i][b[j]]){
                no[i]=1;
                break;
            }
            if(keep[i][a[j]])
                keep[i][b[j]]=1;
            else if(keep[i][b[j]])
                keep[i][a[j]]=1;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(no[i]==0&&no[j]==0&&(keep[i]&keep[j]).count()==0)
                ans++;
    printf("%d\n",ans);
    return 0;
}