首页 > 代码库 > topcoder-srm701-div2-900 博弈\计算二进制位1的个数\dp\状态压缩

topcoder-srm701-div2-900 博弈\计算二进制位1的个数\dp\状态压缩

借用一下qls翻译过来的题面

 现在有 n 个石子,A 和 B 轮流取石子,A先,每次最多可以取 m 个石子,取到最后一个石子的人获胜,但是某个人如果取完石子时候剩余石子数的二进制表示中有奇数个1,这个人就输了
给定 n 和 m,问谁赢
n<=5e8, m<=50
TL 2s 
以前我是从来没接触过博弈的
首先普及一下博弈的基本知识。。
必胜态,必败态,以及必胜点与必败点
首先有一个字必须要看清楚,那就是“必”字
是必胜而不是,胜利就行,这个字很关键
技术分享

 

如图所示,一个点是p-position的条件是,他的前驱节点是必胜态

一个点是N-position则要求他的后继节点全部都是必败态(否则他是做不到必胜,记住。。是必胜)

那么我们可以得到,标记一个点的规则是,观察当前未被标记的点的所有后继节点,如果它的后继节点全部都

达到了必胜态,则这个点一定是必败态,我们就标记成必败态,如果它的后继节点中至少有一个点是必败态,那么

当前的这个点一定是必胜态,因为如果有必胜的方法,只要有,我们就一定会去选择他。

了解了这个之后就差不多了。。

首先。。一开始有n个石子,但是我们每个人都不会清楚当前如何决策是最优的,因为从n个石子的状态开始,

没有一个点的后继节点的状态是明确的,我们要至少找出一个具有明确状态的点才能继续我们的工作

这时候我们需要做的工作是,找到这个博弈情景中的终态,什么是终态呢。。第一,已经分出胜负,

第二,从这个状态开始再也无法移动,游戏无法进行下去了。

那么这个题,有两个终态,第一当你面对石子的时候,它已经剩下了0个,游戏结束,你无法做任何操作,并且你输掉了比赛

第二,当你面对这堆石子时,他的数量写成二进制的形式后有奇数个1,而题目中说了,如果当前移动后的结果是奇数个1,那么

移动的这个人就会输,那么换句话说,当你正好面对这奇数个1时,不用做任何操作,因为上一个人已经输了(按照题目中的游戏定义)

所以我们至少要按照定义找到至少一个有明确状态的点,当我们从n个石子的这个状态出发去考虑,我们发现如果它的儿子们没有明确的

状态,那我就只能去找它儿子的儿子们,那么我们发现这其实是一个递归地过程,最终我们会找到叶子节点(有明确状态的点)

然后根据前面介绍的博弈论的基础知识去回溯,因为我们知道所有的后继节点都有了明确的状态之后,那么我们可以很容易的推知

他们的父亲节点是什么状态

int dfs(int n,int m,int dep){

    if(ans[n]!=-1) {
        return ans[n];
    }
    if(n==0){
        return ans[n]=0;//终态为零时输掉
    }
    if(Count(n)%2==1){
        return ans[n]=1;//当前二进制位数为奇数
    }
    register int i;
    int res=dfs(n-1,m,dep+1);
    for(i=2;i<=m;++i){
        if(n-i>=0){
            res&=dfs(n-i,m,dep+1);
        }
    }
    if(res==1){
        return ans[n]=0;
    }
    else{
        return ans[n]=1;
    }
}

以上为递归程序的版本

我们清楚了这个过程之后,发现,一开始的递归找叶子节点(有明确状态的点)这一过程是多余的

因为我们知道应用何种知识去找出叶子节点,即终态的意义明确

所以我们可以从递归树的底部,直接回溯上去

void solve(int n,int m){
    int i,j;
    int res=0;
    int dp[m];
    for(i=1;i<=m;++i){
        dp[i]=1;
    }
    for(i=1;i<=n;++i){
        // cur=res;

        for(j=2;j<=m;++j){
            if(n-j>0){
                res&=dp[j];
            }
        }
        if(res==1) {
            res=0;
        }
        else{
            res=1;
        }
        if(Count(i)%2==1){
            res=1;
        }
        for(j=m;j>=2;++j){
            dp[j]=dp[j-1];
        }
        dp[1]=res;
    }
}

这个是递推程序的版本

为什么要开m大小的dp数组呢,这是因为,每个博弈的阶段,我们都有m个选择,选择1~m中的一个数,取出对应数的石子

能不能取,我们再说,到时候程序里判断一下就完事了

并且还有另外一个分析的方法,因为你是从递归树的底部往上推,那么你就需要知道上面那个点的所有子节点都是些什么

或者说如何找到它的所有子节点,那么我们知道因为你每个阶段最多作出m个决策(必胜必败,石子数不够的情况都会少于m个决策)

所以通过m我们就能找到它所有的后继节点的状态,因为每次都只用到了这m个状态,所以我们只存这m个状态,每次迭代即可

如何迭代呢?我们就要去分析一下递归树,每次这m个状态都是哪些状态(我都用到了哪m个状态),这个题呢,正好就是有规律的,不断用算出来的一直迭代

旧的状态就行,一定要自己画一画。

走到这一步。。我们注意到,我的dp数组里存的数,不是零就是1,而且m还比较小,最大50,那么long long是能存下的,这里有一个坑

那就是ll p=(1<<50);会溢出。。因为1默认是整型,必须要写成ll p=(1ll<<50)

所以我们考虑用long long来压m位,进行状态压缩。。,那么我怎么考虑我这m个状态的更新呢。。不用担心。。我们使用位运算

使用左移运算就能达到后面的位保存前面的位的效果。。但是这样的话,这个数就越来越大了,不是m位了。。会爆炸的。。所以

我们用一个m位全一的数跟压位的这个数做一下与运算,为的是这个m位全1的数的高位的零把压位的这个数的超过m位的不为1的位都截掉

然后最后一位用或运算更新状态即可。。这样就代替了上面的dp数组

void test(int n,int m){
    ll allwin=(1ll<<m)-1;
    ll nowstate=allwin;
    register int i,j;
    for(i=0;i<=n;++i){
        if(Count(i)&1||nowstate!=allwin){
            res=1;
        }
        else{
            res=0;
        }
        nowstate=((nowstate<<1)&allwin)|res;
    }
}

这里这个Count(int v)函数是用来计算一个数的二进制1的个数,显然这个时间复杂度是nlogn的

对于题目中的数据,这样铁定超时。。

所以说我们就要加速对于Count(n)的计算

然后呢。。我们注意到题目中n最大不会超过int,那么int一共有32位,我们可以用分治的思想

把它分成两半,那么一半就是1<<16了。。,于是乎。。我们就预处理出0~(1<<16)-1(16个1)这些数每个数有多少个1就行了

((pre[i>>16]+pre[i&((1<<16)-1)])&1)我们来理解一下,这个式子。。

前半句是说,取i的高16位,显然是在针对超过16位的i,如果i本来就不够16位,那么我们知道pre[0]=0;

那么后半句就是在说,把i的低十六位取出来。。

然后我们就能快速地预处理这个值了

我们还用到了一个__builtin_popcount,(注意前面有俩下划线。。。),这个是内置函数。。不需要头文件,这个函数算的还是贼快的。。

他能快速算出一个数有多少个二进制位的1

另外:string前面要加上std::

下面贴上代码

#include <iostream>
#include <cstdio>
#include <string.h>
#include <time.h>
#define ll long long
class ThueMorseGame{
public:
    int pre[1<<16];
    std::string get(int n,int m){
    int i;
    int res=0;
    ll allwin=(1ll<<m)-1;
    ll nowstate=allwin;
    for(i=0;i<(1<<16);++i){
        pre[i]=__builtin_popcount(i);
    }
    for(i=0;i<=n;++i){
        if(((pre[i>>16]+pre[i&((1<<16)-1)])&1)||nowstate!=allwin){
            res=1;
        }
        else{
            res=0;
        }
        nowstate=((nowstate<<1)&allwin)|res;
    }
    //i 从1开始,nowstate全是1,是不对的,因为有一个0的必败态
    //所以从零开始,初始化一下
    return (nowstate&1)?"Alice":"Bob";
    }
};
int main(){
    int st,ed;
    int n,m;
    scanf("%d%d",&n,&m);
    ThueMorseGame p;
    st=clock();
    std::string ans=p.get(n,m);
    ed=clock();
    std::cout<<ans<<" time:"<<(double)(ed-st)/CLOCKS_PER_SEC<<"s"<<std::endl;
    return 0;
}

 

 

topcoder-srm701-div2-900 博弈\计算二进制位1的个数\dp\状态压缩