zoj 3964 - Yet Another Game of Stones // 2017zjpc

题意： 有n堆石子，每堆有一个限制0,1,2，限制只对Alice生效，分别表示没有限制，只能取奇数个，只能取偶数个，Alice先手，问她是否有必胜策略

思路： 是nim博弈上面加限制，

当没有限制->裸nim博弈：当异或和为0时先手必败，否则必胜；因为对B没有限制所以其实当异或为0就必败

当异或不为零，当B取偶数的时候A势必要取一个偶数使得回到异或不为零的情况，即留给B异或为0的情况；同理当B取奇数个，A势必要取奇数个

于是这时候考虑限制是否会让A达不到这些条件，可以发现当有1限制的石子都是1个的时候这个限制便不存在

最佳策略：开局A先看能否能取走一些石子达到nim为0的条件，此时最好能消除一些限制，（比如将限制为2的偶数堆整个拿走等等）或将偶数限制为1的堆拿成1的堆

btw，((vec1[0] ^ 1 ^ XOR) == 0)) 这个优先级问题卡了我整整一天，异或你是不是有点太弱了我日

#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll N = 1e5 + 10;ll a[N], b[N];vector<ll> vec1, vec2;int main() {       ll T;    scanf("%lld", &T);    while (T--) {           vec1.clear();        vec2.clear();        ll n;        scanf("%lld", &n);        ll XOR = 0;        for (ll i = 1; i <= n; ++i) {               scanf("%lld", a + i);            XOR ^= a[i];        }        for (ll i = 1; i <= n; ++i) {               scanf("%lld", b + i);            if (b[i] == 1 && a[i] != 1) {                   vec1.push_back(a[i]);            } else if (b[i] == 2) {                   vec2.push_back(a[i]);            }        }        if (XOR == 0) {               puts("Bob");        } else {               if (vec1.size() == 0 && vec2.size() == 0) {                   puts("Alice");            } else if (vec1.size() + vec2.size() > 1) {                   puts("Bob");            } else {                   if (vec2.size() == 1) {                       if ((vec2[0] % 2 == 0) && ((vec2[0] ^ XOR) == 0)) {                           puts("Alice");                    } else {                           puts("Bob");                    }                } else if (vec1.size() == 1) {                       if ((vec1[0] % 2 == 0) && ((vec1[0] ^ 1 ^ XOR) == 0)) {                           puts("Alice");                    } else if ((vec1[0] & 1) && ((vec1[0] ^ XOR) == 0)) {                           puts("Alice");                    } else {                           puts("Bob");                    }                }            }        }    }    return 0;}

转载地址：http://pkzg.baihongyu.com/

你可能感兴趣的文章