专栏文章

CF282D Yet Another Number Game 题解

MMoya_Rao啾？啾！
CF282D题解参与者 24已保存评论 31

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
31 条
当前快照
1 份
快照标识符
@minqy09w
此快照首次捕获于
2025/12/02 06:54
3 个月前
此快照最后确认于
2025/12/02 06:54
3 个月前
查看原文
upd on 2025.11.14 根据要求删除部分“嘎”语气词。

Introduction

好玩的博弈 DP 嘎。
首先第一眼看到这个题目，感觉不怎么好维护，因为有 nn 个数，一个个去维护具体情况很复杂。
但是你不觉得很奇怪吗？这样好像就不可做了嘎。
于是我们再读一次题面，很震惊地发现，题目保证了 n≤3n \le 3 嘎！这是一个非常振奋人心的消息——因为这意味着，可以维护 aa 中所有数字的情况！
但是由于不总是 33 个数字，我们可以分类讨论一下嘎。

When nn is 11

分析一下嘎。
当 n=1n = 1 的时候，说明序列中只有 a1a_1 一个元素，这个时候先手是相对自由的。
很容易发现，当 a1>0a_1 > 0 的时候先手肯定是会赢的。因为他只需要选定 a1a_1 这个数，并让 x=a1x = a_1 ，那么 a1a_1 的值就会变成 00 ，后手就输了，先手就赢了嘎。
但是当 a1=0a_1 = 0 的时候，先手什么也操作不了嘎。他就直接输了，后手就赢了。
所以当 n=1n=1 的时候直接特判一下 a1a_1 的值就可以了嘎，完全不需要 DP 或者怎么样。

When nn is 22

接着考虑有两个数字的情况嘎。
容易定义出状态 fx,yf_{x,y}，表示当最开始的状态为 a1′=x{a_1} ^{\prime} = x 且 a2′=y{a_2} ^{\prime} = y 的情况下，先手是否有必胜策略嘎。
容易发现 ff 是一个 bool 类型的数组。这样正好也节约了空间。
由于一旦有一个必胜策略，就不存在失败的情况了，所以我们可以考虑从必败情况转移到必胜情况。反过来等同于浪费时间，因为初始化的时候状态就是失败，没必要再额外转移了。
接下来考虑具体的转移嘎。
首先肯定要枚举 xx 和 yy。然后我们可以考虑倒着推过去，这样会比较好处理。当然，上面也说了，得判断一下 fx,yf_{x,y} 是否为 00 ，不为 00 的话 continue 掉就好了。
还得枚举 pp，也就是题面中所说的 xx ，即操作时减去的那个具体的数字嘎。
然后就要看看能不能支持了。首先看只处理 a1a_1，也就是只改变 xx 的情况——只需要判断一下 x+p≤a1x+p \le a_1 就可以了，这样就可以让 fx+p,y=1f_{x+p,y} = 1 了嘎！
同理，满足 y+p≤a2y + p \le a_2 的话也有 fx,y+p=1f_{x,y+p} = 1 嘎。
这样我们就处理完了选一个数改变的操作，但还有一个是全局改变。也不难，只要 x+p≤a1x+p \le a_1 和 y+p≤a2y + p \le a_2 这两个条件同时满足就可以了，那么就有 fx+p,y+p=1f_{x+p,y+p} = 1 了嘎。
那么 DP 的部分就结束了。输出的时候判断一下，如果 fa1,a2=1f_{a_1 , a_2} = 1 就代表先手赢，否则代表后手赢。

When nn is 33

最后考虑有三个数字的情况嘎。
这是最复杂的一种情况，但是其实上它的本质和 n=2n=2 的是一样的。
定义 dpx,y,zdp_{x,y,z} 表示当最开始的状态 a1′=x{a_1} ^{\prime} = x、a2′=y{a_2} ^{\prime} = y 且 a3′=x{a_3} ^{\prime} = x 的情况下，先手是否有必胜策略嘎。
枚举 x,y,z,px,y,z,p，x,y,zx,y,z 就不多赘述了，pp 和 n=2n=2 的情况的含义是一样的嘎。
同样也要判断 dpx,y,z=0dp_{x,y,z} = 0，不多说嘎。
接着是转移：如果 x+p≤a1x + p \le a_1，就 dpx+p,y,z=1dp_{x+p,y,z} = 1；如果 y+p≤a2y+p \le a_2，就 dpx,y+p,z=1dp_{x,y+p,z} = 1；如果 z+p≤a3z+p \le a_3，就 dpx,y,z+p=1dp_{x,y,z+p} = 1；最后还有一条，如果上面三个条件全部满足，就可以 px+p,y+p,z+p=1p_{x+p,y+p,z+p} = 1 了嘎！
答案与 n=2n=2 的情况类似，如果 dpa1,a2,a3=1dp_{a_1 , a_2,a_3} = 1 就代表先手赢，否则代表后手赢嘎。

Accepted code

Submission 嘎。
仅供参考，不得抄袭嘎。
CPP
#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=2n=2 和 n=3n=3 的情况相似，所以也很轻松嘎。
顺带一提，我觉得这个题目没有蓝的难度，思维和码量都够不到，不知道之前的评分是怎么弄的，也许远古嘎？不知道，但是个人认为绿会合理一些嘎。

At last

第一期嘎嘎题解，写的不太好，还请各位谅解嘎。
在此，嘎嘎喵要郑重感谢各位读者仔细认真阅读到最后嘎。
如果本篇题解对你有帮助的话，还麻烦你点一个小小的赞，真是太感谢了嘎！

评论

共 31 条评论，欢迎与作者交流。

正在加载评论...