2012ACM天津赛区的一道题目。
很复杂的模拟,没有完全想清楚前别着急敲。我重写了2次代码才过。。。
题意不难理解,思路也很容易得到,枚举所有的牌,看加上这一张牌后能不能胡。
胡牌有3种规则:
1、 7对, 这种情况的判断只需要判断所有的牌是不是0或者2,出现其他情况直接false
2、十三幺,只要判断这十三张牌都出现过,并且没有出现过其他牌。
3、平胡,1个对子+4个组合(三张相同的,或者连续递增的。注意c类牌只能存在三张相同的组合)
首先任意选出一个对子,dfs看剩下的牌能不能凑成4个组合。
600+ms
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; struct node { int x,y; }ans[100]; int sum[4][15]; bool f1() { for(int i=0;i<4;i++) for(int j=1;j<=9;j++) if(sum[i][j]&&sum[i][j]!=2) return false; return true; } bool f2() { for(int i=0;i<3;i++) for(int j=1;j<=9;j+=8) if(!sum[i][j]) return false; for(int i=0;i<3;i++) for(int j=2;j<=8;j++) if(sum[i][j]) return false; for(int i=1;i<=7;i++) if(!sum[3][i]) return false; return true; } inline void fun(int j,int i,int num) { for(int k=i;k<=i+2;k++) sum[j][k]+=num; } bool dfs(int s) { if(s==4) return true; for(int j=0;j<3;j++) for(int i=1;i<=9;i++) { if(!sum[j][i]) continue; if(sum[j][i]&&!sum[j][i-1]&&!sum[j][i+1]&&sum[j][i]<=2) return false; if(sum[j][i]>=3) { sum[j][i]-=3; if(dfs(s+1)) {sum[j][i]+=3;return true;} sum[j][i]+=3; } if(sum[j][i]&&sum[j][i+1]&&sum[j][i+2]) { fun(j,i,-1); if(dfs(s+1)) {fun(j,i,1);return true;} fun(j,i,1); } } return false; } bool istrue() { int tot=0; for(int i=1;i<=7;i++) { if(!sum[3][i]) continue; if(sum[3][i]==3) tot++; else return false; } return dfs(tot); } bool f() { for(int j=0;j<4;j++) for(int i=1;i<=9;i++) { if(sum[j][i]>=2) { sum[j][i]-=2; if(istrue()) {sum[j][i]+=2;return true;} sum[j][i]+=2; } } return false; } int main() { char mp['z'];mp['m']=0;mp['s']=1;mp['p']=2;mp['c']=3; char mpp[]="mspc"; int t,a,j,tot; char b; scanf("%d",&t);getchar(); while(t--) { tot=0; memset(sum,0,sizeof(sum)); for(int i=1;i<=13;i++) { scanf("%d%c",&a,&b);getchar(); sum[mp[b]][a]++; tt[mp[b]]++; } for(j=0;j<4;j++) for(int i=1;i<=9;i++) { if(j==3&&i>7) break; if(sum[j][i]==4) continue; sum[j][i]++; if(f2()) { ans[tot].x=i; ans[tot++].y=j; } else if((sum[j][i]==1||sum[j][i]==4)&&sum[j][i-1]==0&&sum[j][i+1]==0) {sum[j][i]--;continue;} else if(f1()||f()) { ans[tot].x=i; ans[tot++].y=j; } sum[j][i]--; } if(!tot) {printf("Nooten\n");continue;} printf("%d",tot); for(int i=0;i<tot;i++) printf(" %d%c",ans[i].x,mpp[ans[i].y]); puts(""); } return 0; }