题解 AT2389 【[AGC016E] Poor Turkeys】

whiteqwq · 2020-11-23 18:02:19 · 题解

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;
}