2021牛客OI赛前集训营-提高组（第三场） T4扑克

2021牛客OI赛前集训营-提高组（第三场）

题目大意

小A和小B在玩扑克牌游戏，规则如下：

从一副52张牌（没有大小王）的扑克牌中随机发3张到每个玩家手上，每个玩家可以任意想象另外两张牌，与自己手上的牌组成5张牌，已构成最大的手牌。

两幅手牌比较大小的规则如下：

如果牌型一致，则按关键牌组来比较。

小A可以知道小B手中的牌。小A决定对于每一次游戏都想象出一副刚刚好能赢小B的牌。请你告诉小A这两张牌分别是什么，或告诉他无法取胜。

题解

注意事项

• 玩家可以想象对方有的牌，但不能想象自己有的牌
• 小A的牌要在能赢小B的基础上尽量小，如果有两种花色都能赢小B，则优先选择花色小的

一些简化

• 因为无论三张牌如何，都至少可以通过想象得到三条，所以两对，一对和高牌可以不用考虑

做法

在不考虑花色的情况下，暴力枚举出所有五元组，五元组的数量并不多。然后将五元组排序，再求出所有三元组。

对于每次询问，将三元组对应的五元组进行比较，再考虑花色的影响，即可得出答案。

code

#include<bits/stdc++.h>
using namespace std;
int t,c1,vd,mxa,mxb,va,vb,sc,fl,ip[205],icl[205],z[20],zh[20],zp[10][20];
int tot=0,d[500005],l[500005],r[500005];
char op[20],ocl[10];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
struct node{int x,y;
}a[10],b[10];
struct five{int val,sh,a[10];
}w,ans,v[50005];
void init(){for(int i=2;i<=9;i++){ip[i+'0']=i;op[i]=i+'0';}ip['T']=10;ip['J']=11;ip['Q']=12;ip['K']=13;ip['A']=14;op[10]='T';op[11]='J';op[12]='Q';op[13]='K';op[14]='A';icl['S']=4;icl['H']=3;icl['C']=2;icl['D']=1;ocl[4]='S';ocl[3]='H';ocl[2]='C';ocl[1]='D';
}
void dfs(int t,int now){for(int i=now;i<=14;i++){if(z[i]<4){w.a[t]=i;++z[i];if(t<5) dfs(t+1,i);else v[++vd]=w;--z[i];}}
}
bool four_of_a_kind(){if(w.a[2]==w.a[3]&&w.a[3]==w.a[4]){if(w.a[1]==w.a[2]||w.a[4]==w.a[5]) return 1;}return 0;
}
bool full_house(){if(w.a[1]==w.a[2]&&w.a[2]==w.a[3]&&w.a[4]==w.a[5]) return 1;if(w.a[1]==w.a[2]&&w.a[3]==w.a[4]&&w.a[4]==w.a[5]) return 1;return 0;
}
bool three_of_a_kind(){if(w.a[1]==w.a[2]&&w.a[2]==w.a[3]) return 1;if(w.a[2]==w.a[3]&&w.a[3]==w.a[4]) return 1;if(w.a[3]==w.a[4]&&w.a[4]==w.a[5]) return 1;return 0;
}
void gt(){if(w.a[1]+1==w.a[2]&&w.a[2]+1==w.a[3]&&w.a[3]+1==w.a[4]&&w.a[4]+1==w.a[5]) w.sh=1;if(four_of_a_kind()){w.val=7e8+w.a[3]*14;if(w.a[1]!=w.a[3]) w.val+=w.a[1];else w.val+=w.a[5];}else if(full_house()){if(w.a[3]==w.a[1]) w.val=6e8+w.a[3]*15+w.a[5];else w.val=6e8+w.a[3]*15+w.a[1];}else if(w.sh) w.val=4e8+w.a[1];else if(three_of_a_kind()){w.val=3e8+w.a[3]*15*15;if(w.a[1]==w.a[2]&&w.a[2]==w.a[3]) w.val+=w.a[5]*15+w.a[4];else if(w.a[2]==w.a[3]&&w.a[3]==w.a[4]) w.val+=w.a[5]*15+w.a[1];else w.val+=w.a[2]*15+w.a[1];}
}
int find(int w1,int w2,int w3){return w1*15*15+w2*15+w3;
}
int dd(int g1,int g2,int w1,int w2,int w3){if(g2<w1){swap(g2,w1);if(w1<w2){swap(w1,w2);if(w2<w3) swap(w2,w3);}}if(g1<g2){swap(g1,g2);if(g2<w1){swap(g2,w1);if(w1<w2){swap(w1,w2);if(w2<w3) swap(w2,w3);}}}if(w3+1==w2&&w2+1==w1&&w1+1==g2&&g2+1==g1) return 1e8+w3;return g1*15*15*15*15+g2*15*15*15+w1*15*15+w2*15+w3;
}
void pt(){for(int i=1;i<=4;i++) zh[i]=0;for(int i=2;i<=14;i++) z[i]=0;++z[a[1].y];++zh[a[1].x];++zp[a[1].x][a[1].y];++z[a[2].y];++zh[a[2].x];++zp[a[2].x][a[2].y];++z[a[3].y];++zh[a[3].x];++zp[a[3].x][a[3].y];for(int i=5;i>=1;i--){if(z[ans.a[i]]) --z[ans.a[i]];else{if(fl) zp[a[1].x][ans.a[i]]=1;else{for(int j=1;j<=4;j++){if(!zp[j][ans.a[i]]&&zh[j]<4){++zh[j];zp[j][ans.a[i]]=1;break;}}}}}for(int i=2;i<=14;i++){for(int j=4;j>=1;j--){if(zp[j][i]){printf("%c%c ",ocl[j],op[i]);zp[j][i]=0;}}}
}
int main()
{init();dfs(1,2);for(int i=1;i<=vd;i++){w=v[i];gt();v[i]=w;add(find(w.a[1],w.a[2],w.a[3]),i);add(find(w.a[1],w.a[2],w.a[4]),i);add(find(w.a[1],w.a[2],w.a[5]),i);add(find(w.a[1],w.a[3],w.a[4]),i);add(find(w.a[1],w.a[3],w.a[5]),i);add(find(w.a[1],w.a[4],w.a[5]),i);add(find(w.a[2],w.a[3],w.a[4]),i);add(find(w.a[2],w.a[3],w.a[5]),i);add(find(w.a[2],w.a[4],w.a[5]),i);add(find(w.a[3],w.a[4],w.a[5]),i);}char ch[5];scanf("%d",&t);while(t--){fl=sc=0;for(int i=1;i<=3;i++){scanf("%s",ch);a[i]=(node){icl[ch[0]],ip[ch[1]]};}if(a[1].x==a[2].x&&a[2].x==a[3].x) sc=1;for(int i=1;i<=3;i++){scanf("%s",ch);b[i]=(node){icl[ch[0]],ip[ch[1]]};}mxb=0;vb=0;int vt=find(b[1].y,b[2].y,b[3].y);for(int i=r[vt];i;i=l[i]){mxb=max(mxb,v[d[i]].val);vb|=v[d[i]].sh;}if(b[1].x==b[2].x&&b[2].x==b[3].x){int g1=0,g[20];for(int i=14;i>=2;i--){if(i!=b[1].y&&i!=b[2].y&&i!=b[3].y){g[++g1]=i;if(g1>=2) break;}}mxb=max(mxb,500000000+dd(g[1],g[2],b[3].y,b[2].y,b[1].y));if(vb){mxb=9e8+min(10,b[1].y);if(b[1].y==10) mxb=1e9;}}mxa=2e9;va=0;vt=find(a[1].y,a[2].y,a[3].y);for(int i=r[vt];i;i=l[i]){if(v[d[i]].val>mxb&&v[d[i]].val<mxa){mxa=v[d[i]].val;ans=v[d[i]];}va|=v[d[i]].sh;}if(a[1].x==a[2].x&&a[2].x==a[3].x){int g1=0,g[20];for(int i=14;i>=2;i--){if(i!=a[1].y&&i!=a[2].y&&i!=a[3].y) g[++g1]=i;}for(int i=1;i<=g1;i++){for(int j=i+1;j<=g1;j++){vt=5e8+dd(g[i],g[j],a[3].y,a[2].y,a[1].y);if(vt>mxb&&vt<mxa){mxa=vt;fl=1;ans.a[1]=a[1].y;ans.a[2]=a[2].y;ans.a[3]=a[3].y;ans.a[4]=g[j];ans.a[5]=g[i];}}}if(va){for(int i=min(10,a[1].y);i+4>=max(a[3].y,6);i--){vt=9e8+i;if(i==10) vt=1e9;if(vt>mxb&&vt<mxa){mxa=vt;fl=1;ans.a[1]=i;ans.a[2]=i+1;ans.a[3]=i+2;ans.a[4]=i+3;ans.a[5]=i+4;}}}}if(mxa==2e9) printf("-1");else pt();printf("\n");}return 0;
}