51nod 1185 威佐夫游戏 V2 （博弈+大数乘法模拟）

ゝ一纸荒年。 2022-06-15 02:13 172阅读 0赞

题目链接：  
[点击打开题目链接][Link 1]

题解：  
如果数据在106左右，可以直接用(b−a)∗5√\+12。但是这道题数据是1018，那么直接乘的话，肯定会有精度问题。那么我么可以上Java大数的。但是我不会Java啊… 我们也可以直接大数乘法手动模拟。为了提高精度，我们将 0.618033988749894848204586834...拆成三部分的整数放进数组里，然后手动模拟乘法。

代码：

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     //0.618033988749894848204586834... 拆成整数放进数组里，
     //拆成三部分即可 
    ll tmp[3] = {
       618033988,749894848,204586834};
    ll MOD = 1e9;
    
    int main()
    {
        int t;  
        scanf("%d",&t);
        while(t --)
        {
            ll a,b;
            scanf("%lld%lld",&a,&b);        
            if(a > b)
            {
                ll t = a;
                a = b;
                b = t;
            }
            ll diff = b - a;
            //把10^18分成两部分10^9
            ll ta = diff / MOD; 
            ll tb = diff % MOD;
    
            ll tp = tb * tmp[2];
            tp = ta * tmp[2] + tb * tmp[1] + tp / MOD;
            tp = ta * tmp[1] + tb * tmp[0] + tp / MOD;
            tp = ta * tmp[0] + tp / MOD + diff; 
    
            if(tp == a)
                printf("B\n");
            else
                printf("A\n");
        }
        return 0;
    }

[Link 1]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1185

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关 1185 威佐夫游戏 V2(浮点数精度问题)

[1185 威佐夫游戏 V2][1185 _ V2] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [1185 _ V2]: h

矫情吗；*/ 2024年02月18日 00:13/ 0 赞/ 10 阅读

相关 1072 威佐夫游戏(威佐夫博弈模板)

/ Wythoff Game:黄金分割先取完者赢威佐夫博弈：每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取一个局面

怼烎@/ 2024年02月17日 23:59/ 0 赞/ 81 阅读

相关威佐夫博弈

( d o u b l e ) a b s ( b − a ) ∗ ( 1.0 + s q r t ( 5.0 ) ) / 2.0 = = m i n ( a , b ) (

墨蓝/ 2022年08月30日 01:54/ 0 赞/ 164 阅读

相关博弈之威佐夫博弈详解

威佐夫博弈是博弈中的另一个经典模型。问题：首先有两堆石子，博弈双方每次可以取一堆石子中的任意个，不能不取，或者取两堆石子中的相同个。先取完者赢。分析：首

柔光的暖阳◎/ 2022年08月26日 01:15/ 0 赞/ 186 阅读

相关 51nod 1072 博弈威佐夫游戏

有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失

怼烎@/ 2022年08月21日 13:56/ 0 赞/ 190 阅读

相关 51nod 1067 博弈

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次只能拿1，3，4颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。

比眉伴天荒/ 2022年08月21日 12:59/ 0 赞/ 216 阅读

相关 51nod1417 博弈

多年后，每当Noder看到吉普赛人，就会想起那个遥远的下午。 Noder躺在草地上漫无目的的张望，二楼的咖啡馆在日光下闪着亮，像是要进化成一颗巨大的咖啡豆。天气稍有

桃扇骨/ 2022年08月21日 12:48/ 0 赞/ 150 阅读

相关 51nod 1185 威佐夫游戏 V2 （博弈+大数乘法模拟）

题目链接： [点击打开题目链接][Link 1] 题解：如果数据在106左右，可以直接用(b−a)∗5√\+12。但是这道题数据是1018，那么直接乘的话，肯定会有

ゝ一纸荒年。/ 2022年06月15日 02:13/ 0 赞/ 173 阅读

相关博弈论之威佐夫博弈

威佐夫博弈（Wythoff's game）是指的这样一个问题：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不

忘是亡心i/ 2022年05月27日 11:26/ 0 赞/ 223 阅读

相关威佐夫博弈

首先威佐夫博弈的内容是：有两堆石子，两个顶尖聪明的人在玩游戏，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取得人输，分析谁会获得胜利。第

た入场券/ 2022年03月22日 04:18/ 0 赞/ 224 阅读