「bsoj5152」麻将 - 枚举+搜索+Hash | Bill Yang's Blog

「bsoj5152」麻将 - 枚举+搜索+Hash

题目大意





题目分析

看到题的时候:MMP又一道斗地主&@#$@&&%&^#@。
看完题后:良心出题人!

枚举将哪张牌打出去,再枚举收回哪张牌,然后检验是否构成胡牌。
检验构成胡牌的方法是:搜索

因为每次搜索必定少三张牌,因此很快即可得解,事实上我还用了玄学剪枝:若留下落单的牌(旁边都没有牌,且不构成将牌以上),则剪掉。

注意考试的时候没考虑打出去的牌不能再收回来的特殊情况,因此rejudge后丢掉$10$分,事实上也没人会打麻将啊~~

将$Hash$表的花色之间设置间隔,可以少作一些判断。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int Hash[55],a[15],Ans=0,ans=0;
bool Cut(int Down) {
for(int i=Down; i<=min(Down+2,33); i++)
if(Hash[i]&&!((i>=3&&Hash[i-2]&&Hash[i-1])||(i>1&&i<33&&Hash[i-1]&&Hash[i+1])||(i<32&&Hash[i+1]&&Hash[i+2])||Hash[i]>=2))return true;
return false;
}
bool Dfs(int Depth,int Last) {
if(Depth==5) { //将牌
for(int i=1; i<=33; i++)
if(Hash[i]==1)return false;
return true;
}
if(Cut(Last))return false;
for(int i=Last; i<=33; i++)
if(Hash[i]) {
if(Hash[i]>=3) {
Hash[i]-=3;
bool bj=Dfs(Depth+1,i);
Hash[i]+=3;
if(bj)return true;
}
if(Hash[i]&&Hash[i+1]&&Hash[i+2]) {
Hash[i]--;
Hash[i+1]--;
Hash[i+2]--;
bool bj=Dfs(Depth+1,i);
Hash[i]++;
Hash[i+1]++;
Hash[i+2]++;
if(bj)return true;
}
}
return false;
}
bool Judge(int x) {
Hash[x]++;
for(int i=1; i<=33; i++)
if(Hash[i]&&!((i>=3&&Hash[i-2]&&Hash[i-1])||(i>1&&i<33&&Hash[i-1]&&Hash[i+1])||(i<32&&Hash[i+1]&&Hash[i+2])||Hash[i]>=2)) {
Hash[x]--;
return false;
}
bool bj=0;
if(Dfs(1,1))bj=1;
Hash[x]--;
return bj;
}
int Check(int x) {
Hash[x]--;
int ans=0;
for(int i=1; i<=9; i++)
if(i==x&&Hash[i]<3&&Judge(i))ans+=3-Hash[i];
else if(i!=x&&Hash[i]<4&&Judge(i))ans+=4-Hash[i];
for(int i=13; i<=21; i++)
if(i==x&&Hash[i]<3&&Judge(i))ans+=3-Hash[i];
else if(i!=x&&Hash[i]<4&&Judge(i))ans+=4-Hash[i];
for(int i=25; i<=33; i++)
if(i==x&&Hash[i]<3&&Judge(i))ans+=3-Hash[i];
else if(i!=x&&Hash[i]<4&&Judge(i))ans+=4-Hash[i];
Hash[x]++;
return ans;
}
int main() {
for(int i=1; i<=14; i++) {
int x,v;
char y;
scanf("%d%c",&x,&y);
if(y=='s')v=x;
else if(y=='w')v=x+12;
else v=x+24;
Hash[v]++;
a[i]=v;
}
for(int i=1; i<=14; i++) {
int x=Check(a[i]);
if(x>Ans) {
ans=i;
Ans=x;
}
}
printf("%d %d\n",ans,Ans);
return 0;
}
本篇文章有用吗?有用还不快点击!
0%