「DP」SP3885 MCOINS - Coins Game

ImmatureDreamer · 2026-07-21 19:11:01 · 题解

由于只有初始值发生变化，而结束状态一定是 1，考虑从 1 倒推初始值为多少时先手会胜。

那么，每次值的变化有三种：x-K \to x,x-L \to x,x-1 \to x。

DP，设 f_i 表示初始值为 i 时当前玩家是否必胜。

每次在可能的三种取法中，只要存在一种取法，使得取完后剩下的状态是必败态（即对手处在必败态），那么当前玩家就必胜。故有如下转移。

其中 \operatorname{or} 为按位或运算。

最终，若 f_{N_i}=1 则输出 A 否则输出 B。

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

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int m, k, l, mx = 0;
    cin >> k >> l >> m;

    vector<int> n(m, 0);
    for(int i = 0; i < m; ++ i){
        cin >> n[i];
        mx = max(mx, n[i]);
    }

    vector<bool> f(mx + 1, 0);
    for(int i = 1; i <= mx; ++ i)
        f[i] = ((!f[i - 1]) || (i >= k && !f[i - k]) || (i >= l && !f[i - l]));

    for(int i = 0; i < m; ++ i)
        cout << (f[n[i]] ? 'A' : 'B');

    return 0;
}