CF 1634B Fortune Telling

题目描述

https://codeforces.com/contest/1634/problem/B

简要题意：给定一个长度为 $n$ 的数列 $a_i$，现在 $Alice$ 手上有一个数 $x$，$Bob$ 手上的数是 $x+3$，对于这个数列，每个人都从 $a_1$ 开始到 $a_n$ 按顺序操作，对于当前数 $a_i$，可以选择将手上的数 $x$ 加上 $a_i$，或者将 $x$ 异或上 $a_i$，现在给定一个数 $y$，求 $y$ 是 $Alice$ 操作得到的还是 $Bob$ 操作得到的，题目保证 $y$ 一定是其中一个人操作得到的

$n\le 10^5$

Solution

注意到加法和异或对于数的奇偶性的影响是相同的，而 $Alice$ 和 $Bob$ 的两个数初始奇偶性就不同，所以我们从奇偶性出发判断就行了

#include <iostream>
#include <cstdio>
#define maxn 100010
#define ll long long
using namespace std;

ll n, x, y, a[maxn];

void work() {
    cin >> n >> x >> y; int s = y & 1; 
    for (int i = 1; i <= n; ++i) cin >> a[i], s ^= a[i] & 1;
    if ((x & 1) == s) cout << "Alice" << "\n";
    else cout << "Bob" << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}