CF282D Yet Another Number Game 题解

· · 题解

upd on 2025.11.14 根据要求删除部分“嘎”语气词。

Introduction

好玩的博弈 DP 嘎。

首先第一眼看到这个题目，感觉不怎么好维护，因为有 n 个数，一个个去维护具体情况很复杂。

但是你不觉得很奇怪吗？这样好像就不可做了嘎。

于是我们再读一次题面，很震惊地发现，题目保证了 n \le 3 嘎！这是一个非常振奋人心的消息——因为这意味着，可以维护 a 中所有数字的情况！

但是由于不总是 3 个数字，我们可以分类讨论一下嘎。

When n is 1

分析一下嘎。

当 n = 1 的时候，说明序列中只有 a_1 一个元素，这个时候先手是相对自由的。

很容易发现，当 a_1 > 0 的时候先手肯定是会赢的。因为他只需要选定 a_1 这个数，并让 x = a_1 ，那么 a_1 的值就会变成 0 ，后手就输了，先手就赢了嘎。

但是当 a_1 = 0 的时候，先手什么也操作不了嘎。他就直接输了，后手就赢了。

所以当 n=1 的时候直接特判一下 a_1 的值就可以了嘎，完全不需要 DP 或者怎么样。

When n is 2

接着考虑有两个数字的情况嘎。

容易定义出状态 f_{x,y}，表示当最开始的状态为 {a_1} ^{\prime} = x 且 {a_2} ^{\prime} = y 的情况下，先手是否有必胜策略嘎。

容易发现 f 是一个 bool 类型的数组。这样正好也节约了空间。

由于一旦有一个必胜策略，就不存在失败的情况了，所以我们可以考虑从必败情况转移到必胜情况。反过来等同于浪费时间，因为初始化的时候状态就是失败，没必要再额外转移了。

接下来考虑具体的转移嘎。

首先肯定要枚举 x 和 y。然后我们可以考虑倒着推过去，这样会比较好处理。当然，上面也说了，得判断一下 f_{x,y} 是否为 0 ，不为 0 的话 continue 掉就好了。

还得枚举 p，也就是题面中所说的 x ，即操作时减去的那个具体的数字嘎。

然后就要看看能不能支持了。首先看只处理 a_1，也就是只改变 x 的情况——只需要判断一下 x+p \le a_1 就可以了，这样就可以让 f_{x+p,y} = 1 了嘎！

同理，满足 y + p \le a_2 的话也有 f_{x,y+p} = 1 嘎。

这样我们就处理完了选一个数改变的操作，但还有一个是全局改变。也不难，只要 x+p \le a_1 和 y + p \le a_2 这两个条件同时满足就可以了，那么就有 f_{x+p,y+p} = 1 了嘎。

那么 DP 的部分就结束了。输出的时候判断一下，如果 f_{a_1 , a_2} = 1 就代表先手赢，否则代表后手赢。

When n is 3

最后考虑有三个数字的情况嘎。

这是最复杂的一种情况，但是其实上它的本质和 n=2 的是一样的。

定义 dp_{x,y,z} 表示当最开始的状态 {a_1} ^{\prime} = x、{a_2} ^{\prime} = y 且 {a_3} ^{\prime} = x 的情况下，先手是否有必胜策略嘎。

枚举 x,y,z,p，x,y,z 就不多赘述了，p 和 n=2 的情况的含义是一样的嘎。

同样也要判断 dp_{x,y,z} = 0，不多说嘎。

接着是转移：如果 x + p \le a_1，就 dp_{x+p,y,z} = 1；如果 y+p \le a_2，就 dp_{x,y+p,z} = 1；如果 z+p \le a_3，就 dp_{x,y,z+p} = 1；最后还有一条，如果上面三个条件全部满足，就可以 p_{x+p,y+p,z+p} = 1 了嘎！

答案与 n=2 的情况类似，如果 dp_{a_1 , a_2,a_3} = 1 就代表先手赢，否则代表后手赢嘎。

Accepted code

Submission 嘎。

仅供参考，不得抄袭嘎。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 305;
int n,a[5];bool f[N][N],dp[N][N][N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int main(){
  n=read();
  for(int i=1;i<=n;i++)a[i]=read();
  if(n==1){
    if(a[1]>0)cout<<"BitLGM\n";
    else cout<<"BitAryo\n";
  }else if(n==2){
    for(int x=0;x<=a[1];x++)
      for(int y=0;y<=a[2];y++){
        if(f[x][y])continue;
          for(int p=1;p<=300;p++){
            if(x+p<=a[1])f[x+p][y]=1;
            if(y+p<=a[2])f[x][y+p]=1;
            if(x+p<=a[1]&&y+p<=a[2])f[x+p][y+p]=1;
          }
      }
      if(f[a[1]][a[2]])cout<<"BitLGM\n";
      else cout<<"BitAryo\n";
  }else{
    for(int x=0;x<=a[1];x++)
      for(int y=0;y<=a[2];y++)
        for(int z=0;z<=a[3];z++){
          if(dp[x][y][z])continue;
          for(int p=1;p<=300;p++){
            if(x+p<=a[1])dp[x+p][y][z]=1;
            if(y+p<=a[2])dp[x][y+p][z]=1;
            if(z+p<=a[3])dp[x][y][z+p]=1;
            if(x+p<=a[1]&&y+p<=a[2]&&z+p<=a[3])dp[x+p][y+p][z+p]=1;
          }
        }
    if(dp[a[1]][a[2]][a[3]])cout<<"BitLGM\n";
    else cout<<"BitAryo\n";
  }
  return 0;
}

Summary

这就是整个题目的思维逻辑了，并不难想，也不难写。个人感觉唯一麻烦的点是要分类讨论，不过 n=2 和 n=3 的情况相似，所以也很轻松嘎。

顺带一提，我觉得这个题目没有蓝的难度，思维和码量都够不到，不知道之前的评分是怎么弄的，也许远古嘎？不知道，但是个人认为绿会合理一些嘎。

At last

第一期嘎嘎题解，写的不太好，还请各位谅解嘎。

在此，嘎嘎喵要郑重感谢各位读者仔细认真阅读到最后嘎。

如果本篇题解对你有帮助的话，还麻烦你点一个小小的赞，真是太感谢了嘎！