题解 P4702 【取石子】

· · 题解

没人解释我就来说明一下

首先明确，只要还有石子，那么一定能取

不妨设有两堆石子a_{1}，a_{2}，假设现在还有石子且无法取

那么有a_{1}+a_{2} ≥ 0,a_{2}<a_{1}<0

①两不等式矛盾：两个负数相加必定不是非负数

②石子数不可能为负数

所以只要还有石子，就一定能取

那么问题就转换为两人轮流从一堆石子取一粒，谁先不能取谁输

我们可以假设石子一共有x粒，甲取了k粒

若是甲赢，那么甲一定比乙多取了一颗，得x=2k+1，x为奇数

若是乙赢，那么甲一定和乙取的石子数一样，得x=2k，x为偶数

就推出了双方赢的充要条件

那么上代码


// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int main(){
    int tmp,sum,n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&tmp);
        sum+=tmp;
    }
    if(!(sum&1)){//利用位运算优化
        printf("Bob");
    }
    else{
        printf("Alice");
    }
}