題目鏈接：點擊查看

題目大意：最初有n堆石子，每堆石子的數(shù)目已知，現(xiàn)在有兩個人輪流按照下列規(guī)則操作，不能操作的一方即為失敗

首先選擇一堆石子，設(shè)該堆石子目前有x個，從中拿走a個石子，剩下了k個石子，a和k必須滿足

0<a<x

0<k<x

k^x<x

然后加入一堆新的石子，數(shù)目為k^x，每個人每一局可以使用一次技能，讓新增加的石子為(2*k)^x

題目分析：這個題如果直接去分析挺難想的，我們可以轉(zhuǎn)換一下思維模式，上述兩個規(guī)則無疑就是將n堆石子中滿足條件的一堆分成了兩堆，其新的值為k和k^x，直到不能再分為止，能想到這里還是差點火候，下面我用網(wǎng)上大佬的思路，來證明一下k和k^x的關(guān)系：

我們分成四種情況，討論其中二進制的某一位p：

x	k	k^x
0	0	0
0	1	1
1	0	1
1	1	0

通過上表，我們可以看出，在將x分為k和k^x后，1的個數(shù)之和的奇偶性不變，然后從某一位p的結(jié)論推廣到整個x和k中，可以得到相同的結(jié)論，我也不知道是怎么想到的。。換做是我肯定想不到orz

下面在討論一下關(guān)于終止條件，也就是必敗條件是什么，我們選出其中一堆，若該堆石子的數(shù)目轉(zhuǎn)換為二進制后，1的數(shù)目只有一個，那么該堆是無法再分的，因為題目要求了k^x<x，所以我們找不出合適的k來滿足條件（反之，若1的數(shù)目大于一個的話，我們每次都可以從x中選取任意數(shù)目的1，并且給x中剩下一定數(shù)目的1，即可滿足條件）

所以我們現(xiàn)在有了兩個結(jié)論：

x 和k與k^x中1的數(shù)目之和的奇偶性相同

每次k至少需要選擇x中任意數(shù)目的1

最后再分析一下每個人可以使用的那個技能，因為是將k^x變?yōu)?2k^x)，乘二在二進制里也不會影響1的數(shù)目之和的奇偶性，所以這個技能實際上沒有什么貢獻

綜上所述，我們只需要分析一下初始時n堆石子中1的數(shù)目之和，然后減去原本n堆中需要保留的一個1（必敗態(tài)），再判斷一下奇偶性就能判斷操作次數(shù)了，如果答案為奇數(shù)，則先手能操作最后一步，先手必勝，否則先手必敗

對了，因為這個題目需要統(tǒng)計每個數(shù)字中1出現(xiàn)的次數(shù)，一般來說我們都會直接跑一遍二進制，今天學會了一個更快的方法可以優(yōu)化，就是用n&(n-1)，下面放上大佬的證明：

https://blog.csdn.net/u013243347/article/details/52220551

實現(xiàn)代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int getnum(int n) {int cnt=0;while(n){n&=n-1;cnt++;}return cnt; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;int kase=0;while(w--){int n;int ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){int num;scanf("%d",&num);ans+=getnum(num);}printf("Case %d: %s\n",++kase,(ans-n)&1?"Yes":"No");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 4388 Stone Game II(博弈+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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