自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:30:31，当前版本为作者最后更新于2021-03-21 21:27:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

准备工作

这部分主要讲解如何将牌型映射到对 $p$ 的操作上。观察到牌型总共分为两大类，普通牌与解牌，于是分别考虑。

$1.$ 普通牌

对于普通牌，我们能够发现每种牌型对 $p$ 的操作都可以用形如 $p\gets \left\lfloor p\cdot a+b\right\rfloor$ 来表示，其中 $a,b$ 是仅与这种牌型有关的常数。经过简单地讨论，我们可以找出所有这样的 $a,b$ ：

$$\def\arraystretch{1.5}\begin{array}{||c|c|c||c|c|c||}\hline \textbf{牌型} & \boldsymbol{a} & \boldsymbol{b} &\textbf{牌型} & \boldsymbol{a} & \boldsymbol{b} \cr \hline A_1 & 1 & 1 & B_1 & 1 & -1\cr\hline A_2 & 1 & 2 & B_9 & 1 & -9\cr\hline A_5 & 1 & 5 & B_{19} & 1 & -19\cr\hline A_9 & 1 & 9 & C_2 & 2 & 0 \cr\hline A_{19} & 1 & 19 & D_2 & 0.5 & 0\cr\hline A_{49} & 1 & 49 & E_0 & 0 & 0\cr\hline A_{99} & 1 & 99 & E_{49} & 0 & 49\cr\hline && & E_{99} & 0 & 99\cr\hline \end{array}$$

具体实践的时候，我们可以开一个 $\text{map}$ ，将 $\text{string}$ 映射到对应的二元组 $(a,b)$ 。

$2.$ 解牌

对于解牌，因为一共才只有 $3$ 种，所以我们实际模拟的时候再进行考虑。使用带符号整型 $d$ 存储 $1$ 或 $-1$ ，用于判断当前顺序是顺时针还是逆时针；使用布尔型 $f$ 存储当前玩家是否处于 $\text{DOUBLE}$ 状态。三种牌型的处理方式如下：

• $\textbf{PASS}$ ：这部分处理起来比较简单，你只要直接跳过当前玩家就行了。

• $\textbf{TURN}$ ：也比较简单，直接令 $d\gets -d$ ，然后跳过该名玩家。

• $\textbf{DOUBLE}$ ：相对复杂的一部分。我们令 $f=\verb!true!$ ，然后跳过该名玩家。对于 $\text{DOUBLE}$ 状态的主要处理方式，将会在下一部分进行讲解。

---

对于玩家手牌的存储，只要对每名玩家开一个 $\text{map}$ （标记为 $H_{1},H_{2}\cdots$ ），将卡牌名映射到该名玩家持有该卡牌的数量就行了（其实也可以用 $\text{multiset}$ 之类的）。主要好处是，我们可以使用 $\text{STL}$ 自带的 $\text{auto}$ 功能快速遍历每名玩家持有的所有手牌。

使用手牌

在下文，我们使用 $o$ 表示当前玩家的序号。

$1.$ 删除手牌

我们新建函数 $\text{del(c)}$ ，来删除当前玩家手上的牌 $c$ 。这部分非常简单，你只需要 $H_{o,c}\gets H_{o,c}-1$ 就行了。每当删除一张牌，都要从牌堆获取另外一张牌。用 $\text{string}$ 类型的数组 $K$ 存储牌堆中的牌，你只要令 $kk\gets kk+1$ ，然后获取 $K_{kk}$ 即可。删除后，记得输出删除信息。

$2.$ 普通牌

我们新建函数 $\text{useA(v)}$ ，来处理当前玩家使用普通牌的情况，返回一个布尔值表示玩家是否使用成功。特别地，我们传入一个布尔变量 $v$ 用于表示此时需要使 $p$ 最大还是最小。

此时可以用 $\text{auto}$ 枚举该名玩家所有手牌。因为 $\text{useA}$ 函数只考虑普通牌，所以我们直接忽略特殊牌就行了。用 $W_1\sim W_5$ 存储每类普通牌产生的最大/最小值，用 $F_1\sim F_5$ 存储对应的牌（$\text{string}$ 类型）。对于手头的普通牌，我们计算出 $p'$ ，表示使用它后 $p$ 会变成的数值。如果它不超过 $99$ ，那就去更新对应的 $W_i$ 和 $F_i$ 就行了。

枚举完之后，按照题目规定的顺序（依次考虑乘法牌、加法牌、减法牌、除法牌、固定牌，或者依次考虑除法牌、减法牌、加法牌、乘法牌、固定牌）从 $W_1\sim W_5$ 中挑选出能使得 $p$ 最大/最小的手牌并使用，接着令 $f\gets \verb!false!$ ，然后返回 $\verb!true!$ 。如果无论如何都会超过 $99$ ，就不决策，并返回 $\verb!false!$ 。

$3.$ 解牌

我们新建函数 $\text{useB()}$ ，来处理当前玩家使用解牌的情况，返回一个布尔值表示玩家是否使用成功。依次判断玩家手头有没有这三张牌，如果有，那就按照“准备工作”章节中的做法处理后删除掉这张牌，并返回 $\verb!true!$ 。否则返回 $\verb!false!$ 。

模拟

该部分将讲述如何利用上述函数处理游戏主要过程。

• 初始时，输入所有牌，令 $o\gets 1$ 。这是整局游戏开始时的预处理操作。

• 对于每一轮，依次进行处理。每一轮开始时令 $d\gets 1,p\gets 0$ 。讨论此时 $f$ 的情况，可分为以下 $4$ 个 $\text{Label}$ ，每种 $\text{Label}$ 的对应情况分别是：当前未处于 $\text{DOUBLE}$ 状态；当前处于 $\text{DOUBLE}$ 状态；跳转到下一名玩家；该名玩家成为失败者。初始时根据 $f$ 的值跳转至 $\text{Label 1}$ 或 $2$ 。

  • $\text{Label 1}$ ：当前 $f=\verb!false!$ 。依次考虑 $\text{useA(\verb!true!)}$ 和 $\text{useB()}$ ，如果可行就跳转到 $\text{Label 3}$ ，否则跳转到 $\text{Label 4}$ 。

  • $\text{Label 2}$ ：当前 $f=\verb!true!$ 。如果 $\text{useB()}$ 返回 $\verb!true!$ 并跳至 $\text{Label 3}$ ；否则根据 $\text{useA(\verb!false!)}$ 决定跳至 $\text{Label 1}$ 还是 $\text{Label 4}$ 。

  • $\text{Label 3}$ ：令 $o\gets p+d$ 。如果 $o=n+1$ ，就令 $o=1$ ；如果 $o=0$ ，就令 $o=n$ ，比较显然。

  • $\text{Label 4}$ ：输出该名玩家失败的信息，结束该轮。

至此，该题目圆满结束。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;++i)
using namespace std;
const int INF=2e9,NN=30+3,KK=1e6+3;
const string TR="TURN",DB="DOUBLE",PS="PASS";
int n,m,k,o=1,d,p,h=100,kk=0; string N[NN],K[KK],c; bool f;
unordered_map <string,pair<double,double>> M; unordered_map<string,int> H[NN];
enum{ADD=0,MIN,MUL,DIV,SET};
bool del(string c){
	if(!H[o][c]) return 0;
	cout<<N[o]<<" used "<<c<<",now p="<<p<<".\n",--H[o][c],H[o][K[++kk]]++;
	return 1;
}
#define f(x) if(v?W[x]>w:W[x]<w)w=W[x],r=x;
bool useA(bool v){
	int W[5],r,t,y,w=v?-INF:INF; string F[5],s; fill(W,W+5,w); bool e=1;
	for(auto x:H[o]) if((s=x.first)!=TR&&s!=DB&&s!=PS&&x.second){
		t=s[0]-'A',y=floor(M[s].first*p+1e-9+M[s].second);
		if(y<h&&(v?y>W[t]:y<W[t])) W[t]=y,F[t]=s,e=0;
	}
	if(v){
		if(W[MUL]>w) w=W[MUL],r=MUL; if(W[ADD]>w) w=W[ADD],r=ADD;
		if(W[MIN]>w) w=W[MIN],r=MIN; if(W[DIV]>w) w=W[DIV],r=DIV;
		if(W[SET]>w) w=W[SET],r=SET;
	}
	else{
		if(W[DIV]<w) w=W[DIV],r=DIV; if(W[MIN]<w) w=W[MIN],r=MIN;
		if(W[ADD]<w) w=W[ADD],r=ADD; if(W[MUL]<w) w=W[MUL],r=MUL;
		if(W[SET]<w) w=W[SET],r=SET;
	}
	if(e) return 0; p=w,del(F[r]),f=0; return 1;
}
bool useB(){
	if(del(PS)) return 1; if(del(TR)) {d=-d; return 1;} if(del(DB)) {f=1;return 1;}
	return 0;
}
#define g(a,b,c) M[a]=make_pair(b,c)
int main(){ 
	g("A1" ,1, 1);g("A2" , 1, 2);g("A5",1, 5);g("A9" ,1, 9);g("A19",1, 19);
	g("A49",1,49);g("A99", 1,99);g("B1",1,-1);g("B9" ,1,-9);g("B19",1,-19);
	g("C2" ,2, 0);g("D2" ,.5, 0);g("E0",0, 0);g("E49",0,49);g("E99",0, 99);
	cin>>n>>m>>k;
	up(1,n,i){cin>>N[i]; up(1,3,j) cin>>c,++H[i][c]; }
	up(1,k,i) cin>>K[i];
	up(1,m,i){
		cout<<"Round "<<i<<":\n",d=1,p=f=0; while(1){
			if(!f) goto L1;if(useB()) goto L2; if(!useA(0)) break;
			L1: if(!useA(1)&&!useB()) break;
			L2: o+=d; if(o==n+1) o=1; if(!o) o=n;
		}
		cout<<N[o]<<" lost the game.\n";
		H[o].clear(); up(0,2,j) H[o][K[++kk]]++;
	}
	return 0;
}
//好孩子不要抄袭哦