Wannafly summer camp Day3 —— Stones
初次接触SG博弈，参考了很多大牛的博客，经历了痛并快乐的思考过程。嗯，虽然还是不懂SG到底是什么，嘤嘤嘤… 但博弈不就是一个确定的必赢必输规律吗？不用管什么SG了，照着规律来答案一定是对的~~ 忽然开心( •̀ ω •́ )y 下面开始我复杂的崎岖的解题过程，途中废话可能过多，必要可以手动屏蔽，向下滑… I wil show you the code（手动滑稽）
训练赛 Wannafly summer camp Day3 这套题，恕我直言——————太毒瘤啦！！！ 队友被两道的签到题卡住，一个题会卡精度，一个题纯暴力打表找规律。。。 一个半小时过去了，爆0！！！ 两水题无望，我开始选择开博弈。
进入正题： 这道题和以前做过的石子堆博弈类似，先考虑只有一个堆的情况，一个堆的初始石头数会直接决定先手胜利或失败，从中找到规律 。 以石头数从1开始，递增规律为： 1~b+a-1个一定是先手赢 之后a个一定是先手输 之后b个一定是先手赢 之后a个一定是先手输 之后b个一定是先手赢 … 规律浅显。(＾－＾)V
虽然找出来这个规律，但还不能高兴太早。。。后面再考虑上多个石头堆就复杂了。 具体大佬是怎么想的我不知道。。我是全部情况找出来的，对，没有算法，就是暴力枚举情况_(:з」∠)_
☆☆☆情况1：有一个石头堆数 a<= X <= b 就能直接通过拿这个堆获得胜利！！
☆☆☆情况2：石头堆都是先手输状态，先手必输！！！ 不信自己玩玩看！！
☆☆☆情况3：只有一个石头堆赢，别的石头堆都输，先手必赢（就看准会赢那堆拿，拿完后下个人只能把必输的状态拿走，先手一直都能拿必赢态！！！）
☆☆☆情况4：能赢的石头堆有偶数个，，，emmmmm这时。。我就被打哭了，嗯。（捂脸）我是弟弟。 通过大佬的SG打表代码看出的规律：这里设置先声明一个变量 contribute_w， 简单理解为在赢的状态下，还能坚持几轮一直保持赢的状态，举个例子，如果这个堆现在有7个石头，最少拿2，最多拿3，通过之前的规律，这堆初始状态为必赢，但…这个石头堆可以不用拿2个（剩5）到下个必输态，玩家可以选择拿3个（剩4）保持这个堆的必赢态！！！contribute_w = 2（初始为1，能坚持一轮+1） 可这样有什么用呢？？ 这个先手不会是个傻子吧。。给下家留必赢态！！！ 好吧，再来加一个石头堆，就是只能拿一次就会到必输态那种。。。 现在有： 8 7 两个石头堆，最少拿2，最多拿3…现在看来，两个堆都是必赢态，先手的玩家拿完一个必赢，就成了后手一直拿必赢！！！这时先手不乐意了，觉得这种 有两个赢的状态 就是坑，于是为了把这坑留给对方，选择把7个石头的堆拿成4… (:з」∠) 好了，现在后手就必须面对这个必输的坑啦~~ （ps：现在的石头 8 4 他们的contribute_w都是 1 没办法再推给对方） 所以对 能赢的的状态 计算其contribute_w ，将得到值相互异或，看看是不是将所有堆赢的状态都轮换着拿，最后还能不能给先手剩下单独一个堆的必赢态，也就是异或值不为0 ，这样先手就能赢啦。反之， 先手输！
好了，下面只要把这些情况都考虑到，规律就有啦。代码实现其实很简单的，嘤嘤嘤…
AC代码：
/* * @Author: Achan * @Date: 2018-10-27 18:12:22 * @Last Modified by: Achan * @Last Modified time: 2018-10-29 11:12:20 */ #include<bits/stdc++.h> #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<iomanip> #include<vector> #include<queue> #include<cmath> using namespace std; #define X first #define Y second #define eps 1e-2 #define gcd __gcd #define pb push_back #define PI acos(-1.0) #define lowbit(x) (x)&(-x) #define fin freopen("in.txt","r",stdin); #define fout freopen("out.txt","w",stdout); #define bug printf("!!!!!\n"); #define mem(x,y) memset(x,y,sizeof(x)) #define rep(i,j,k) for(int i=j;i<(int)k;i++) #define per(i,j,k) for(int i=j;i<=(int)k;i++) #define pset(x) setiosflags(ios::fixed)<<setprecision(x) #define io std::ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL); typedef long long ll; typedef long double LD; typedef pair<int,int> pii; typedef unsigned long long ull; const int inf = 1<<30; const ll INF = 1e18 ; const int mod = 1e9+7; const int maxn = 1e5+2; const int mov[4][2] = {-1,0,1,0,0,1,0,-1}; const int Mov[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1}; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main(void) { //fin //fout io int T;cin>>T; while(T--) { int n,a,b; cin>>n>>a>>b; int flag = 0; int ans = 0; while(n--) { int t; cin>>t; if(flag) continue; //已确定先手赢，跳过 if(a<=t && t<=b) flag = 1; //确定先手赢 if(t <= b) continue; //必输不统计 else if( b<t && t <= a+b-1) { ans ^= 1; //该堆下次必须让对方输!! 胜利贡献1 } else { if(a==1) ans ^= t%(a+b); //特殊处理a=1 ,胜利贡献一定是 0~a+b-1的循环！！ else { // a个1 + a个0 + (从b开始的相对长度)/a ： 2 ~ (a+b-1)/a 的循环 t -= b; int np = t % (a+b); int conw = np/a; //贡献胜利 //cout<<conw << endl; //特殊处理前a个1 a个0 取反即可 if(conw == 1) conw = 0;1范围：说明在a里面 不做贡献 else if(!conw) conw = 1; //在0范围：说明是对上次的额外贡献 1 ans ^= conw; //异或 胜利贡献次数 更新最终SG } } // sum += ( (np>=1 && np<=b)? 1:0); } puts((ans || flag)?"Yes":"No"); } }