本文主要是介绍51nod 1185 威佐夫游戏 V2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
有2堆石子。A B两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出2堆石子的数量,问最后谁能赢得比赛。
例如:2堆石子分别为3颗和5颗。那么不论A怎样拿,B都有对应的方法拿到最后1颗。
Input
第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 - T + 1行:每行2个数分别是2堆石子的数量,中间用空格分隔。(1 <= N <= 10^18)
Output
共T行,如果A获胜输出A,如果B获胜输出B。
Input示例
3
3 5
3 4
1 9
Output示例
B
A
A
解题思路
威佐夫博弈,关键主要是对于精度的处理,这里将(0.)618033988,749894848,204586834先保存在数组tmp[]中,则其与另一个数x相乘便可转化为 x*tmp[0]/mod+x*tmp[1]/mod/mod+x*tmp[2]/mod/mod/mod(mod=1e9),①
又∵ x=(x/mod)*mod+x%mod,令m=x/mod,n=x%mod
则①式可转化为
(m*tmp[0]+n*tmp[0]/mod)+(m*tmp[1]/mod+n*tmp[1]/mod/mod)+(m*tmp[2]/mod/mod+n*tmp[2]/mod/mod/mod),
继续转化则有
m∗tmp[0]+(n∗tmp[0]+m∗tmp[1]–––––––––––––––––––––––+(n∗tmp[1]+m∗tmp[2]–––––––––––––––––––––––+n∗tmp[2]/mod–––––––––––––––)/mod––––––––––––––––––––––––––––––––––––––––––––––––)/mod. m ∗ t m p [ 0 ] + ( n ∗ t m p [ 0 ] + m ∗ t m p [ 1 ] _ + ( n ∗ t m p [ 1 ] + m ∗ t m p [ 2 ] _ + n ∗ t m p [ 2 ] / m o d _ ) / m o d _ ) / m o d .
此题需要乘以1.618……,最后再加上一个差值即可.
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IO ios::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0);
ll tmp[3] = {618033988,749894848,204586834};
const ll mod= 1e9;
int main()
{IO;int T;cin>>T;ll a,b;while(T--){cin>>a>>b;if(a<b) swap(a,b);ll t=a-b;ll m=t/mod;ll n=t%mod;ll ans=n*tmp[2];ans=n*tmp[1]+m*tmp[2]+ans/mod;ans=n*tmp[0]+m*tmp[1]+ans/mod;ans=t+m*tmp[0]+ans/mod;if(ans==b) cout<<"B"<<endl;else cout<<"A"<<endl;}return 0;
}
这篇关于51nod 1185 威佐夫游戏 V2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!