2016年1月31日 星期日

[SPOJ MATGAME]MATGAME - Matrix Game

先備知識:$SG$函數的性質

首先可以發現每一列(這裡的「列」是row)可以視作獨立的遊戲,那麼我們就可以分別把每一列的$SG$函數算出來,全部XOR起來,如果是零,那麼先手敗,否則先手勝

再來觀察每一列的$SG$函數怎麼算,為了方便說明,設這一列的第$i$個數字是$A_{i}$,$SG(i)$代表$A_{1}$~$A_{i-1}$都是0時的$SG$函數

經過觀察,可以發現:
$SG(M)=A_{M}$(代表一個經典的$Nim$遊戲)
$if\ A_{i}\leq SG(i+1)$,$SG(i)=A_{i}-1$
$else$,$SG(i)=A_{i}$
(也是一個$Nim$遊戲,只是0顆石頭時的$SG$函數是$SG(i+1)$,不是0)

把所有$SG(1)$XOR起來,判斷是不是0,就完成了

時間複雜度:$O(N*M)$

code:
#include<cstdio>
#include<cassert>
#include<vector>
using namespace std;
int N,M;
int GetSG(const int cnt,const int sg_of_zero)
{
    assert(cnt>0);
    if(cnt<=sg_of_zero)return cnt-1;
    return cnt;
}
int GetSG(const vector<int>&s)
{
    int ans=0;
    for(int i=(int)s.size()-1;i>=0;i--)ans=GetSG(s[i],ans);
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d%d",&N,&M);
        int ans=0;
        for(int row=0;row<N;row++)
        {
            vector<int>s;
            for(int col=0,v;col<M;col++)
            {
                scanf("%d",&v);
                if(v)s.push_back(v); 
            }
            ans^=GetSG(s);
        }
        puts(ans==0?"SECOND":"FIRST");
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原