?

【題目鏈接】?http://poj.org/problem?id=2315

?

【題目大意】

　　兩名球員輪流從N個球中挑出不多于M個射門，每個球半徑都是R，離球門S。
　　每次只能踢出L以內的距離。進最后一個球者勝，求誰有必勝策略？

?

【題解】

　　我們發現對數據進行處理之后，題目等價于給出n堆石子，
　　每堆石子中每次最多取k個石子，每次最多選取m個石子堆做操作的博弈問題
　　首先我們將每堆石子堆對k+1取模簡化運算，
　　對于只能取一堆石子上的石子的做法我們是對所有的石子堆的sg值進行xor運算得到sg值
　　xor又稱為半加運算，只進行加法而不進位，
　　對于選取m堆石子的博弈我們的xor則是對于m+1進制下的半加運算，
　　所以我們按位計算這個sg值，模擬m+1進制下的半加運算即可得到答案。

?

【代碼】

#include <cstdio> #include <cstring> #include <cmath> using namespace std; const int N=30; const double PI=acos(-1.0); int n,m,l,r,a[N],sg[N]; int dis(int s){return (int)(s/(2*PI*r))+1;} bool solve(){memset(sg,0,sizeof(sg));int k=dis(l);for(int i=0;i<n;i++)for(int j=0,g=dis(a[i])%k;sg[j]+=g&1,g;j++,g>>=1);for(int i=0;i<30;i++)if(sg[i]%(m+1))return 1;return 0; } int main(){while(~scanf("%d%d%d%d",&n,&m,&l,&r)){for(int i=0;i<n;i++)scanf("%d",&a[i]);puts(solve()?"Alice":"Bob");}return 0; }

轉載于:https://www.cnblogs.com/forever97/p/poj2315.html

總結

以上是生活随笔為你收集整理的POJ 2315：Football Game（博弈论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。