抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

洛谷-P7147题解

题解洛谷

发布于：2024年12月20日

luogu 阅读链接。

前言

麻将模拟器
调了一早上结果发现 DP 中的 jj 写成 ii 了。
题目中的和牌距离基本和向听数差不多。
文中的面子指刻子和顺子的统称。

基础操作

定义

#define endl '\n'   
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)   
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)   
#define pc putchar   
struct player{   
	int a[20], len;   
	bool pass;   
}p[4];   
int cd[200], top, turn = 1;

我们用一个 player 结构体存一个玩家的信息，分别是玩家手中的牌，牌的数量，是否被 pass。
cd 用来存牌堆，top 表示最上面的牌，turn 是回合顺序。

牌面存储

因为直接存储牌是字符，并不利于判断优先级。
所以我们在输入的时候先转化成优先级，输出时再换回字符。

//main内   
FR(i, top = 148, 1){   
	string s;   
	cin >> s;   
	//转化   
	if(isdigit(s[0]))   
		switch(cd[i] = s[0] ^ 48, s[1]){   
			case 'S':cd[i] += 9;   
			case 'P':cd[i] += 9;   
		}   
	else switch(cd[i] = 28, s[0]){   
			case 'P':cd[i]++;   
			case 'R':cd[i]++;   
			case 'D':cd[i]++;   
			case 'Z':cd[i]++;   
			case 'F':cd[i]++;   
			case 'B':cd[i]++;   
			case 'N':cd[i]++;   
			case 'W':cd[i]++;   
			case 'S':cd[i]++;   
		}   
}   
//优先级->字符   
void outcd(int x){   
	if(x <= 27)cout << (x - 1) % 9 + 1 << ("MPS"[(x - 1) / 9]);   
	else if(x <= 34)cout << ("ESWNBFZ"[x - 28]);   
	else if(x == 35) cout << "DOUBLE";   
	else if(x == 36) cout << "REVERSE";   
	else cout << "PASS";   
}

输出操作

#define in(x, y)pc(x + 'A'), cout << " IN ", outcd(y), pc(endl)   
#define nxt(x) (((x) + turn + 4) % 4)   
#define out(x, y) pc(x + 'A'), cout << " OUT ", outcd(y), (y == 37) && (pc(' '), pc(nxt(x) + 'A')),  pc(endl)   
#define outpeng(x, y) pc(x + 'A'), cout << " PONG ", outcd(y), pc(' '), outcd(y), pc(' '), outcd(y), pc(endl)   
#define outchi(x, y) pc(x + 'A'), cout << " CHOW ", outcd(y), pc(' '), outcd(y + 1), pc(' '), outcd(y + 2), pc(endl)   
void GameOver(int x, int y){   
	if(x == -1)cout << "DRAW", exit(0);   
	pc(x + 'A'), cout << (y ? " RON" : " SELFDRAWN") << endl;   
	pc(x + 'A'), cout << " WIN", exit(0);   
}

这部分就没什么好说的，注意 pass 的输出特判。

摸牌和删牌

可以将每个人手中的牌按优先级维护，好判断特殊牌。

//摸牌   
void mopai(int x){   
	if(!top)GameOver(-1, 0);   
	int *a = p[x].a, z = upper_bound(a + 1, a + p[x].len + 1, cd[top]) - a;   
	FR(i, p[x].len, z)a[i + 1] = a[i];   
	a[z] = cd[top--], p[x].len++, in(x, a[z]);   
}   
//出牌   
void delpai(int x, int y){   
	int *a = p[x].a, z = lower_bound(a + 1, a + 1 + p[x].len, y) - a;   
	FL(i, z, --p[x].len)a[i] = a[i + 1];   
}

和牌距离

我们来看最难的和牌距离部分。

我们定义：
dpi,j,k,l,gdp_{i,j,k,l,g} 表示前第 ii 种牌中有 jj 个面子和 kk 个对子，且第 i−1i - 1 种牌开始有 gg 个顺子，第 ii 种牌开始有 gg 个顺子，时的和牌距离。
zyi,j,k,l,gzy_{i,j,k,l,g} 表示此时要丢弃的优先级最高牌。
nxnx 表示现在能转移的状态的和牌距离，nyny 表示需要丢弃的牌。

我们再枚举一个 qq 表示需要 qq 张第 ii 种牌，rr 表示除顺子后剩下的。

如果我们剩余的牌能凑出刻子，那么我们就可以转移到 i+1,j+l+1,k,g,r−3i+1,j+l+1,k,g,r-3。
如果能凑出对子，可以转移到 i+1,j+l,k,g,r−2i+1,j+l,k,g,r-2。
我们也可以开启新的顺子，可以转移到 i+1,j+l,k,g,ri+1,j+l,k,g,r。

转移（dp′,zy′dp',zy' 表示新状态）：
如果 nx<dp′nx < dp'，那么 dp′←nx,zy′←nydp' \gets nx, zy' \gets ny。
如果 nx=dp′,ny>zy′nx = dp',ny > zy'，那么 zy′←nyzy' \gets ny。

具体细节可以看代码。

int sl[40], dp[40][5][2][3][3], zy[40][5][2][3][3];//sl 表示每种牌的数量   
#define zhuanyi(i, j, k, l, g) if(nx < dp[i][j][k][l][g] || (nx == dp[i][j][k][l][g] && ny > zy[i][j][k][l][g])) dp[i][j][k][l][g] = nx, zy[i][j][k][l][g] = ny   
pair<int, int> JuLi(int x){//求和牌距离与要弃的牌，x 表示最后有几个面子   
	memset(dp, 0x3f, sizeof(dp)), memset(zy,-1,sizeof(zy));   
	dp[0][0][0][0][0] = 0;   
	FL(i, 0, 34) FL(j, 0, x) FL(k, 0, 1)    //前第 i 种牌，有 j 个面子，k 个对子   
		FL(l, 0, min(2, x - j)){            //从第 i - 1 种牌开始的 l 个顺子   
			FL(g, 0, min(2, x - l - j))     //从第 i 种牌开始的顺子   
				if(dp[i][j][k][l][g] <= 14){//状态合法   
					FL(q, l + g, 4){   
						int nx = dp[i][j][k][l][g] + max(0, q - sl[i + 1]);  //新的和牌距离   
						int ny = (sl[i + 1] > q ? i + 1 : zy[i][j][k][l][g]);//要打出的牌   
						int r = q - l - g; //剩了几个第 i 种牌   
                        //可以凑出刻子   
						if(r >= 3 && j + l + 1 <= x)zhuanyi(i + 1, j + l + 1, k, g, r - 3);   
                        //可以凑出对子   
						if(r >= 2 && !k)zhuanyi(i + 1, j + l, 1, g, r - 2);   
                        //开启新的顺子   
						if(r <= 2)zhuanyi(i + 1, j + l, k, g, r);   
					}   
                    //字牌不能组成顺子   
					if(i % 9 == 0 || i >= 27) break;   
				}   
			if(i % 9 == 0 || i >= 27) break;   
		}   
	return make_pair(dp[34][x][1][0][0], zy[34][x][1][0][0]);   
}   
pair<int, int> check(int x){//统计除了特殊牌的其他牌面   
	memset(sl, 0, sizeof(sl));   
	int *a = p[x].a, &len = p[x].len;   
	FL(i, 1, len) if(a[i] <= 34) ++sl[a[i]];   
	return JuLi(4 - (14 - len) / 3);   
}

游戏部分

框架部分

//main内部   
FL(i, 1, 13)FL(j, 0, 3)mopai(j);   
int now = 0;   
while(1){   
	if(p[now].pass)p[now].pass = 0, now = nxt(now);   
	else mopai(now), now = chupai(now);   
}

出牌阶段

bool TeShuPai(int x){//没有特殊牌才可能和   
	FL(i, 1, p[x].len)if(p[x].a[i] >= 34)return 0;   
	return 1;   
}   
int chupai(int x){   
	int *a = p[x].a, &len = p[x].len;   
    //有特殊牌直接打   
	if(a[len] == 37)return --len, p[nxt(x)].pass = 1, out(x, 37), nxt(x);   
	if(a[len] == 36)return --len, turn *= -1,  out(x, 36), nxt(x);   
	if(a[len] == 35)return --len, out(x, 35), x;   
	int chu = check(x).second;	//要打出的牌   
	if(chu == -1)GameOver(x, 0);//自摸   
	delpai(x, chu), out(x, chu);   
    //先判断荣和   
	for(int i = nxt(x); i != x; i = nxt(i))   
		if(TeShuPai(i)){   
			p[i].a[++p[i].len] = chu;   
			if(check(i).second == -1)GameOver(i, 1);   
			p[i].len--;   
		}   
	//然后是碰   
	int z = Peng(chu);   
	if(z != -1)return chupai(z);   
	//吃   
	if(Chi(nxt(x), chu))return chupai(nxt(x));   
	return nxt(x);   
}

特殊牌的优先级最高，有就直接打。
否则就看一下是不是自摸，不然就打出去。
荣和的比碰、吃都在前面，但是有截和，注意判断顺序。
而吃碰后不用摸牌，直接跳到出牌阶段。

碰

碰就比吃的可能少多了，注意要和牌距离要严格变小才会碰。

int Peng(int y){   
	FL(i, 0, 3){   
		int z = check(i).first;//原本的和牌距离   
		if((sl[y] -= 2) >= 0)  //至少要两张   
			if(z > JuLi(3 - (14 - p[i].len) / 3).first)//和牌距离严格变小   
				return outpeng(i, y), delpai(i, y), delpai(i, y), i;   
	}   
	return -1;   
}

吃

只有下家能吃，但有三种可能。

bool Chi(int x, int y){//判断吃，注意判断顺序，优先级越大越好。   
	if(y > 27)return 0;   
	int z = check(x).first;   
	if((y - 1) % 9 <= 6 && sl[y + 1] && sl[y + 2]){   
		sl[y + 1]--, sl[y + 2]--;   
		if(z > JuLi(3 - (14 - p[x].len) / 3).first)   
			return outchi(x, y), delpai(x, y + 1), delpai(x, y + 2), 1;   
		++sl[y + 1], ++sl[y + 2];   
	}   
	if(y % 9 > 1 && y % 9 != 0 && sl[y - 1] && sl[y + 1]){   
		sl[y - 1]--, sl[y + 1]--;   
		if(z > JuLi(3 - (14 - p[x].len) / 3).first)   
			return outchi(x, y - 1), delpai(x, y - 1), delpai(x, y + 1), 1;   
		++sl[y - 1], ++sl[y + 1];   
	}   
	if((y - 1) % 9 >= 2 && sl[y - 1] && sl[y - 2]){   
		sl[y - 1]--, sl[y - 2]--;   
		if(z > JuLi(3 - (14 - p[x].len) / 3).first)   
			return outchi(x, y - 2), delpai(x, y - 1), delpai(x, y - 2), 1;   
		++sl[y - 1], ++sl[y - 2];   
	}   
	return 0;   
}

代码

大功告成！
代码（约5KB）

更新于：2024年12月30日

题解

模拟