2016年2月13日 星期六

[Codeforces 603C][SG value] Lieges of Legendre

原題連結
這題對於SG value的新手來說還是不錯的題目,說明了遊戲題還是需要嘗試和觀察的....

根據SG定理,每堆乳牛都是獨立的遊戲,只需要分別求出他們的SG value並XOR起來即可。
先按照定義寫下SG的值
SG(x)={ mex{SG(x-1)}, if x%2==1
              mex{SG(x-1),SG(x/2)*(k mod 2)}, if x%2==0
              0,  if x==0
            }
恩.....還是沒想法,那就先把SG(1)~SG(15)列出來吧!(記得k有奇偶兩種情況要分別列出)
接著就要觀察了....k是偶數的情況相對容易觀察,最後可以在O(1)時間給出k是偶數時的SG value
k是奇數的情況可能就沒那麼容易。但是別忘了,只要能在O(log a_i)的時間內給出SG value,總體時間複雜度就是可以忍受的。

最終我做到的總體時間複雜度O(N log a),或許還有更快的方法,不過AC就AC吧(?

#include<bits/stdc++.h>
using namespace std;
int getSG(int x,int k)
{
    if(x==0) return 0;
    if(x==1) return 1;
    if(k%2==0)
    {
        if(x==2) return 2;
        if(x%2==0) return 1;
        else return 0;
    }
    else
    {
        if(x==2) return 0;
        if(x==3) return 1;
        if(x==4) return 2;
        if(x%2==1) return 0;
        else return getSG(x/2,k)==1?2:1;
    }
}
int main()
{
    int n,k,ans=0;
    scanf("%d%d",&n,&k);
    for(int i=0,x;i<n;i++){scanf("%d",&x);ans^=getSG(x,k);}
    printf("%s\n",ans!=0?"Kevin":"Nicky");
}

沒有留言:

張貼留言