Nim游戏的一个扩展——51nod 1661 黑板上的游戏+LA 5059 Playing With Stones

谁借莪１个温暖的怀抱￠ 2022-07-17 04:07 95阅读 0赞

前几天做过一道题目，是Nim游戏的一个扩展，也不能说扩展吧，只是说另一种常见的状态。

### 问题引入： ###

给定n堆石子，每堆石子有vi（1<=vi<=1e5) 个，每次可以取一堆中的一些石子，使得剩下的石子为1到vi/k个，为最后的是先手胜，还是后手胜，如果先手胜则输出相应的操作策略。

### 思考： ###

当k==2的时候，显然就退化成了la 5059 的题目，我们以此为基础来考虑，肯定要先计算出sg的函数表，然后观察规律，lrj在训练指南中说的很清楚，打表的规则也很简单，下面给出lrj所打出的表：  
0 1 0 2 1 3 0 4 2 5  
当然，lrj是从奇偶性来分析的，那么很容易得出  
sg（x）=n%2==0？sg（n/2）这样的结论，因为k==2，刚好有一些特性被提现出来了。所以：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    ll sg(ll n)
    {
        return n%2==0 ? n/2 : sg(n/2);
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n;
            ll x;
            scanf("%d",&n);
            ll ans=0;
            while(n--)
            {
                scanf("%lld",&x);
                ans^=sg(x);
            }
            if(ans)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }

那么当k>2的时候，又该怎么去解决？难道比葫芦画瓢？要推出  
sg=（n%k==0）？n/k：sg（n/k） 这样的结论，如果真的这样，我只能说比葫芦画瓢的能力只用在了记答案上，这种能力应该是一种分析该问题的方法，正确的解法无非是打sg表，寻找规律。

笔者随手推了一下，那么打出的表如下：

k==3： 0 1 2 0 3 4 1 5 6  
k==4：0 1 2 3 0 4 5 6 1 7 8 9

可以发现，都有123456……这个序列，而再去翻看上面的n==2的情况，发现都存在这样的规律，但是，好像没什么用，具体编程还是没办法操作，再去细看，发现打断123456这个序列的的下标x都是x%k==1，而且去掉123456这样的数后得到的都是原序列，那么，也就是说，当x%k==1时，sg（x）=sg（x/k） 否则，这样的123456序列实际上是由x-阶梯层数得到的，什么是阶梯层数，当k==3的时候x=1，2，3就属于第一层，x=4，5，6 就属于第二层，那么容易得出：

x%k==1 ? sg(x/k) : x-x/k-(x%k!=0);

于是，上题的第二种解法为：

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    ll k=2;
    ll sg(ll x){
       if (x==1) return 0;
       return x%k==1 ? sg(x/k) : x-x/k-(x%k!=0);
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n;
            ll x;
            scanf("%d",&n);
            ll ans=0;
            while(n--)
            {
                scanf("%lld",&x);
                ans^=sg(x);
            }
            if(ans)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }

而对于51nod中要求求必胜操作时，只需预处理一下sg值，然后枚举每一位根据sg值来逆推符合条件的x即可。

提交地址：  
[http://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1661][http_www.51nod.com_onlineJudge_questionCode.html_problemId_1661]

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int N=1e5+5;
    
    ll n,k,sl[N],sr[N],v[N],vt[N];
    ll sg(ll x){
       if (x==1) return 0;
       return x%k==1 ? sg(x/k) : x-x/k-(x%k!=0);
    }
    
    int main()
    {
        sl[0]=sr[n+1]=0;
        cin>>n>>k;ll p=0,ans=0;
        for (int i=1;i<=n;i++){
            scanf("%lld",v+i);
            vt[i]=sg(v[i]);
            sl[i]=sl[i-1]^vt[i];
        }
        for (int i=n;i>=1;i--) sr[i]=sr[i+1]^vt[i];
        for (int i=1;i<=n;i++){
          ll tt=sl[i-1]^sr[i+1],tx=ceil(1.0*v[i]/k);
          if (v[i]==1||vt[i]<=tt) continue;
          ll ttl=(ll)(1.0*tt*k/(k-1)+1);
          if (ttl%k==1) ttl--;
          for (int j=0;j<64;j++){
              if (ttl>=tx) break;
              ttl=ttl*k+1;
          }
          if (ttl<v[i]&&sg(ttl)==tt){
                p=i;ans=ttl;break;
            }
        }
        if (sl[n]) cout<<"Alice "<<p<<" "<<ans<<endl;
        else puts("Bob");
    }

[http_www.51nod.com_onlineJudge_questionCode.html_problemId_1661]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1661