游戲

jzoj 1984

題目大意：

有很多個點，兩個人每次可以取走$2^k$（k是一個自然數(shù)，可以自己選）個點，取走最后一個點的人勝利，現(xiàn)在你先選，問你是否能贏（能贏輸出MaoLaoDa will win.，不能贏輸出King will win.），如果可以贏，第一步最少拿幾個點

輸入樣例#1

8 4 2

輸出樣例#1

MaoLaoDa will win. 2 MaoLaoDa will win. 1 MaoLaoDa will win. 2

輸入樣例#2

3 8 2

輸出樣例#2

King will win. MaoLaoDa will win. 2 MaoLaoDa will win. 2

數(shù)據(jù)范圍

0<n<10^1000002

解題思路：

我們設(shè)$f[i]$為現(xiàn)在還剩i個點，先拿是否可贏，我們可以得出$f[i]=?f[i?x^k]$，我們稍微用手推一下可以發(fā)現(xiàn)序列：
···
1,1，-1，1,1，-1，1,1，-1，1,1，-1，1,1，-1……
···
不難發(fā)現(xiàn)，可以整除3的都是-1，其它都是1
然后我們還可以發(fā)現(xiàn)可以贏時，第一步就是整除3的余數(shù)，然后因為數(shù)據(jù)太大，我們可以用整除3的性質(zhì)：把所有位置上的數(shù)字加在一起，除以3的結(jié)果和一開始一樣

代碼：

#include<cstdio> #include<string> #include<cstring> #include<iostream> using namespace std; int s; int read() {char x=getchar();int d=0;while (x<'0'||x>'9') x=getchar();while (x>='0'&&x<='9') d+=x-48,x=getchar();//數(shù)位相加return d; } int main() {for (int i=1;i<=3;++i){s=read();if (s%3==0) printf("King will win.\n");//判斷else printf("MaoLaoDa will win.\n%d\n",s%3);//余數(shù)}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【结论】游戏（jzoj 1984）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。