本文主要是介绍1185 威佐夫游戏 V2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1185 威佐夫游戏 V2 
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
收藏
关注
有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
威佐夫博弈：
（ak，bk） 且ak<=bk
k=bk-ak ip=1.618 -->(√5+1)/2
若ak=k*ip 则后手胜
但是
事情远远没有这么简单
这道题有精度要求，所以不能直接简单去乘1.618
题目要求：石子数最多有18位，所以要把它分开= =
第2 - T + 1行：每行2个数分别是2堆石子的数量，中间用空格分隔。(1 <= N <= 10^18)
具体实现：
上面提到，由于是大数，直接乘以(sqrt(5)+1)/2会有精度问题。
那么我们就来模拟一下两数之差和(sqrt(5)+1)/2相乘的过程，
它等价为：(b-a)*黄金分割比例+(b-a) .
我们用tmp数组存储黄金分割比例的小数点后1~9位、10~18位、19~27位。
用l存储(b-a)的高9位，r存储(b-a)的低9位。
则两数相乘有：
tmp[0] tmp[1] tmp[2]
* l r
——————————————————————
r*tmp[0] r*tmp[1] r*tmp[2]
+ l*tmp[0] l*tmp[1] l*tmp[2]
以上是模拟乘法的过程，只需要把每一位对应的数相加再加上低位，最后加上(b-a)即可。
代码中sum求解过程理解：（以第一个测试数据3 5为例）
618033988 749894848 204586834
* 0 2
———————————————————————————
1236067976 1499789696 409173668
+ 0 0 0
sum=409173668
sum=1499789696+(409173668/1e9) -->实则把倒数第二位变成1499789696.409173668
=1499789696 没进位，所以后面九位省略就好
sum=1236067976+(1499789696/1e9) -->实则把倒数第三位变成1236067976.1499789696 409173668
=1236067976 注意这里10位，说明倒数第三位有进位，+1就好，小数点后面都省略，因为没用~~
sum=k+0+(1236067976 /1e9) -->实则把最后乘积结果变成0.1236067976.1499789696 409173668
-->0.1236067977 也是十位，需进位，结果变成1.236067977（乘积最终结果）
-->因为使用1.618...后面小数乘k的，所以还要+小数点前面的1*k
代码：
#include<iostream>
#include<cmath>
using namespace std;long long s[3]={618033988,749894848,204586834};
long long mod=1e9;int main()
{int t;cin>>t;long long a,b,k;while(t--){cin>>a>>b;if(a>b)swap(a,b);k=b-a;long long sum=0;long long l=k/mod; //k的高九位long long r=k%mod; //k的低九位sum=r*s[2]; //最低位sum=r*s[1]+l*s[2]+sum/mod; //倒二位.倒一位（如果没进位只剩倒二，否则+进位）sum=r*s[0]+l*s[1]+sum/mod; //倒三位.倒二位倒一位sum=k+l*s[0]+sum/mod; //0.618...(共27位)，所以乘积除以三个1e9 最后加上1*kif(a==sum)cout<<"B"<<endl;elsecout<<"A"<<endl;}return 0;
}
这篇关于1185 威佐夫游戏 V2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
