BZOJ-2804 [Ctsc2012]showhand

n+e posted @ 2015年7月03日 21:04 in BZOJ with tags 模拟 容斥原理 , 750 阅读

以前被学长说非常丧的题...

然而其实事实不是这样...只需要对一副牌,算出它的牌型、点数和花色就好了。

接下来重载一个小于号,sort一下

再接下来容斥。由于对于A的每一副牌,它对答案的贡献是B手中<A这幅牌的牌数,并且两者没有公共牌。

后一个用容斥原理,假设有三张牌为 $a,b,c$,那么贡献为

$tot-cnt_a-cnt_b-cnt_c+cnt_{a,b}+cnt_{a,c}+cnt_{b,c}-cnt_{a,b,c}$

可以发现状态数是$2^5$,如果强行对于每副牌hash,最大的hash值为4e ($52^5$)

然而事实上A与B不可能取到两幅相同的牌,于是可以把31去掉变成30。这样的话最大的hash值为 $52^4$,就不用开hash表了。

/**************************************************************
    Problem: 2804
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:19552 ms
    Memory:121128 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
typedef long long ll;
int Y[5][2],Z[5][2],tot,n,now,vis[15][4],f[7400000];ll ansx,ansy,g;
struct P{int a[5],kind,x,y,c;}p[2600000];
bool operator<(const P&a,const P&b){
    if(a.kind!=b.kind)return a.kind<b.kind;
    return a.x!=b.x?a.x<b.x:a.y<b.y;
}
template<class T>void init_P(T&t){
    tot++;
    for(int i=0;i<5;i++)p[tot].a[i]=t[i][0]*4+t[i][1];
    std::sort(p[tot].a,p[tot].a+5,std::greater<int>());
    static int a[5],b[5],cnt_a[15],cnt_b[4];
    int max_a=0,min_a=13,max_b=0,max_t=0,tot_a=0,tot_b=0,kind=0,x=0,y=0;
    for(int i=0;i<5;i++){
        a[i]=p[tot].a[i]/4,b[i]=p[tot].a[i]&3;
        if(!cnt_a[a[i]]++)tot_a++;
        if(!cnt_b[b[i]]++)tot_b++;
        if(a[i]>max_a)max_a=a[i];
        if(a[i]<min_a)min_a=a[i];
        if(cnt_b[b[i]]>max_b)max_b=cnt_b[b[i]];
        if(cnt_a[a[i]]>max_t)max_t=cnt_a[a[i]];
    }
    if(tot_a==5&&tot_b==1){
        if(a[0]==12&&a[1]==3&&a[2]==2&&a[3]==1&&a[4]==0)kind=8,x=-1,y=b[1];
        else if(max_a-min_a==4)kind=8,y=b[0];
        if(kind==8&&x!=-1)for(int i=0;i<5;i++)x|=1<<a[i];
    }
    if(!kind&&tot_a==2&&max_t==4){
        kind=7;
        for(int i=0;i<5;i++)if(cnt_a[a[i]]==4)x|=1<<a[i],y|=1<<b[i];
    }
    if(!kind&&tot_a==2&&max_t==3){
        kind=6;
        for(int i=0;i<5;i++)if(cnt_a[a[i]]==3)x|=1<<a[i],y|=1<<b[i];
    }
    if(!kind&&tot_b==1){
        kind=5;y=b[0];
        for(int i=0;i<5;i++)x|=1<<a[i];
    }
    if(!kind&&tot_a==5){
        if(a[0]==12&&a[1]==3&&a[2]==2&&a[3]==1&&a[4]==0)kind=4,x=-1,y=b[1];
        else if(max_a-min_a==4)kind=4,y=b[0];
        if(kind==4&&x!=-1)for(int i=0;i<5;i++)x|=1<<a[i];
    }
    if(!kind&&tot_a==3&&max_t==3){
        kind=3;
        for(int i=0;i<5;i++)if(cnt_a[a[i]]==3)x|=1<<a[i],y|=1<<b[i];
    }
    if(!kind&&tot_a==3&&max_t==2){
        kind=2;int max=0;
        for(int i=0;i<5;i++)if(cnt_a[a[i]]==2){
            x|=1<<a[i];
            if(a[i]>max)max=a[i];
        }
        x<<=13;
        for(int i=0;i<5;i++){
            if(cnt_a[a[i]]==1)x|=1<<a[i];
            if(a[i]==max)y|=1<<b[i];
        }
    }
    if(!kind&&tot_a==4&&max_t==2){
        kind=1;
        for(int i=0;i<5;i++)if(cnt_a[a[i]]==2)x|=1<<a[i],y|=1<<b[i];
        x<<=13;
        for(int i=0;i<5;i++)if(cnt_a[a[i]]==1)x|=1<<a[i];
    }
    if(!kind){
        for(int i=0;i<5;i++)x|=1<<a[i];y=1<<b[0];
    }
    p[tot].x=x,p[tot].y=y,p[tot].kind=kind;p[tot].c=now;
    for(int i=0;i<5;i++)cnt_a[a[i]]--,cnt_b[b[i]]--;
}
template<class T>void dfs(T&t,int x,int a,int b){
    if(x==5)init_P(t);
    else for(int i=a;i<13;i++)
    for(int j=i==a?b:0;j<4;j++)if(!vis[i][j]){
        t[x][0]=i,t[x][1]=j;
        vis[i][j]=1,dfs(t,x+1,i,j+1),vis[i][j]=0;
    }
}
void calc(int id){
    for(int s=1,x,y,j;s<=30;y&1?ansx-=f[x]:ansx+=f[x],s++)
    for(x=y=j=0;j<5;j++)if(s&(1<<j))y++,x=x*52+p[id].a[j];
}
void hash(int id){
    for(int s=1,x,j;s<=30;f[x]++,s++)
    for(x=j=0;j<5;j++)if(s&(1<<j))x=x*52+p[id].a[j];
}
ll gcd(ll x,ll y){return!y?x:gcd(y,x%y);}
ll comb(int n,int k){
    ll s=1;
    for(int i=n,j=1;j<=k;i--,j++)s=s*i/j;
    return s;
}
int main(){
    scanf("%d",&n);
    for(int i=0,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        if(x==1)x=14;y=4-y;x-=2;
        Y[i][0]=x,Y[i][1]=y,vis[x][y]=1;
    }
    for(int i=0,x,y;i<n-1;i++){
        scanf("%d%d",&x,&y);
        if(x==1)x=14;y=4-y;x-=2;
        Z[i][0]=x,Z[i][1]=y,vis[x][y]=1;
    }
    dfs(Y,n,0,0);now=1;dfs(Z,n-1,0,0);std::sort(p+1,p+1+tot);
    for(int i=1,j=0;i<=tot;i++)if(!p[i].c)ansx+=j,calc(i);else j++,hash(i);
    ansy=comb(53-2*n,5-n)*comb(48-n,6-n),g=gcd(ansx,ansy),ansx/=g,ansy/=g;
    if(ansx==0)puts("0/1");else printf("%lld/%lld\n",ansx,ansy);
}
---By n+e

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter