首页 > 其他分享 >hdu 2177 取(2堆)石子游戏 (博弈)

hdu 2177 取(2堆)石子游戏 (博弈)

时间:2023-07-18 19:38:32浏览次数:38  
标签:hdu temp 必败 石子 vis 2177 printf include dis


题意:有两堆石子,两人轮流取石子,轮到某人时,有两种取法,要么从两堆石子中同时取出一定数量的石子,要么只从一堆中取任意数量的石子,不能不取。不能取的人判为输。

普通思想:对于博弈问题,首先想到的就是sg函数。所以我们先从小到大的看局面。可以得出,对于每一种状态(x,y)x,y为石子堆。要么(x,y)本身是必败态,要么(x,y)就是必胜态,因为每种必胜态的(x,y)局面都可以通过同时从两堆取相同数量的石子或者从某一堆去一定数量的石子,使得对手面对的是必败态。下面介绍如何得出的:

(0,0)为必败态,(1,2)为必败态,这个是显然的,很显然了。不是那些大神的博客里的那些显然,那些显然一点都不显然。。。

然后可以推出:(3,5)为必败态,而(2,1)这种相反的就不用说了。对于某种必败态来说,其x,y值是确定的,若只改变其中一个值,则局面必然是必胜态。因为只要拿走多余的,则必然可以使得对手面对必败态。因此,我们只要从x=0开始一直往后面推算,只要x的值在之前的x和y中没有出现过,那么必然有一个y>x,使得(x,y)是必败态,而这个差值,根据推算,可以得出是逐一递增的,也就是每相邻的两个必败态的y-x的值只相差1.如:

0:(0,0)

1:(1,2)

2:(3,5)

3:(4,7)

4:(6,10)

...

根据上面的推式,我们可以用一个for循环得到所有的必败态。将其存放到一个数组里。然后我们再用一个一维数组保存y-x的差值得必败态的x的值,数组下标即为y-x。

根据上面两个数组,我们就可以计算出每一个局面先手的胜负,然后在输出的时候,我们要考虑的就是如果当前局面是必败态,则输出0,如果不是,则先看同时取,

对于同时取:根据y-x的差值,得到离其最近的必败态的x值,用当前x减去之就是同时取的石子数(若x小于它,则不能同时取),输出并记录,避免重复输出。

对于一堆取:根据x值所对应的必败态的y,与当前的y对比,若当前的大,则直接输出x的必败态,如比当前小,则判断y的必败态的y,与当前的x比,若比当前的小,则输出y的必败态。若小,不可能出现这种情况。(证明很简单,根据bk =  ak + k,可以得证)

到此所有情况都考虑到了,1A。(其实此题就是威佐夫博奕,下面会讲)

普通思想代码:

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;

const int MAX__ = 1000010;
int vis[MAX__],dis[MAX__];

void init(){
    int i;
    memset(vis,-1,sizeof(vis));
    vis[0] = 0;
    int tmp = 1;
    for(i = 1;i < MAX__;i++){
        if(vis[i]==-1){
            vis[i] = i+tmp;
            dis[tmp] = i;
            if(i+tmp < MAX__) vis[i+tmp] = i;
            tmp++;
        }
    }
}

int main(){
    //freopen("d:\\1.txt","w",stdout);
    int a,b, tmp1, tmp2;
    init();
    while(~scanf("%d%d",&a,&b),a||b){
        if(vis[a] == b || vis[b] == a){
            printf("0\n");
            continue;
        }
        printf("1\n");
        if(a == b){
            printf("0 0\n");
            if(vis[a] < b)  {
                printf("%d %d\n",min(a,vis[a]),max(a,vis[a]));
            }
            continue;
        }
        if(a == 0 || b == 0){
            printf("0 0\n");
            continue;
        }
        if((b-a == vis[dis[b-a]] - dis[b-a])
            ||(b-a == dis[b-a] - vis[dis[b-a]])){
                if(dis[b-a] < a){
                    tmp1 = min(vis[dis[b-a]],dis[b-a]);
                tmp2 = max(vis[dis[b-a]],dis[b-a]);
                printf("%d %d\n",min(vis[dis[b-a]],dis[b-a])
                       ,max(vis[dis[b-a]],dis[b-a]));
                }

            }
        if(vis[a] < b){


            if( tmp1 != min(a,vis[a]))
            printf("%d %d\n",min(a,vis[a]),max(a,vis[a]));
        }
        if(vis[b] < a){

            if( tmp1 != min(b,vis[b]))
            printf("%d %d\n",min(b,vis[b]),max(b,vis[b]));
        }
    }
    return 0;
}

 


威佐夫博奕:有两堆各若干个物品,两个人轮流从某一堆或同




时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。




这种情况下是颇为复杂的。我们用(ak,bk)(ak ≤ bk ,k=0,1,2,…,n)表示

两堆物品的数量并称其为 局势 ,如果甲面对(0,0),那么甲已经输了,这种局势我们



称为 奇异局势 。前几个奇异局势是:



(0,0)、



(1,2)、



( 3,5)、



(4,7)、



(6, 10)、



(8,13)、



(9,15)、



(11,18)、



(12,20)。



那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?我们有如下公式:



ak =[k(1+√5)/2],bk= ak + k  (k=0,1,2,…,n 方括号表示取整函数)



同样对应两种取法:



同取:利用公式:abs(temp-a)==abs(temp+k-b)且temp < a 则可以同时取,输出之



一堆取:对于局面(a,b),将1至b的所有奇异局势与a,b对比,若有一个值是相等的,则即为答案,输出之。






威佐夫博奕代码:



#include <iostream>
#include <math.h>
#include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{
    int a,b,temp,temp2,k,i, tmp;
    while(scanf("%d%d",&a,&b),a+b)
    {
        if(a>b)
            swap(a,b);
        k=b-a;    //求出差值
        temp=k*(1.0+sqrt(5.0))/2.0;    //求出差值对应的开头数
        if(a==temp)    //奇异局势
            printf("0\n");
        else
        {
            printf("1\n");
            if(abs(temp-a)==abs(temp+k-b) && temp < a){
            //取两堆中相同数量,判断差值是否相等
                printf("%d %d\n",temp,temp+k);
                tmp = temp;
            }

            //一堆中取
            if(a==0)    //0 0情况,第一种奇异局势
                printf("0 0\n");
            for(i=1;i<=b;i++)
            {
                temp=i*(1.0+sqrt(5.0))/2.0;    //开头
                if(temp == tmp)continue;
                temp2=temp+i;    

                if(temp==a)   
                    printf("%d %d\n",a,temp2);
                else if(temp2==a)
                    printf("%d %d\n",temp,a);
                else if(temp2==b)
                    printf("%d %d\n",temp,b);
            }
        }
    }
    return 0;
}




 

 

标签:hdu,temp,必败,石子,vis,2177,printf,include,dis
From: https://blog.51cto.com/u_16192154/6767440

相关文章

  • HDU 1595 find the longest of the shortest
    题意:对于题目给定的一个图,问去掉起点到终点的最短路径上的某一条边之后起点到终点的最短距离里的最大值。思路:先计算原图的最短路径,保存最短路径。枚举最短路径每一条边,删掉该边,然后计算最短路径,保留最大的那个即可。实现:先用一个spfa求得最短路径,用一个路径数组保存路径。然后枚举......
  • hdu 1142 A Walk Through the Forest
    WA了好多次了,大概是一直没搞清题意。题意:对边<a,b>,如果a到终点的距离小于b到终点的距离,那么b就可以到a,但是a就不能到b了,所以经过这样的一种筛选的方法之后,我们要在这样的图里寻找能从起点走到终点的路径的总数。思路:先算出每一点到终点的最小距离;然后dfs记忆化搜索路径总数。#incl......
  • hdu 1150 Machine Schedule
    二部图问题:每个任务的两种模式对应一条边,那么最大的匹配数就是最多的任务不用改变模式的任务数。相当于求最小点覆盖,而最小点覆盖=最大匹配数 代码:#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>usingnamespacestd;#defineMAXN110intuN,......
  • hdu Circular Area
    计算两圆相交的面积。参考文章:http://blog.sina.com.cn/s/blog_850498e20100w6fq.html  #include<iostream>#include<cstdio>#include<cstring>#include<cmath>usingnamespacestd;#defineINF0x3fffffff#defineMAXN100001#definepiacos(-1.0)#......
  • hdu 2227 Find the nondecreasing subsequences (树状数组+dp+离散化)
    题意:给定一个长度为n(n<=100000)的整数序列,求其中的递增序列的个数。对于某些序列中的递增序列的个数是可以用dp来求解的,其状态转移方程为:dp[i]=sum(dp[j])+1,j<i&&a[j]<a[i]根据状态转移方程可以得知这样dp的时间复杂度为O(n^2),而对于题目给定的10^6的数量级来说,这样......
  • hdu Polynomial Problem
     有点杂乱无章,考虑各种情况就行了。 #include<iostream>#include<cstdio>#include<cstring>#include<cmath>usingnamespacestd;#defineINF0x3fffffff#defineMAXN100001intmain(){intn,m,x,flag,mul,ans;charstr[MAXN];whil......
  • hdu 1010 Tempter of the Bone (dfs+奇偶剪枝)
    小记:最开始以为是T时间内,用bfsWA了,后来知道是刚好T时间,然后就用dfs,相当于暴力了,然后简单的dfs提交TLE,必须剪枝。首先判最少需要的时间是否有,没有就不用继续了,而如果有,那么因为我们是要花掉T时间刚好到达,那么我们先保证能走到终点的时间,然后在路上花掉多余的时间此时,我们必须保证......
  • 题解 HDU5726【GCD】/ LGT353762【Soso 的最大公约数】
    Problem给你一个长为\(N(1\leqN\leq1\times10^5)\)的整数序列:\(a_{1},\cdots,a_{n}(0<a_{i}\leq1\times10^9)\)。有\(Q(1\leqQ\leq1\times10^5)\)次提问。每次提问有个范围\(l,r\),你需要计算出\(\gcd(a_{l},,a_{l+1},...,a_{r})\),并且统计数对\((l’,r’......
  • 2023-07-05:爱丽丝和鲍勃继续他们的石子游戏 许多堆石子 排成一行,每堆都有正整数颗石
    2023-07-05:爱丽丝和鲍勃继续他们的石子游戏许多堆石子排成一行,每堆都有正整数颗石子piles[i]游戏以谁手中的石子最多来决出胜负。爱丽丝和鲍勃轮流进行,爱丽丝先开始。最初,M=1。在每个玩家的回合中,该玩家可以拿走剩下的前X堆的所有石子,其中1<=X<=2M然后,令M=max......
  • hdu 2604(矩阵快速幂)
    题意:f和m两种字母,给出l表示有2^l个由f和m组成长度为l的字符串,如果这些字符串内包含fmf或fff子串的是一种特殊字符串,给出l问不是特殊字符串的数量是多少。题解:先暴力把前几个l的答案跑了一下,发现有个规律f(n)=f(n-1)+f(n-3)+f(n-4),试着用这个公式写了矩阵快速幂交上去......