题解 | 浮木博弈

看到好多人都是正向思考的，我分享下我的反向思考。感觉思路还是挺简单的喵。

显然，在最后一个堆先手的家伙一定会赢（这里设之为0号选手），那么，取完倒数第二个堆的家伙一定输。我们用一个标记来判断当前堆是谁取完（败者1，胜者0）进行迭代，初始显然为胜者，然后从倒数第二个堆开始遍历，如果上一个先取的家伙是败者，毫无疑问这次一定是胜者先手并取完（显然不用考虑堆里东西的个数），如果上一个先取的家伙是胜者，那么这次要败者取完，如果堆中个数为1，说明这次是败者先手；否则，就是胜者先手（使得堆中只剩一个让败者取），那么显然迭代到最开始的情况，就知道先手的Alice是胜者还是败者了！

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        long long a[n];

        for(int i=0;i<=n-1;i++){
            cin >> a[i];
        }
        //显然，到最后一堆一定全取，取完倒数第二推的输，依次类推
        int res = 0; //假设取到最后一堆的为0号选手
        //过程状态为，在对应堆先开始取的人
        for(int i=n-2;i>=0;i--){
            if(res){ //上一个状态是败者取，这次胜者取完
                res^=1;
            }else{ //上一个状态是胜者取，这次败者取完
                if(a[i]==1) res = 1;
                else res = 0; //胜者先取。
            }
        } 
        if(!res){ 
            cout << "Alice" << '\n';
        }else cout << "Bob" << '\n';
    }
}
// 64 位输出请用 printf("%lld")