[CCPC2015][HDU5548]Mahjong解题报告

题目



给定点数为1~K的麻将牌各4张(这4张完全相同),问有多少种方案,从中选出一个M张牌组成的集合,能够和牌。“和牌”指:其中有两张完全相同的将牌,其他牌可以被三三分组,每组要么是“n-1 n n+1”型,要么是“n n n”型。注意:集合相同而和法不同仅算一次。

题解

我们考虑这样一个命题:如果给定一个集合,能否和牌。这是一个很简单的DP:大致是:f[i][n2][n1][p]={0,1},其中i是到了点数为i的,n2是以i-2开始的连牌组数,n1以i-1的连牌组数,p是是否有将牌。对于点数为i的牌,枚举是否从中选取将牌,尔后贪心转移即可。

我们可以发现:这样的(n2,n1,p)的状态只有3*3*2=18个(n2,n1<=2,p<=1)。换言之:用一个长度为18的01数即可表示出某个状态的所有DP情况。我们设这个状态是s,那么对于原先的题目,如果开一个DP数组:F[i][s],表示到了点数为i的牌,到达DP情况为s的方案数。不妨把这个s想象成某种“虚拟机”,F[i][s]就是到达这个“虚拟机”的方案数。在最后,如果“虚拟机”中代表结束的状态为1,就代表能够和牌。

但是还有个问题:2^18显然太大,我们不能都存下来。怎么办呢?实际上我们可以发现,合法的“虚拟机”个数很少(仅有68)个,先BFS把它们都找出来,哈希一下编个号即可。

这个做法是队友@KuribohG告诉我的,当时惊为天人,因为这个算法背后的思想十分深刻。它在一个DP的基础上进行了更高一层的抽象,实质上是在下标里储存了全部的DP信息,即一个“虚拟机”。

代码

#include
#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=210;
const int MOD=1000000000+7;
int get(int s,int k){
    return (s>>k)&1;
}
int change(int s,int k,int t){
    s&=(~(1<=3) n0-=3;
    return n0;
}
int state_goto(int s0,int n0,int jiang){
    int n2,n1,p;
    decode(s0,n2,n1,p);
    if(p&&jiang) return -1;
    int t0=trans(n2,n1,n0,jiang);
    if(t0==-1) return -1;
    return encode(n1,t0,p|jiang);
}
int VM_goto(int vm0,int n0){
    int vm1=0;
    for(int s0=0;s0<3*3*2;s0++){
        if(!get(vm0,s0)) continue;
        for(int p=0;p<=1;p++){
            int s1=state_goto(s0,n0,p);
            if(s1!=-1){
                vm1=change(vm1,s1,1);
            }
        }
    }
    return vm1;
}
map Dict;
int cnt=0;
int table[SIZEN][SIZEN]={0};
bool success[SIZEN]={0};
queue Q;
bool add_state(int vm){
    if(!Dict.count(vm)){
        Dict[vm]=cnt;
        Q.push(vm);
        if(get(vm,encode(0,0,1))) success[cnt]=true;
        cnt++;
        return true;
    }
    return false;
}
void BFS_states(void){
    int vm0=0;
    vm0=change(vm0,encode(0,0,0),1);
    add_state(vm0);
    while(!Q.empty()){
        vm0=Q.front();Q.pop();
        for(int i=0;i<=4;i++){
            int vm1=VM_goto(vm0,i);
            add_state(vm1);
            table[Dict[vm0]][i]=Dict[vm1];
        }
    }
}
int N,M;
int F[SIZEN][SIZEN][SIZEN];
void add(int &a,int b){
    a+=b;
    a%=MOD;
}
void work(void){
    static int kase=0;
    int vm0=0;
    vm0=change(vm0,encode(0,0,0),1);
    memset(F,0,sizeof(F));
    F[0][0][Dict[vm0]]=1;
    for(int i=1;i<=N+3;i++){
        int h=i>N?0:4;
        for(int j=0;j<=M;j++){
            for(int id=0;id

发表评论

电子邮件地址不会被公开。 必填项已用*标注