AT_icpc2012autumn_b 题解

KSCD_ · 2024-07-08 10:27:00 · 题解

思路

发现从剩余的 45 张牌里选两张的方案数为 \frac{45\times44}{2}=990，每个人从七张牌中选五张的方案数为 \frac{7\times 6}2=28，总共需要处理的牌型有 990\times28\times2=55440 种，所以直接暴力搜出每一种即可。

另外还有一些处理牌型时能注意到的点：

• 每张牌是什么花色不重要，只需要知道五张牌是否同花色即可。
• 任意两种有区别的牌型均能分出大小。
• 所有比较均是先比较类型，再以某些牌的大小为关键字比较。

因此想到如果能把每种牌型都压成一个数，会更方便比较。所以代码中把牌的类型作为高位，其他关键字依次作为低位压成了一个数。而且这里只需要保证同种类型的牌型处理时位置对齐即可，不同类型之间已经由于最高位不同分出大小了。

一共才 55440 种牌型，且时限 20 秒，处理常数大点也能过，但我的代码大概用了 200 毫秒。

具体还是看代码吧，里面还写了几个函数来简化。

代码

#include<iostream>
#include<vector>
#include<cstdio> 
#include<algorithm>
#define pb push_back
#define int long long 
#define double long double
using namespace std;
const int P=1e17;
char tc[3];
struct card {int cl,rk;} my[3],op[3],pu[6];
bool eq(card x,card y) {return x.cl==y.cl&&x.rk==y.rk;} //判断两张牌是否相同 
bool chkgl(card x,card y) {return x.rk==y.rk?x.cl<y.cl:x.rk<y.rk;} //给每两张不同牌唯一的大小关系 
vector <card> temp,tem;
vector <int> rk,tk; //rk 为牌型，tk 为比较时的关键字 
int cnt,tcl,p[6];
int ccl(char ch)
{
    if(ch=='S') return 0;
    if(ch=='H') return 1;
    if(ch=='D') return 2;
    return 3;
} //转换花色 
int crk(char ch)
{
    if(ch>='2'&&ch<='9') return ch-'0';
    if(ch=='A') return 14;
    if(ch=='T') return 10;
    if(ch=='K') return 13;
    if(ch=='Q') return 12;
    return 11;
} //转换点数 
bool eqlr(int l,int r)
{
    for(int i=l+1;i<=r;i++) if(rk[i]!=rk[i-1]) return false;
    return true;
} //判断 rk 中 [l,r] 是否相等 
int flus()
{
    if(rk[4]==14)
    {
        bool tf=true;
        for(int i=0;i<4;i++) if(rk[i]!=i+2) tf=false;
        if(tf) return 1;
    }
    for(int i=1;i<5;i++) if(rk[i]!=rk[i-1]+1) return 0;
    return rk[0];
} //判断 rk 中的五张牌是不是顺子，若是，返回其最小值作为权值 
int so()
{
    int res=0,len=tk.size();
    for(int i=0;i<len;i++) res+=tk[i]*p[len-i-1];
    return res;
} //把 tk 中的比较关键字压缩成一个数字 
void ins(int x) {tk.pb(x);}
int sol()
{
    sort(rk.begin(),rk.end()); //先升序排序 
    if(tcl!=-2&&flus()) return P*9+flus(); //同花顺 
    if(eqlr(0,3)) {ins(rk[0]),ins(rk[4]); return P*8+so();}
    if(eqlr(1,4)) {ins(rk[1]),ins(rk[0]); return P*8+so();} //四张 
    if(eqlr(0,2)&&eqlr(3,4)) {ins(rk[0]),ins(rk[3]); return P*7+so();}
    if(eqlr(0,1)&&eqlr(2,4)) {ins(rk[2]),ins(rk[0]); return P*7+so();} //三带二 
    if(tcl!=-2) {for(int i=4;i>=0;i--) ins(rk[i]); return P*6+so();} //同花色 
    if(flus()) return P*5+flus(); //顺子 
    if(eqlr(0,2)) {ins(rk[0]),ins(rk[4]),ins(rk[3]); return P*4+so();}
    if(eqlr(1,3)) {ins(rk[1]),ins(rk[4]),ins(rk[0]); return P*4+so();}
    if(eqlr(2,4)) {ins(rk[2]),ins(rk[1]),ins(rk[0]); return P*4+so();} //三张 
    if(eqlr(1,2)&&eqlr(3,4)) {ins(rk[3]),ins(rk[1]),ins(rk[0]); return P*3+so();}
    if(eqlr(0,1)&&eqlr(3,4)) {ins(rk[3]),ins(rk[0]),ins(rk[2]); return P*3+so();}
    if(eqlr(0,1)&&eqlr(2,3)) {ins(rk[2]),ins(rk[0]),ins(rk[4]); return P*3+so();} //两对 
    for(int i=0;i<4;i++) if(rk[i]==rk[i+1])
    {
        ins(rk[i]);
        for(int j=4;j>=0;j--) if(j!=i&&j!=i+1) ins(rk[j]);
        return P*2+so();
    } //一对 
    for(int i=4;i>=0;i--) ins(rk[i]);
    return P+so(); //单牌 
}
int solv()
{
    tcl=-1,rk.clear(),tk.clear();
    for(card k:tem) rk.pb(k.rk),tcl=((tcl==-1||tcl==k.cl)?k.cl:-2);
    return sol();
} //判断 tem 中五张牌是否同花色，不同则 tcl=-2，同时把点数传到 rk 中 
int solve()
{
    int res=-1;
    for(int i=0;i<7;i++) for(int j=i+1;j<7;j++)
    {
        tem.clear();
        for(int k=0;k<7;k++) if(k!=i&&k!=j) tem.pb(temp[k]);
        res=max(res,solv());
    }
    return res;
} //枚举 temp 中七张牌选五张（不选两张）的方案，并传到 tem 计算最大值 
void check()
{
    if(eq(pu[4],pu[5])||chkgl(pu[4],pu[5])) return;
    for(int i=4;i<=5;i++)
    {
        for(int j=1;j<=2;j++) if(eq(pu[i],my[j])||eq(pu[i],op[j])) return;
        for(int j=1;j<=3;j++) if(eq(pu[i],pu[j])) return;
    } //判断没有牌重复 
    int mysc,opsc; temp.clear();
    for(int i=1;i<=5;i++) temp.pb(pu[i]);
    temp.pb(my[1]),temp.pb(my[2]),mysc=solve(),temp.pop_back();
    temp.pop_back(),temp.pb(op[1]),temp.pb(op[2]),opsc=solve(); //分别把各自的七张牌传到 temp 中计算 
    cnt+=(mysc>opsc);
} //对于每种 pu[4],pu[5] 的情况计算是否获胜 
signed main()
{
    p[0]=1;  for(int i=1;i<=5;i++) p[i]=p[i-1]*1000;
    while(cin>>tc)
    {
        if(tc[0]=='#') break;
        cnt=0,my[1]={ccl(tc[0]),crk(tc[1])};
        cin>>tc,my[2]={ccl(tc[0]),crk(tc[1])};
        for(int i=1;i<=2;i++) cin>>tc,op[i]={ccl(tc[0]),crk(tc[1])};
        for(int i=1;i<=3;i++) cin>>tc,pu[i]={ccl(tc[0]),crk(tc[1])}; //存储牌 
        for(pu[4].cl=0;pu[4].cl<4;pu[4].cl++) for(pu[4].rk=2;pu[4].rk<=14;pu[4].rk++)
        for(pu[5].cl=0;pu[5].cl<4;pu[5].cl++) for(pu[5].rk=2;pu[5].rk<=14;pu[5].rk++) check(); //枚举 
        printf("%.8Lf\n",(double)cnt/990);
    }
    return 0;
}