Java教程

P2575

本文主要是介绍P2575,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

P2575(博弈论,多解)

方法一(\(SG\)定理+二进制):

\(O(n20^n)\)
可以把每一行看作一个\(20\)位的二进制数字,对于每一位的初始状态有就记位\(1\),没有就记为\(0\),最多\(20^n\)种情况。
状态的转移:是把\(1\)往后移动到右边第一个\(0\),最多\(20\)位(后来想了一下似乎不到\(10\)位)。
于是暴力打表计算所有的\(sg\)值。
\(sg\)定理计算即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define ll long long
const ll N = (1<<20)+50;
ll sg[N];
bool vis[20];
void init(){
    for(ll i = 1;i <= (1<<20);i++){
        if((i&(i+1)) == 0) {sg[i] = 0;continue;}
        ll cnt = 0,tmp = i;
        while(tmp) tmp>>=1,cnt++;
        ll flag = -1;
        memset(vis,false,sizeof vis);
        for(ll j = 0;j <= cnt-1;j++){
            if(((i>>j)&1) == 0) flag = j;
            else if(flag!=-1) vis[sg[i-(1<<j)+(1<<flag)]] = true;
        }
        ll res = 0;
        while(vis[res])++res;
        sg[i] = res;
    }
}
int main() {
    ios::sync_with_stdio(false);
    init();
//    for(ll i = 1;i <= 100;i++){
//        cout<<i<<' '<<sg[i]<<endl;
//    }
    ll t;cin>>t;
    while(t--){
        ll n,ans = 0;cin>>n;
        while(n--){
            ll l = 0,a[25] = {0};
            ll m;cin>>m;
            while(m--){
                ll x;cin>>x;
                a[x] = 1;
            }
            for(ll i = 1;i <= 20;i++){
                l<<=1;
                if(a[i] == 1)l++;
            }
            //cout<<l<<' '<<sg[l]<<endl;
            ans^=sg[l];
        }
        puts(ans?"YES":"NO");
    }
    return 0;
}

方法二(阶梯\(Nim\)):

把每两个空位置之间的棋子看做一堆石子儿,我们发现每一次移动就相当于一堆把若干石子儿从一堆转移到右边的一堆,直到最右边的那一堆。这样的变换符合阶梯\(Nim\)。
\(Nim\),\(SG\)值为奇数位的异或和,最后\(SG\)定理即可。
(下面是别人的代码,据说是最快的?)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int SG[30],a[30],fz[1000];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t,n;cin>>t;int a[30],cnt[30];
    while(t--)
    {
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;++i)
        {
            int len;
            memset(cnt,0,sizeof cnt);
            cin>>len;
            for(int i=1;i<=len;++i)
                cin>>a[i],cnt[a[i]]++;
            int tot=0,i=20,fg=0;
//			for(int i=1;i<=20;++i)printf("cnt=%d\n",cnt[i]);
            while(cnt[i])--i;
            for(;i;--i)
            {
//				printf("tot=%d\n",tot);
                if(!cnt[i])ans^=(fg?tot:0),fg^=1,tot=0;
                else ++tot;
//				printf("ans=%d i=%d tot=%d\n",ans,i,tot);
            }
            ans^=(fg?tot:0);
        }
        cout<<(ans?"YES":"NO")<<endl;
    }
    return 0;
}

一些思考:

对于用\(SG\)函数,精巧之处在于设计二进制,并巧妙地转移。
对于阶梯\(Nim\),应该要抓住一个重点——阶梯不变石子变。并且抽象的做出来。

这篇关于P2575的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!