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

Problem Analysis

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

对于输入而言，有两种操作，当输入1 k时，在序列尾部添加一个元素 k k k。当输入2 k时，表示从 k k k开始游戏。对于所有的操作，输出该次游戏的获胜者。

思路分析：

设 d p [ i ] dp[i] dp[i]表示指针在位置 i i i时的胜负状态。当 d p [ i ] = 1 dp[i] = 1 dp[i]=1时，表示棋子在 i i i位置时必胜；当 d p [ i ] = = 0 dp[i] == 0 dp[i]==0时，表示棋子在 i i i位置时必败。那么不难发现对于相同的数字，我们只需要考虑最靠近末端的该数字是否为必胜态即可。那么我们可以暴力处理所有后面的元素，每个元素向前标记所有可能到达的必输态即可。

#include 
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 tmp;
    for(int i = 0; i  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 > a[i]; update(a[i], i); } //!在读入时更新last数组
    Sort();
    while(m--) solve();
    return 0;
}