麻将(mahjong) Input Output Example Scoring
“为什么, 你们的力量在哪里得到如此地 ”
“我们比 1 分钟前的我们还要进步, 虽然很微小, 但每转一圈就会前进一寸。这就是钻头啊!” “那才是通向毁灭的道路。为什么就没有意识到螺旋族的极限”
“那是你的极限。那只不过是在封闭的宇宙里, 象国王一样将其他生命困住的你自己的极限而已。给我记好了, 我们的钻头将在这片宇宙中钻开风洞。已经倒下的人们的愿望, 和后继迩来的人们的希望。将这两股思念交织成二重螺旋, 凿出驰骋于明天的未来之路。这就是天元突破! 这就是 Gurren Lagann! 我的钻头是开创天际的钻头!”
终于,GranzeBorma 爆炸了。
“那么, 这片宇宙, 一定要保护好 ”
西蒙回答了 Anti-Spiral 这最后的一句话。“那是当然。人类还没有愚蠢到那种地步”
Anti-Spiral 的终结, 化做为银河各地的螺旋族欢喜的信息, 从四面八方传来。
——在那这之后要说的话, 也所剩无几了。
回到地球后的妮亚与西蒙结了婚, 并且永远地离开了, 因为她是由 Anti-Spiral 创造出来的假想生命。但是在离别的那一瞬间, 妮亚与西蒙依然互相微笑着。
时光飞逝, 在地球大总统罗修的努力下, 全银河螺旋力和平利用会议得以召开。超银河大 Gurren 承载着地球的代表踏上旅途。还有通过新闻, 想起与大家的种种回忆的昔日大 Gurren 团的成员。
然后——
在一个远离市区的地方, 有一个男人教会了少年使用钻头的方法。夜空中,Gurren Lagann 画出螺旋的轨道, 从男人与少年的头顶飞过。在那前方, 螺旋的朋友们正在那片群星中等待着我们。
终于有一天,在这颗古老的星球上诞生了一种了不起的游戏——mahjong 游戏只使用万、筒、条三种花色,即以下 27 种牌面:
每一种牌面各有 4 张,总计 108 张牌。
胡牌的牌型为 4 个“句子”和 1 副“将牌”。
句子一共以下有两种形式:
- 三张相同花色且连续的牌,如图1
- 三张相同的牌,如图2
将牌:两张相同的牌,如:
当手牌构成 4 个“句子”和 1 副“将牌”时则构成胡牌牌型,如:
听牌:当 13 张手牌再加上某一张就能成胡牌牌型时称之为听牌,如:
听牌时再加上某一张就能胡牌,那我们就称那张牌是听的牌 如图牌型就听三、六条
现在你手中有 14 张牌,求打出第几张牌会使得你听得牌的张数最多,最多听多少张牌
一行 14 张牌,用空格隔开
1..9 表示牌上数字,w、p、s 分别表示万、筒、条,如 1s 表示一条
Output
一行两个数用空格隔开,分别表示打出第几张牌会使得你听得牌的张数最多以及最多听多少张牌 如果有多张牌使得打出后听得牌一样多,输出标号最靠前的
Example
mahjong.in |
mahjong.out |
|||||||||||
1s 7p |
2s 7p |
3s |
4s |
6s |
6s |
6s |
2w |
2w |
2w |
3p |
3p |
1 4 |
1s 8p |
1s 9p |
1s |
2s |
3s |
4s |
5s |
6s |
6p |
6p |
7p |
8p |
12 10 |
Explanation
样例 1:无论是打出 1s 还是 4s 都是听 3p 和 7p,而 3p 共有 4 张,手中已经有 2 张,牌堆中还剩 2
张,7p 也有 4 张,手中已经有 2 张,牌堆中还剩 2 张,所以打出 1s 听 4 张样例 2:打出 6p 或 9p 听 7p 共 3 张,打出 8p 听 1s、4s、7s、6p 共 10 张
Scoring
- 对于 30% 的数据,胡牌牌型中的句子只会是三张相同的牌。
对于另外 20% 的数据,14 张手牌同属于万、筒、条其中的某一种。注:测试点 6 时限 2s
这次比赛最大的收获——学会了打麻将!
思路:
像这样棋牌的暴搜,方法不难,难在用搜索来写出方法。因为给定的数量,数据量小,但枚举各种情况的步骤复杂,最适合暴搜啦
按照三种牌的类型和9个点数依次搜索,当前点数和类型的牌搜完指的是它和之前点数的牌都得到应有的安排,每层搜索都必须确保搜完才能进入下一层,否则,如果有牌没法和别的牌凑成句子或将,就证明当前情况不能胡牌;
用全局变量flag记录是否胡牌,当某种情况可以胡牌时,赋值true,之后回溯时再不进行任何向下搜索,直接返回退出DFS;
用变量z记录是否已经凑出将牌,如果已经凑出,此后不再考虑将牌的情况;
分以下几种情况讨论:
<1>当前搜到了点数10,即当前类型的牌搜完了,继续搜下一种类型的牌,如果已经彻底搜完了,就证明可以胡牌;
<2>当前点数和类型没有牌,继续下一层搜索;
<3>当前点数小于等于7并且其后两个点数都有牌,那么这三张牌可以当做一个句子;
<4>当前点数和类型牌的张数大于3,那么这三张牌可以当做一个句子;
<5>当前点数和类型牌的张数大于2,那么这两张牌可以当做一副将牌;
如何计算、输出结果不赘述,但要注意要输出标号最靠前的,在输入记录编号时只记录最前的即可
兴学长哒~
#include<cstdio> int sl[3][10],ans,mx,s; struct xh { int xh,z; }x[30]; bool dfs(int a,int b,int c,int d) { if(c&&d==4) return 1; if(a==3) return 0; bool re; int ta,tb; if(b==9) tb=1,ta=a+1; else tb=b+1,ta=a; if(sl[a][b]>1&&!c) { sl[a][b]-=2; re=dfs(a,b,1,d); sl[a][b]+=2; if(re) return 1; } if(sl[a][b]>2) { sl[a][b]-=3; re=dfs(ta,tb,c,d+1); sl[a][b]+=3; if(re) return 1; } if(b>2&&sl[a][b]&&sl[a][b-1]&&sl[a][b-2]) { sl[a][b]--,sl[a][b-1]--,sl[a][b-2]--; re=dfs(a,b,c,d+1); sl[a][b]++,sl[a][b-1]++,sl[a][b-2]++; if(re) return 1; } return dfs(ta,tb,c,d); } int main() { // freopen("mahjong.in","r",stdin),freopen("mahjong.out","w",stdout); char c; while(scanf("%d%c",&x[++s].xh,&c)!=EOF) { if(c=='p') x[s].z=2; else x[s].z=c=='w'; sl[x[s].z][x[s].xh]++; if(s==14) break; } for(int i=1;i<s;++i) { int jl=0; sl[x[i].z][x[i].xh]--; for(int j=0;j<3;++j) for(int k=1;k<10;++k) { sl[j][k]++; if(dfs(0,1,0,0)) jl+=5-sl[j][k]; sl[j][k]--; } sl[x[i].z][x[i].xh]++; if(jl>mx) mx=jl,ans=i; } printf("%d %d",ans,mx); return 0; }
注释代码^-^
#include<cstdio> int a[4][10],b[4][10],ans1,ans2; bool flag; void dfs(int x,int y,bool z)//(z表示是否已有将牌) { if(y==10) //如果当前点数到头 { if(x==4) flag=true; //如果当前花色到头 else if(!flag) dfs(x+1,1,z); return; } if(!a[x][y]) { dfs(x,y+1,z); return; } if(y<=7) //找顺子 { if(a[x][y+1]&&a[x][y+2]) { --a[x][y];--a[x][y+1];--a[x][y+2]; if(!flag) { if(a[x][y]) dfs(x,y,z); else dfs(x,y+1,z); } ++a[x][y];++a[x][y+1];++a[x][y+2]; } } if(a[x][y]>=3) //找三同 { a[x][y]-=3; if(!flag) { if(a[x][y]) dfs(x,y,z); else dfs(x,y+1,z); } a[x][y]+=3; } if(a[x][y]>=2&&!z) //找将牌,将牌已有则不再找 { a[x][y]-=2; if(!flag) { if(a[x][y])dfs(x,y,1); else dfs(x,y+1,1); } a[x][y]+=2; } return; } int main() { int t1;char t2; for(int i=1;i<=14;++i) { scanf("%d%c",&t1,&t2); //t1点数,t2花色 if(t2=='w') { ++a[1][t1]; //a[i][j] 记录 i 点数,j 花色的数量 if(!b[1][t1]) b[1][t1]=i; //b[i][j] 记录该牌的次序 } else if(t2=='p') { ++a[2][t1]; if(!b[2][t1]) b[2][t1]=i; } else { ++a[3][t1]; if(!b[3][t1]) b[3][t1]=i; } } for(int i=1;i<=3;++i) { for(int j=1;j<=9;++j) { if(!a[i][j])continue; //打出一张a[i][j],所以不能为0 --a[i][j]; t1=0; for(int k=1;k<=3;++k) //枚举所有能摸到的牌 { for(int l=1;l<=9;++l) { ++a[k][l]; //摸到a[k][l] dfs(1,1,false); if(flag) //如果能胡牌 { t1+=4-a[k][l]+1; //加上能听的a[k][l]的数量 flag=false; } --a[k][l]; } } if(t1>ans1) { ans1=t1; ans2=b[i][j]; } ++a[i][j]; } } printf("%d %d ",ans2,ans1); return 0; }