CSAcademy Round #63 (Div. 2 only) Graph Game

题目链接https://csacademy.com/contest/round-63/task/graph-game/

题意AliceBob在玩游戏,给定一个无向图,每轮每个人要删去一个度数为偶数的点,同时删除这个点连着的边,谁先不能操作谁先输,Alice先手,两个人都用最佳的策略,问Alice能否赢。

思路:考虑当加入一条边的时候边两条的点的度数都加一,所以最终无向图总度数一定是偶数。同时我们有总度数=偶数度数的点的总度数+奇数度数的点的总度数,而偶数度数的点的总度数又一定总是偶数的,所以我们可以知道奇数度数的点的总度数一定总是偶数,又由这个可以推导出奇数度数的点的总数一定是偶数,而对于一张无向图,点的总个数=偶数度数的点的总个数+奇数度数的点的总个数,因为后者一定为偶数,所以点的总个数和偶数度数的点的总个数的奇偶性一定是相同的。
回到题目,现在我们每次要删去一个度数为偶数的点,而由上的性质我们可以知道,如果先手的时候点的总个数是偶数,那么他的回合偶数度数的点的总个数一定永远是偶数,最后的结果一定是到他的回合的时候偶数度数的点的总数为0而落败,所以我们只要判断点的总数的奇偶性即可,奇数先手必胜,偶数先手必败。

int T,n,m,x,y;
int main(){
    for (cin>>T;T--;){
        cin>>n>>m;
        for (int i=1,x,y;i<=m;i++) cin>>x>>y;
        puts(n&1?"1":"0");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注