The 2020 ICPC Asia Macau Regional Contest G.Game on Sequence 博弈+思维

Problem Analysis

题目大意：给定一个长度为的非负整数序列，游戏规则为：初始状态有一个指针指向某个序列元素，你可以从下标后面的元素中选择一个一个二进制位与其相差不超过位的元素，并将指针移动到该元素上。和轮流进行游戏，不能操作的人视为输掉游戏。

对于输入而言，有两种操作，当输入​

​1 k​

​​时，在序列尾部添加一个元素。当输入​​

​2 k​

​​时，表示从开始游戏。对于所有的操作，输出该次游戏的获胜者。

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 100, MAX = 256;
int a[N], last[300], dp[300], tot;

const bool cmp (const int &a, const int &b) { return last[a] > last[b]; }

inline void update(int x, int loc){ last[x] = loc; }

inline void Sort(){
    memset(dp, 1, sizeof(dp));
    vector<int> tmp;
    for(int i = 0; i < MAX; i++) if(last[i]) tmp.push_back(i);
    sort(tmp.begin(), tmp.end(), cmp);      //找到最后出现的数字中最大的，该数字为必胜态
    for(auto num : tmp){
        bool flag = false;
        for(int i = 0; i < 8; i++){
            if(!dp[num ^ (1 << i)]){
                flag = true;
                break;
            } 
        }
        if(flag) dp[num] = 1;
        else dp[num] = 0;
    }
}

inline void solve(){
    int op = 0, x; cin >> op >> x;
    if(op == 1){
        a[++tot] = x;
        update(a[tot], tot);
        Sort();
    }
    else{
        if(last[a[x]] == x){
            if(dp[a[x]]) puts("Grammy");
            else puts("Alice");
        }
        else puts("Grammy");
    }
}

signed main(){
    int n, m; cin >> n >> m; tot = n;
    for(int i = 1; i <= n; i++){ cin >> a[i]; update(a[i], i); } //!在读入时更新last数组
    Sort();
    while(m--) solve();
    return 0;
}