首页 > 其他分享 >HDU 1527 取石子游戏(博弈论)

HDU 1527 取石子游戏(博弈论)

时间:2023-04-20 21:33:59浏览次数:49  
标签:HDU 石子 两堆 ak 博弈论 000 bk int 1527


取石子游戏


Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3717    Accepted Submission(s): 1868



Problem Description


有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。


 



Input


输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。


 



Output


输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。


 



Sample Input


2 1 8 4 4 7


 



Sample Output


0 1 0


 



Source







   裸威佐夫博奕,一直没搞明白,就是代码简单


     假设面对的局势是(a,b),若 b = a,则同时从两堆中取走 a 个物体,就变为了奇异局势(0,0);如果a = ak ,b > bk 那么,取走b - bk个物体,即变为奇异局势;如果 a = ak , b < bk 则同时从两堆中拿走a-a[b-a] 个物体变为奇异局势( a[b-a], b-a+a[b-a]);如果a > ak ,b= ak + k 则从第一堆中拿走多余的数量a - ak 即可;如果a < ak ,b= ak + k,分两种情况,第一种,a=aj (j < k)从第二堆里面拿走 b - bj 即可;第二种,a=bj (j < k)从第二堆里面拿走 b - aj 即可。


证明见 : http://baike.baidu.com/view/1952620.htm?fr=aladdin




#include<iostream>
#include<cmath>

using namespace std;

int main()
{
    int n,m;
    while(cin >> n >> m)
    {
        if(n > m)
        {
            int t;
            t = n;
            n = m;
            m = t;
        }
        double p = m - n;
        int mm = (sqrt(5.0)+1)*p / 2.0;
        if(mm == n)
        {
            cout << "0" << endl;
        }
        else
        {
            cout << "1" << endl;
        }
    }
    return 0;
}














标签:HDU,石子,两堆,ak,博弈论,000,bk,int,1527
From: https://blog.51cto.com/u_14834528/6210678

相关文章

  • kuangbin专题一 简单搜索 石油储备(HDU-1241)
    OilDepositsTimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)ProblemDescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangula......
  • HDU 1042 N! (大整数阶乘)
    这道题开始并不会,是看了别人的代码,自己又改造了一下,代码如下:(PS:这个时候自带大整数运算的java就有优势了)#include<bits/stdc++.h>usingnamespacestd;constintN=20000+10;intans[N];voidfact(intn){ans[0]=ans[1]=1;inttot=1;for(inti=......
  • HDU 1253 胜利大逃亡
    题目有个坑是可能没有到达门口的路,结果WA好几次#include<iostream>#include<cstdio>#include<queue>#include<algorithm>usingnamespacestd;constintINF=10000000;inta,b,c,d;ints[60][60][60],cost[60][60][60];intdx[]={0,0,1,-1,0,0}......
  • hdu 1272 小希的迷宫
    这是我第一次用并查集解决问题,其实刷这道题就是为了学习并查集,这是学长在hdu上找的模板题#include<iostream>#include<cstdio>usingnamespacestd;constintN=110000;intpar[N],mark[N];intfind1(intx){intr=x;while(par[r]!=r)r=par[r];......
  • HDU 5443 The Water Problem RMQ
    题目:http://acm.hdu.edu.cn/showproblem.php?pid=5443题意:给定一个数组,查询区间最大值思路:RMQ模板题#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>usingnamespacestd;constint......
  • HDU 2894 DeBruijin (欧拉回路)
    题目地址:HDU2894跟POJ1392基本一样的。。代码如下:#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include<stdio.h>......
  • HDU 1116 && POJ 1386 Play on Words(欧拉路径)
    按字母来建边,每个单词的首字母和尾字母加边。先判断是否连通,然后判断每个字母的入度和出度不能出现差的绝对值大于2,然后入度和出度差的绝对值为1的不能超过两个。就可以形成欧拉路径代码如下:#include<iostream>#include<string.h>#include<math.h>#include<queue>#include......
  • HDU 1878 欧拉回路 (并查集+欧拉回路)
    题目地址:HDU1878这个题要注意欧拉回路与欧拉通路的区别。在都保证连通性的前提下,欧拉回路要求每个点的度数都是偶数,而欧拉通路允许两个点的度数是奇数。所以这题用并查集判断连通性后判断下度数就可以了。代码如下:#include<iostream>#include<string.h>#include<math.h>#in......
  • HDU 2089 不要62 (数位DP)
    简单的数位DP。代码如下:#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include<stdio.h>usingnamespacestd;#d......
  • HDU 2842 Chinese Rings(矩阵快速幂+递推)
    题目地址:HDU2842这个游戏是一个九连环的游戏。假设当前要卸下前n个环。由于要满足前n-2个都卸下,所以要先把前n-2个卸下,需要f(n-2)次。然后把第n个卸下需要1次,然后这时候要卸下第n-1个,然后此时前n-2个都已经被卸下了。这时候把前n-2个都卸下与都装上所需的次数是一样的,因为卸下与装......