水の斗牛

0
15011418730 LV 7 @ 2025-8-24 22:06:11
自动搬运

查看原文

来自洛谷，原作者为

Eason_AC
Remember? / AFOed on 2022.6.14 / 彻底死咯

搬运于2025-08-24 22:06:11，当前版本为作者最后更新于2020-08-15 23:42:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Update
- $\texttt{2020.8.18}$ 修改了一些格式上的问题。
- $\texttt{2020.10.26}$ 新增了一个提醒。
Content

这题不好弄题意简述啊，说个大概吧，就是 $n$ 个人玩 $T$ 局斗牛游戏，问你 $T$ 局过后 $n$ 个人的分数。

规则自己去看题目去。

数据范围：$0\leqslant T\leqslant 100000,3\leqslant n\leqslant 100000$。

Gossip

这题目真的是卡了我好久，调了大概有 $1$ 天吧，反正坑点挺多的就对了。交了大概有 $20$ 多次，之前没过的时候，分数一直在 $40\sim70$ 之间。

我当时在讨论区里问某个点的时候，某位红名大佬还给我回复道：

当时我就被吓着了，什么？迷你猪国杀？！然而，当时我看到通过数只有可怜的 $29$ ，于是我就下定了决心要过了这题目。

Solution

正如出题者 $\texttt{CYJian}$ 大神在当时的赛后题解中所述，这题目就是直接模拟，不过需要考虑很多的细节。

看目前的两篇题解都没解释清楚具体的步骤（包括但不限于直接用注释讲解），所以我在这里将具体步骤跟大家讲讲。

首先要有一个大概的框架。这个大家应该都清楚，我下面就把大致的思路图摆出来。

没错，一场斗牛就是这四个步骤，首先我们要发牌，发到 $3$ 个人手里（一场斗牛有 $3$ 个玩家），然后再通过预处理，得到每个人的牌型，接着，两两比拼，按照规则加减分，最后将分数统计出来。

那么接下来就是细节化的问题了。

0 变量定义 and 注意事项

为了避免之后的过程中造成的误解，我先把每一个变量下个定义：

一位玩家有以下的系数：
- $card_j$ 表示该玩家拥有的第 $j$ 个牌的点数。
- $col_j$ 表示该玩家拥有的第 $j$ 个牌的花色。特别注意！在这里，我们默认花色用一个大于等于 $1$ 且小于等于 $4$ 的整数表示，并且 $1$ 代表方块， $2$ 代表梅花， $3$ 代表红桃， $4$ 代表黑桃。接下来会讲到这么做的用意。
- $num_j$ 表示该玩家拥有的点数为 $j$ 的牌的个数，接下来会讲到这么做的用意。
- $sum$ 表示该玩家拥有的所有的牌的点数之和，即为 $\sum\limits_{j=1}^5card_j$ 。接下来会讲到这么做的用意。
- $niu$ 表示该玩家所拥有的这副牌的牛数，其中牛牛在此处用 $10$ 表示，牛一至牛九则用 $1\sim9$ 表示，至于无牛就用 $0$ 来表示。接下来会讲到这么做的用意。
- $tieban$ 表示该玩家拥有的这幅牌的铁板的点数。没有铁板用 $0$ 表示。
- $bomb$ 表示该玩家拥有的这幅牌的炸弹的点数，没有炸弹用 $0$ 表示。
- $maxx$ 表示该玩家拥有的这副牌中点数最大的牌的点数。接下来会讲到这么做的用意。
- $idd$ 表示该玩家拥有的这副牌中点数最大的牌的最大花色。接下来会讲到这么做的用意。
- $score$ 表示该玩家目前的分数。
还有，不保证本题解不会很长，所以请做好心理准备。

1 发牌

发牌是以上这四个步骤中算比较简单的一步，但是需要注意的地方也很多。

发完牌之后最重要的一步就是处理出这张牌的点数和花色。我们发现，只有点数为 $10$ 时，这张牌用题目所用的字符串中的第二个字符为 $1$ ；只有点数为 $1$ ，这张牌用题目所用的字符串中的第二个字符为 $\text{A}$ 。

所以，处理点数时，我们只需要特判上面两种情况，剩下的就直接将数字字符转换为数字了，这里想必无需多说。

花色也只需要对应存储就行。

你以为发牌到这里就完了？

那么我上面用的这么多变量岂不都是摆设了吗？

那么之后预处理该怎么办？

所以，我们需要用到上面这些变量来存储信息。具体来说， $sum$ 需要加上这张牌的点数， $num$ 将这张牌的点数在这副牌中出现的次数加 $1$ ，并且更新 $maxx$ 和 $idd$ 的值。尤其要注意更新 $maxx$ 和 $idd$ 的操作，就是因为这里出现了差错导致我的程序一直超不过 $70$ 分。在这里特别讲一下。

首先，我们假设手里有这样两张牌：黑桃10和红桃10，并假设红桃10是在比较之前 $maxx$ 和 $idd$ 的所属牌。那么，由于红桃10的花色比黑桃10的要小，所以肯定首选是黑桃10，用黑桃10的点数和花色信息将 $maxx$ 和 $idd$ 更新。

所以发牌的过程就模拟完了。

2 预处理出牌型

接下来就要预处理牌型了。

笔者提醒：在看这一部分时强烈建议去做 P6014，这样的话可以对这一部分有更加深的理解。另外，您也可以参考 P6014 处理好这一部分的细节问题。

根据大小顺序，我们先把炸弹处理，再把铁板和牛数一起处理。

那么这里 $num$ 就起到作用了。它直接可以判定是否有炸弹和铁板（根据定义显然可以推出来）。所以我们可以利用 $num$ 将炸弹和铁板处理出来。注意，一旦有炸弹，后面就不要再处理了，但是有铁板，千万不要立马退出，因为比较牌型的时候是按照牛数排序，所以我们要等在没有铁板的情况下的牛数处理完再去比较，权衡一下利弊。

那么一般情况的牛数怎么算呢？

我们都知道， $5^2=25,5^3=125$ 。但这有什么用呢？

我们这么想，如果我们直接枚举三个牌的点数，那么它的循环次数就是 $5^3=125$ 次，对于 $T\leqslant 100000,n\leqslant 100000$ 的数据来说有些玄，那么我们能否有减少循环次数的办法呢？

如果我们只用枚举两个牌的点数的话，循环次数就是 $5^2=25$ ，大大减少了时间。那么能够想到什么办法？

还记得我们之前提到的 $sum$ 吗？

这里就应该让它起作用了！

因为前面我们已经预处理出了 $sum$ ，所以我们直接枚举两个牌的点数，将 $sum$ 减去这两张牌的点数就是剩下三张牌的点数！

那么判断该如何呢？

设我们枚举的两张牌的点数分别是 $card_a$ 和 $card_b$ 。我们都知道，两个被一个数取模有相同余数的两个数相减得到的数，必定被这个模数整除。所以，我们的判断条件即为是否有 $card_a+card_b\equiv sum \pmod{10}$ 。有的话更新这个牛数。特别注意，如果 $10\mid card_a+card_b$ 的话，那么这牌就是最好的牛牛，我们更新牛数的时候将其更新为 $10$ ，这样就能和其他牛数以及无牛相区分开来了。

那么这里的牛数弄完之后，我们再和之前铁板的牛数相比较，如果铁板的牛数大于等于没有铁板的牛数，那么有铁板的情况肯定是最优的。这时我们将最终的牛数定为有铁板时的牛数。否则，因为我们首先要比较牛数，所以应该将没有铁板时的牛数定为最终的牛数。这里特别说明一下有铁板的牛数等于一般情况的牛数的情况。因为有铁板的话还可以翻倍，所以肯定它的牌型是比没铁板时的高的，所以我们应该选有铁板的牌型。

那么预处理牌型也弄完了。

3 两两比拼

这里有很多的坑点，可以说是本题的关键。

因为炸弹是最大的牌型，所以我们先比较炸弹。

因为在前面我们定义了如果没有炸弹则将 $bomb$ 记为 $0$ ，所以直接比较就好了，有炸弹或者炸弹大的狂加 $100$ 分，没炸弹或者炸弹小的狂扣 $100$ 分。

对于测试点 $3,4$ ，就相当于一个炸弹大战了。

那么炸弹比较完我们再来比较牛数。如果牛数大就是牛数大的那方赢，所以直接根据大的一方的牛数翻倍就好了，如果牛数大的那方还有铁板，分数就再 $\times2$ 。如果牛数相等的话，就看有没有铁板，因为没有铁板是我们也规定将 $tieban$ 变为 $0$ ，所以也是直接比较一下，如果一方有铁板或者铁板大就是那一方赢，并且因为TA有铁板，所以分数 $\times2$ 。但是如果两方都没有铁板呢？那么根据其最大的牌的点数进行比较，如果还是相等？根据花色进行比较。这里 $maxx$ 和 $idd$ 就起到了作用。如果比出来了结果，就再根据胜方的牛数进行翻倍，至于铁板……因为没有铁板就没必要再去比较了。

如果都是无牛牌型呢？题目里已经讲得很明白，就和相同牛数且均无铁板时的处理办法一样，这里不再赘述了。

那么到这里，两两比拼也结束了。

4 统计分数

这个倒没什么必要讲的，直接利用 $score$ 来储存分数就行，到最后一把输出完事。

那么这个题目到这里就讲完了，自己去代码实现的时候注意一亿些细节就好。希望我这篇题解能够帮到更多人！（鞠躬

Code

目前我的 $5$ 个 $\color{MediumSpringGreen}\texttt{AC}$ 记录中的最优记录是 $\texttt{1.36s/26.60MB}$ ，在所有 $\color{MediumSpringGreen}\texttt{AC}$ 记录中排第 $4$ ，虽说空间占得有点多（估计是因为这么多变量的原因），但是时间上还是比较快速的。很神奇的是将这个最优的代码开 $\texttt{O2}$ 后再交居然比原来不开 $\texttt{O2}$ 还要多出 $\dfrac{1}{5}$ 的时间。

Orz排在我前面的三位巨佬 $\texttt{So\underline{ }Interesting}$ （ $\texttt{1.05s/16.37MB}$ ）， $\texttt{Richard\underline{ }for\underline{ }OI}$ （ $\texttt{1.09s/11.62MB}$ ）和 $\texttt{wjyyy}$ （ $\texttt{1.21s/12.14MB}$ ）（截至 $\texttt{2020.8.17}$ ）。

（ $\texttt{Update on 2020.8.18)}$

忽然发现用 $\texttt{unordered\underline{ }map}$ 会快很多，于是超越了 $\texttt{wjyyy}$ 巨佬。不过还是得膜TA。

引用 $\texttt{Konjacq}$ 巨佬的原文所述，unordered_map内部实现是hash表，map内部实现是平衡树，所以可以大大提高算法效率。
```
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <unordered_map>
#define F(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
using namespace std;

int useless, t, n;
struct player {
	string name;
	int card[7], num[17], col[7], sum, niu, tieban, maxx, bomb, idd;
	long long score;
	/*
		card：记每个牌的点数
		num：记每种点数出现在的牌的数量
		col：记每张牌的花色 
		sum：记所有牌点数的和 
		niu：记牌的类型
			niu=0-10 无牛、牛一至九、牛牛 
		tieban：记录铁板的点数，如果没有铁板则记为0。 
		maxx：记录所有牌中最大的点数
		bomb：记录炸弹的点数，如果没有炸弹则记为0. 
	*/
}a[100007];
unordered_map<string, int> hashmap;

inline void cle(int id) {
	memset(a[id].card, 0, sizeof(a[id].card));
	memset(a[id].num, 0, sizeof(a[id].num));
	memset(a[id].col, 0, sizeof(a[id].col));
	a[id].sum = a[id].niu = a[id].tieban = a[id].maxx = a[id].bomb = a[id].idd = 0;
}
inline void premission(int t3) {
	F(i, 1, 5) {
		string cards;
		cin >> cards;
		if(cards[1] == '1' && cards[2] == '0')	a[t3].card[i] = 10;
		else if(cards[1] == 'A')	a[t3].card[i] = 1;
		else	a[t3].card[i] = cards[1] - '0';
		a[t3].sum += a[t3].card[i];
		a[t3].num[a[t3].card[i]]++;
		if(cards[0] == 'a')	a[t3].col[i] = 4;
		if(cards[0] == 'b')	a[t3].col[i] = 3;
		if(cards[0] == 'c')	a[t3].col[i] = 2;
		if(cards[0] == 'd')	a[t3].col[i] = 1;
		if(a[t3].card[i] > a[t3].maxx) {
			a[t3].maxx = a[t3].card[i];
			a[t3].idd = a[t3].col[i]; 
		} else if(a[t3].card[i] == a[t3].maxx && a[t3].col[i] > a[t3].idd)
			a[t3].idd = a[t3].col[i];
	}
	F(i, 1, 5) {
		if(a[t3].num[a[t3].card[i]] == 4) {
			a[t3].bomb = a[t3].card[i];
			break;
		}
		if(a[t3].num[a[t3].card[i]] == 3) {
			a[t3].tieban = a[t3].card[i];
			if(!((a[t3].sum - a[t3].card[i] * 3) % 10))	a[t3].niu = 10;
			else	a[t3].niu = (a[t3].sum - a[t3].card[i] * 3) % 10;
		}
		F(j, 1, 5) {
			if(i == j)	continue;
			if((a[t3].card[i] + a[t3].card[j]) % 10 == a[t3].sum % 10) {
				int p = a[t3].niu;
				if(!((a[t3].card[i] + a[t3].card[j]) % 10))	a[t3].niu = 10;
				else	a[t3].niu = max(a[t3].niu, (a[t3].card[i] + a[t3].card[j]) % 10);
				if(a[t3].niu > p)	a[t3].tieban = 0;
			}
		}
	}
}
inline void pk(int id1, int id2) {
	int difen = 10, sf = 0;
	if(a[id1].bomb > a[id2].bomb) {
		sf = 1;
		difen *= 10;
	} else if(a[id1].bomb < a[id2].bomb) {
		sf = 2;
		difen *= 10;
	} else if(!a[id1].bomb && !a[id2].bomb) {
		if(a[id1].niu > a[id2].niu) {
			if(a[id1].niu == 10)
				difen *= 3;
			else if(a[id1].niu >= 7 && a[id1].niu <= 9)
				difen *= 2;
			else
				difen *= 1;
			if(a[id1].tieban)	difen *= 2;
			sf = 1;
		} else if(a[id1].niu < a[id2].niu) {
			if(a[id2].niu == 10)
				difen *= 3;
			else if(a[id2].niu >= 7 && a[id2].niu <= 9)
				difen *= 2;
			else
				difen *= 1;
			if(a[id2].tieban)	difen *= 2;
			sf = 2;
		} else if(a[id1].niu == a[id2].niu && a[id1].niu) {
			if(a[id1].tieban > a[id2].tieban) {
				if(a[id1].niu == 10)	difen *= 3;
				else if(a[id1].niu >= 7 && a[id1].niu <= 9)	difen *= 2;
				else	difen *= 1;
				difen *= 2;
				sf = 1;
			} else if(a[id1].tieban < a[id2].tieban){
				if(a[id2].niu == 10)	difen *= 3;
				else if(a[id2].niu >= 7 && a[id2].niu <= 9)	difen *= 2;
				else	difen *= 1;
				difen *= 2;
				sf = 2;
			} else if(a[id1].tieban == a[id2].tieban) {
				if(a[id1].maxx > a[id2].maxx)
					sf = 1;
				else if(a[id1].maxx < a[id2].maxx)
					sf = 2;
				if(sf == 1) {
					if(a[id1].niu == 10)	difen *= 3;
					else if(a[id1].niu >= 7 && a[id1].niu <= 9)	difen *= 2;
					else 	difen *= 1;
					if(a[id1].tieban)	difen *= 2;
				} else if(sf == 2) {
					if(a[id2].niu == 10)	difen *= 3;
					else if(a[id2].niu >= 7 && a[id2].niu <= 9)	difen *= 2;
					else	difen *= 1;
					if(a[id2].tieban)	difen *= 2;
				}
				else {
					if(a[id1].idd > a[id2].idd) {
						sf = 1;
						if(a[id1].niu == 10)	difen *= 3;
						else if(a[id1].niu >= 7 && a[id1].niu <= 9)	difen *= 2;
						else	difen *= 1;
						if(a[id1].tieban)	difen *= 2;
					}
					else if(a[id1].idd < a[id2].idd) {
						sf = 2;
						if(a[id2].niu == 10)	difen *= 3;
						else if(a[id2].niu >= 7 && a[id2].niu <= 9)	difen *= 2;
						else	difen *= 1;
						if(a[id2].tieban)	difen *= 2;
					}
				}
			}
		} else if(!a[id1].niu && !a[id2].niu) {
			if(a[id1].maxx > a[id2].maxx)
				sf = 1;
			else if(a[id1].maxx < a[id2].maxx)
				sf = 2;
			else {
				if(a[id1].idd > a[id2].idd)
					sf = 1;
				else if(a[id1].idd < a[id2].idd)
					sf = 2;
			}
		}
	} 
	if(sf == 1)	a[id1].score += difen, a[id2].score -= difen;
	else	a[id1].score -= difen, a[id2].score += difen; 
}

int main() {
	scanf("%d%d%d", &useless, &t, &n);
	F(i, 1, n) {
		cin >> a[i].name;
		hashmap[a[i].name] = i;
	}
	while(t--) {
		string s1, s2, s3;
		int t1, t2, t3;
		cin >> s1; t1 = hashmap[s1];
		premission(t1);
		cin >> s2; t2 = hashmap[s2];
		premission(t2);
		cin >> s3; t3 = hashmap[s3];
		premission(t3);
		pk(t1, t2);
		pk(t1, t3);
		pk(t2, t3);
		cle(t1), cle(t2), cle(t3);
	}
	F(i, 1, n) {
		cout << a[i].name;
		printf(" %lld\n", a[i].score);
	}
	return 0;
}
```
看在我写了这么多的份上，不点个赞再走嘛qwq。