推一下蒟蒻 $\color{salmon}{blog}$ 。

原题链接qaq

_写在最前：本文的代码和官方题解没什么区别，只是加一点个人的解释，权且做一个注脚_

为数不多的炉石背景题。

难不见得难，就是装腔作势，借以吓人罢了。

广义上看，从题面、赛时过题人数、代码谢特的程度来说，这确实是一道大模拟。

而精确地讲，这是一道伪装成大模拟的大暴搜，思想可能和【NOIP2015 斗地主】类似。

即：『用搜索来决策当前这一步应该干什么，会带来什么后果。』

定义一个 $dfs$ 函数，返回型 $double$ ，表示在 这个局面下操作者的胜率 。

显然这个可以 记忆化 。

先列好我们能在一局中干什么。

  • 用随从攻击
  • 开技能（嘬一口）
  • 打牌（开biubiubiu）
  • 结束回合。

这些操作有优先级的限制吗？

显然是没有的，我们可以在任何时候嘬一口，也可以在任何时候结束回合。

先看随从攻击这一环节。

一个随从存在两个攻击状态，可以攻击（能动）和不可攻击（不能动）。

同时，他还有两种血量的状态（如果他没有GG的话），一血和两血。

这使我们想到，要保存当前一个玩家的随从场面，需要开四个参数，将血量状态（1/2）和攻击状态（1/0）一一配对，参数的值表示 处于该状态的随从个数 ，定为 $x_{11},x_{10},x_{21},x_{20}$ 。

对于当时对面的场面，我们不关心他们是否能动，就开 $y_1,y_2$ 分别代表 某血量对应的个数 即可。

因为 看了题解 要尽量减小 $dfs$ 函数的谢特程度，我们在 函数传参 时，把一血怪的两种参数压进一个两位数里，十位上是 能动 的一血怪数，个位上是 不能动 的一血怪数，等到函数内部要用值的时候再用 $\%10$ 或 $\div10$ 取出来。二血怪同理。（这里笔者换结构体写了一下，发现怎么调也调不出，最后还是向压缩屈服了）

传参：

1
2
3
4
5
double dfs(int HPx, int HPy, int MINx1, int MINx2, int MINy, int cnt, int cardx, int cardy, int biu)
    //HPx 我方血量，HPy敌方血量
    //MINx1压缩后的我方一血怪情况，MINx2二血，MINy对方情况（十位二血怪数，个位一血怪数）
    //cnt我方剩余嘬+biubiubiu次数，cardx我方牌数，cardy对方牌数
    //这个 biu 比较特殊，他指的是当前是biubiubiu的第几发之后，一会再讲

处理参数：

1
2
3
4
/*MINx1,MINx2,MINy 都是从函数传进来经过压缩的参数*/
int x11 = MINx1 / 10, x10 = MINx1 % 10, x21 = MINx2 / 10, x20 = MINx2 % 10;
int y1 = MINy % 10, y2 = MINy / 10;
int tot = x11 + x10 + x21 + x20 + y1 + y2 + 2;//biubiubiu的总目标数，现在还没用

一个 $k$ 点血且能动的怪要么去交换场面，与对面的随从同归于尽，即 $x_{k1}—,y_?—$；要么直接打脸，攻击对方减 $3$ 点血，即 $x_{k1}—,x_{k0}++,HP_y-=3$ 。

随从攻击：

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
double prob;//该场面我方胜率
......
if (x11)
{
	if (y2)
	{
		prob = max(prob, dfs(HPx, HPy, MINx1 - 10, MINx2, MINy - 10, cnt, cardx, cardy, 0));//我方失去一个能动一血怪，对方失去一个二血怪
	}
	if (y1)
	{
		prob = max(prob, dfs(HPx, HPy, MINx1 - 10, MINx2, MINy - 1, cnt, cardx, cardy, 0));//我方失去一个能动一血怪，对方失去一个一血怪
	}
	prob = max(prob, dfs(HPx, HPy - 3, MINx1 - 9, MINx2, MINy, cnt, cardx, cardy, 0));//打脸，我方一个能动一血怪变成了不能动一血怪，对方HP-3
}
if (x21)//大致同上
{
	if (y2)
	{
		prob = max(prob, dfs(HPx, HPy, MINx1, MINx2 - 10, MINy - 10, cnt, cardx, cardy, 0));
	}
	if (y1)
	{
		prob = max(prob, dfs(HPx, HPy, MINx1, MINx2 - 10, MINy - 1, cnt, cardx, cardy, 0));
	}
	prob = max(prob, dfs(HPx, HPy - 3, MINx1, MINx2 - 9, MINy, cnt, cardx, cardy, 0));
}

其次是开技能。

嘬一口需要满足三个条件：有技能次数，自己血量高于两血，手牌小于 $3$ 张（一血不慌，二血健康，三血抽口也不伤）。

我们开个 $if$ 判一下就是了。

嘬一口：

1
2
3
4
5
6
/*上接随从攻击*/
......
if (cnt && HPx > 2 && cardx != 3)//有技能次数，自己血量高于两血，手牌小于 3 张
{
	prob = max(prob, dfs(HPx - 2, HPy, MINx1, MINx2, MINy, cnt - 1, cardx + 1, cardy, 0));
}

终于来到了本题最复杂最宏伟的结构——biubiubiu 了。

一个 biubiubiu 分为三次伤害，两次伤害之间 有结算 。换句话说，不会有伤害落在死人身上。

这启示我们把一个 biubiubiu 拆成三个连续的 单点伤害 来看，只不过在三个伤害之间 玩家不能操作 罢了。

我们令参数 $biu$ 代表当前场面是在第几次 biubiubiu 之后的场面，若为 $1/2$ ，则说明这是一个在 biubiubiu 期间的局面，既然在 biubiubiu 期间，那我们唯一能做的就是枚举下一发落到哪，对所有情况取个平均数以体现伪随机即可。

枚举 biubiubiu：

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
double dv = 1.0 / tot;//求平均数用的分母，tot是总目标数，赋值在“参数处理”部分
if (biu && biu < 3)//若在 biubiubiu 期间
       //这个判断在随从攻击和开技能之前
{
	if (biu == 2)//如果这是最后一发
	{
		cardx--;
		MINx2++;//则放置一个二血随从，手牌-1
	}
	biu = (biu + 1) % 3;//多一发，如果当前是2，会变成0
       /*开始枚举伤害位置*/
	prob += dv * dfs(HPx - 1, HPy, MINx1, MINx2, MINy, cnt, cardx, cardy, biu);
	prob += dv * dfs(HPx, HPy - 1, MINx1, MINx2, MINy, cnt, cardx, cardy, biu);//打到人身上
	if (x11)
	{
		prob += x11 * dv * dfs(HPx, HPy, MINx1 - 10, MINx2, MINy, cnt, cardx, cardy, biu);//打到己方能动一血怪身上，己方少一个能动一血怪
	}
	if (x10)
	{
		prob += x10 * dv * dfs(HPx, HPy, MINx1 - 1, MINx2, MINy, cnt, cardx, cardy, biu);//以下同上，读者自行理解
	}
	if (x21)
	{
		prob += x21 * dv * dfs(HPx, HPy, MINx1 + 10, MINx2 - 10, MINy, cnt, cardx, cardy, biu);
	}
	if (x20)
	{
		prob += x20 * dv * dfs(HPx, HPy, MINx1 + 1, MINx2 - 1, MINy, cnt, cardx, cardy, biu);
	}
	if (y1)
	{
		prob += y1 * dv * dfs(HPx, HPy, MINx1, MINx2, MINy - 1, cnt, cardx, cardy, biu);
	}
	if (y2)
	{
		prob += y2 * dv * dfs(HPx, HPy, MINx1, MINx2, MINy - 9, cnt, cardx, cardy, biu);
	}
	return store_in = prob;//&store_in 是我们存储记忆化结果的位置，您也可以用其它的方式进行记忆化
}

而在非 biubiubiu 期间，我们要开一次 biubiubiu 的条件又是什么呢？手上有牌，剩余出牌次数>0，我方场上随从<=3 。

开一次 biubiubiu ：

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
/*上接使用技能*/
......
if (cardx && cnt && x11 + x10 + x21 + x20 <= 3)//手上有牌，剩余出牌次数>0，我方场上随从数<=3 
{
	cnt--;//少一次次数
	double tmp = 0.0;//临时储存开 biubiubiu 带来的胜率，因为如果胜率不好我们可以干脆不开
   	/*枚举第一发伤害位置，各语句意义与上一个代码块相同，在此不表*/
	tmp += dv * dfs(HPx - 1, HPy, MINx1, MINx2, MINy, cnt, cardx, cardy, 1);
	tmp += dv * dfs(HPx, HPy - 1, MINx1, MINx2, MINy, cnt, cardx, cardy, 1);
	if (x11)
	{
		tmp += x11 * dv * dfs(HPx, HPy, MINx1 - 10, MINx2, MINy, cnt, cardx, cardy, 1);
	}
	if (x10)
	{
		tmp += x10 * dv * dfs(HPx, HPy, MINx1 - 1, MINx2, MINy, cnt, cardx, cardy, 1);
	}
	if (x21)
	{
		tmp += x21 * dv * dfs(HPx, HPy, MINx1 + 10, MINx2 - 10, MINy, cnt, cardx, cardy, 1);
	}
	if (x20)
	{
		tmp += x20 * dv * dfs(HPx, HPy, MINx1 + 1, MINx2 - 1, MINy, cnt, cardx, cardy, 1);
	}
	if (y1)
	{
		tmp += y1 * dv * dfs(HPx, HPy, MINx1, MINx2, MINy - 1, cnt, cardx, cardy, 1);
	}
	if (y2)
	{
		tmp += y2 * dv * dfs(HPx, HPy, MINx1, MINx2, MINy - 9, cnt, cardx, cardy, 1);
	}
	prob = max(prob, tmp);//取max
	cnt++;//恢复次数
}

最后就是我们的结束回合操作了。

结束这个回合，我们会得到【1.0-对手下回合胜率】的胜率。

我们如何表示下一个回合中对手的胜率？是不是 以对手为主视角 ，做一次 $dfs$ ，参数如下：

1
2
dfs(HPy, HPx, y1 * 10, y2 * 10, (x21 + x20) * 10 + (x11 + x10), O, min(cardy + 1, 3), cardx, 3)
   //y1*10，即所有一血怪都被重置为能动状态，y2同理

我们发现这里的 $biu$ 参数居然是 $3$ ，这又代表什么。

其实是高明的THU爷把 $biu$ 同时还当作了一个标记，因为题目里说一个回合不能啥事不干地 空过 ，所以当 $biu=3$ 其实是 还没有执行过操作 的情况。

所以在 $biu=3$ 时，我们将 $prob$ 初始化为 0 ，否则则至少有 【1.0-对手下回合胜率】作为保底。

初始化 prob ：

1
2
3
4
5
6
7
8
9
10
11
12
/*上接“是否在biubiubiu期间”的判断*/
......
if (biu != 3)
{
	prob = 1.0 - dfs(HPy, HPx, y1 * 10, y2 * 10, (x21 + x20) * 10 + (x11 + x10), O, min(cardy + 1, 3), cardx, 3);
}
else
{
	prob = 0.0;
}
......
/*下接随从攻击*/

这样我们就有了获取某场面胜率的基本方式，现在我们可以整合起来看看。

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
double dfs(int HPx, int HPy, int MINx1, int MINx2, int MINy, int cnt, int cardx, int cardy, int biu)
{
	if (HPy <= 0)//若死了人则直接返回
	{
		return 1.0;
	}
	if (HPx <= 0)
	{
		return 0.0;
	}
	double &store_in = dp[HPx - 1][HPy - 1][id_x[MINx2 * 100 + MINx1]][id_y[MINy]][cnt][cardx][cardy][biu];//id_x和id_y都表示：某一种随从场面对应的编号，这个编号当然是自己定的，主要是为了防炸空间
	if (store_in == store_in)//现学的高明记忆化
	{
		return store_in;
	}
	double prob = 0.0;
    
    /*参数处理*/
	int x11 = MINx1 / 10, x10 = MINx1 % 10, x21 = MINx2 / 10, x20 = MINx2 % 10, y1 = MINy % 10, y2 = MINy / 10;
	int tot = x11 + x10 + x21 + x20 + y1 + y2 + 2;
	double dv = 1.0 / tot;
    
    /*biubiubiu期间的判断*/
	if (biu && biu != 3)
	{
		if (biu == 2)
		{
			cardx--;
			MINx2++;
		}
		biu = (biu + 1) % 3;
		prob += dv * dfs(HPx - 1, HPy, MINx1, MINx2, MINy, cnt, cardx, cardy, biu);
		prob += dv * dfs(HPx, HPy - 1, MINx1, MINx2, MINy, cnt, cardx, cardy, biu);
		if (x11)
		{
			prob += x11 * dv * dfs(HPx, HPy, MINx1 - 10, MINx2, MINy, cnt, cardx, cardy, biu);
		}
		if (x10)
		{
			prob += x10 * dv * dfs(HPx, HPy, MINx1 - 1, MINx2, MINy, cnt, cardx, cardy, biu);
		}
		if (x21)
		{
			prob += x21 * dv * dfs(HPx, HPy, MINx1 + 10, MINx2 - 10, MINy, cnt, cardx, cardy, biu);
		}
		if (x20)
		{
			prob += x20 * dv * dfs(HPx, HPy, MINx1 + 1, MINx2 - 1, MINy, cnt, cardx, cardy, biu);
		}
		if (y1)
		{
			prob += y1 * dv * dfs(HPx, HPy, MINx1, MINx2, MINy - 1, cnt, cardx, cardy, biu);
		}
		if (y2)
		{
			prob += y2 * dv * dfs(HPx, HPy, MINx1, MINx2, MINy - 9, cnt, cardx, cardy, biu);
		}
		return store_in = prob;
	}

    /*初始化prob*/
	if (biu != 3)
	{
		prob = 1.0 - dfs(HPy, HPx, y1 * 10, y2 * 10, (x21 + x20) * 10 + (x11 + x10), O, min(cardy + 1, 3), cardx, 3);
	}
	else
	{
		prob = 0.0;
	}
    
    /*随从攻击*/
	if (x11)
	{
		if (y2)
		{
			prob = max(prob, dfs(HPx, HPy, MINx1 - 10, MINx2, MINy - 10, cnt, cardx, cardy, 0));
		}
		if (y1)
		{
			prob = max(prob, dfs(HPx, HPy, MINx1 - 10, MINx2, MINy - 1, cnt, cardx, cardy, 0));
		}
		prob = max(prob, dfs(HPx, HPy - 3, MINx1 - 9, MINx2, MINy, cnt, cardx, cardy, 0));
	}
	if (x21)
	{
		if (y2)
		{
			prob = max(prob, dfs(HPx, HPy, MINx1, MINx2 - 10, MINy - 10, cnt, cardx, cardy, 0));
		}
		if (y1)
		{
			prob = max(prob, dfs(HPx, HPy, MINx1, MINx2 - 10, MINy - 1, cnt, cardx, cardy, 0));
		}
		prob = max(prob, dfs(HPx, HPy - 3, MINx1, MINx2 - 9, MINy, cnt, cardx, cardy, 0));
	}
    
    /*嘬一口*/
	if (cnt && HPx > 2 && cardx != 3)
	{
		prob = max(prob, dfs(HPx - 2, HPy, MINx1, MINx2, MINy, cnt - 1, cardx + 1, cardy, 0));
	}
    
    /*开biubiubiu*/
	if (cardx && cnt && x11 + x10 + x21 + x20 <= 3)
	{
		cnt--;
		double tmp = 0.0;
		tmp += dv * dfs(HPx - 1, HPy, MINx1, MINx2, MINy, cnt, cardx, cardy, 1);
		tmp += dv * dfs(HPx, HPy - 1, MINx1, MINx2, MINy, cnt, cardx, cardy, 1);
		if (x11)
		{
			tmp += x11 * dv * dfs(HPx, HPy, MINx1 - 10, MINx2, MINy, cnt, cardx, cardy, 1);
		}
		if (x10)
		{
			tmp += x10 * dv * dfs(HPx, HPy, MINx1 - 1, MINx2, MINy, cnt, cardx, cardy, 1);
		}
		if (x21)
		{
			tmp += x21 * dv * dfs(HPx, HPy, MINx1 + 10, MINx2 - 10, MINy, cnt, cardx, cardy, 1);
		}
		if (x20)
		{
			tmp += x20 * dv * dfs(HPx, HPy, MINx1 + 1, MINx2 - 1, MINy, cnt, cardx, cardy, 1);
		}
		if (y1)
		{
			tmp += y1 * dv * dfs(HPx, HPy, MINx1, MINx2, MINy - 1, cnt, cardx, cardy, 1);
		}
		if (y2)
		{
			tmp += y2 * dv * dfs(HPx, HPy, MINx1, MINx2, MINy - 9, cnt, cardx, cardy, 1);
		}
		prob = max(prob, tmp);
		cnt++;
	}
	return store_in = prob;
}

然后主函数有手就行（（（

这里再点两个细节：

  • 有一个有效而可行的剪枝是，在不是 biubiubiu 期间，且当前手上随从 全部打脸 就能赢的时候，直接返回 1.0 。（亲测每个点可以平均-3s）
1
2
3
4
if (HPy <= (x11 + x21) * 3)
{
	return store_in = 1.0;
}
  • 记得把 y1 define 掉。/kk

想来想去还是放送一下主函数比较好：

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
#include <bits/stdc++.h>
using namespace std;
#define y1 MKANJD
#define y0 MAIJBXJ
double dp[20][20][70][15][6][4][4][4];
int id_x[4007], id_y[4007];
int situa[47] = {0, 1, 2, 3, 4, 10, 11, 12, 13, 20, 21, 22, 30, 31, 40};//所有可能的随从场面
int O;
double dfs(int HPx, int HPy, int MINx1, int MINx2, int MINy, int cnt, int cardx, int cardy, int biu)
{
	......
}
int read()
{
	int num = 0, bj = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
		{
			bj = -1;
		}
		ch = getchar();
	}
	while (isdigit(ch))
	{
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return bj * num;
}
signed main()
{
    /*预处理id_y*/
	for (int i = 1; i < 15; ++i)
	{
		id_y[situa[i]] = i;
	}
	memset(dp, -1, sizeof(dp));
    
    /*预处理id_x*/
	int tot = 0;
	for (int i = 0; i < 15; i++)
	{
		for (int j = 0; j < 15; j++)
		{
			if (situa[i] / 10 + situa[i] % 10 + situa[j] / 10 + situa[j] % 10 <= 4 && id_x[situa[i] * 100 + situa[j]] == 0)//场上随从数不到4个的都叫合法
			{
				id_x[situa[i] * 100 + situa[j]] = tot++;
			}
		}
	}
    
    
	int T;
	T = read();
	O = read();
	while (T--)
	{
		int HPx = read();
		int HPy = read();
		int minx1 = 0, minx2 = 0, miny = 0;//我方一血怪、二血怪，对方随从
		int M;
		M = read();
		for (int i = 1; i <= M; i++)
		{
			int K;
			K = read();
			if (K == 1)
			{
				miny++;
			}
			if (K == 2)
			{
				miny += 10;
			}
		}
		M = read();
		for (int i = 1; i <= M; i++)
		{
			int K;
			K = read();
			if (K == 1)
			{
				minx1 += 10;
			}
			if (K == 2)
			{
				minx2 += 10;
			}
		}
		int card_y = read();
		int card_x = read();
		printf("%.9lf\n", dfs(HPx, HPy, minx1, minx2, miny, O, min(3, card_x + 1), card_y, 3));
	}
	//老师彩笔！
}

最后更新： 2021年04月18日 20:30

原始链接： https://quest233.github.io/2021/04/17/%E6%88%91%E8%B5%B0%E5%9C%A8%E6%B2%A1%E6%9C%89%E4%BD%A0%E7%9A%84%E5%A4%9C%E9%87%8C%E5%86%B7%EF%BD%9E%E5%86%B0%EF%BD%9E%E5%86%B0%EF%BD%9E/