自动搬运

查看原文

来自洛谷，原作者为

	Mr_Li **

搬运于2025-08-24 22:12:54，当前版本为作者最后更新于2021-11-19 14:37:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

没人写题解？那我试着写一篇。

我们把保证无论农民的牌如何，地主一定能春天的地主初始手牌称为春天牌，第六、第七组数据要求输出的答案就是春天牌的数量

这题表面上是个数数题（还故意写对998244353取模），但根据直觉分析，春天牌的数量应该不多（通过写代码计算可以验证数量在 $10^4$ 到 $10^5$ 之间，这里不写出具体数值），我们对于每一组数据，枚举它属于多少种春天牌即可。现在的问题是如何找出所有的春天牌。

春天牌一定属于下列两种情况之一（或者下列两种情况都满足）：

1. 包含大小王两张牌至少一张，并且包含除大小王之外的每种数码的牌至少一张；

2. 去掉若干组炸弹和火箭后，剩下的牌可以一次打出。

上面这句话的正确性非常显然，如果不满足第二种情况，意味着地主需要打出至少两次非炸弹火箭牌，所以第一次打出非炸弹火箭牌时，由于地主手里还有牌，所以打出的牌可能被农民炸掉，所以农民不能存在炸弹和火箭，即需要满足第一种情况。

下面分两种情况考虑：

第一种情况

先枚举第一种春天牌中的王牌是只有一张小王，只有一张大王，还是大小王都有。

由于第一种春天牌除大小王之外每种数码的牌至少一张，所以到目前为止我们已经有14张或15张牌已经确定，我们可以用DFS确定剩下的5张或6张牌，确定之后再套一个DFS判断确定的牌是否属于第一种春天牌。

我们需要判断我们第一层DFS搜索出来的20张牌是否属于第一种春天牌，可以看出，这一种情况能保证农民必然没有炸弹和火箭，所以我们可以枚举地主可以打出的手牌，判断这一手牌有没有可能被农民接的上，如果不可能，把这一手牌打出，并递归搜索剩下的可以打出的手牌。

按照我的枚举手牌的顺序，我先枚举顺子，先枚举顺子的开头数码，然后从小到大枚举顺子的结尾数码，如果地主存在数码为枚举的结尾数码的牌至少一张，说明枚举的结尾数码可以继续增大，但是注意只有结尾数码和开头数码的差值大于4时这手牌才能打出，而且结尾数码不能超过A，判断这一手牌有没有可能被农民接的上时，按类似的方法枚举顺子即可。

同理枚举连对，先枚举连对的开头数码，然后从小到大枚举连对的结尾数码，如果地主存在数码为枚举的结尾数码的牌至少两张，说明枚举的结尾数码可以继续增大，但是注意只有结尾数码和开头数码的差值大于2时这手牌才能打出，而且结尾数码不能超过A，判断这一手牌有没有可能被农民接的上时，按类似的方法枚举连对即可。

我们把三张牌视为只含一组三张牌的三顺，并相应地把三带一和三带二视为飞机，那么我们可以类似地枚举三顺和飞机，先枚举三顺或飞机的三顺部分的开头数码，然后从小到大枚举三顺或飞机的三顺部分的结尾数码，如果地主存在数码为枚举的结尾数码的牌至少三张，说明枚举的结尾数码可以继续增大，如果枚举的是飞机，则还要再套一层DFS枚举飞机的单牌部分或对子部分，注意到结尾数码和开头数码的差值没有要求，但是结尾数码在不等于开头数码时不能超过A，由于农民牌的总数量很多，所以在判断农民是否存在比枚举的飞机要大的飞机，只要枚举农民是否存在比枚举的飞机三顺部分要大的三顺。（顺带一提，NOIP2015提高组的斗地主是没有飞机的）

接着枚举炸弹和四带二，先枚举四张相同的牌，如果要枚举四带二，则再枚举剩下两张牌，注意到当地主打出炸弹和四带二的时候，农民一定要不起。

最后只剩下单牌和对子、火箭没有枚举，枚举单牌和对子，在判断农民时候能接的上即可，不需要额外枚举火箭，因为当你拥有组成火箭的大王和小王时，你可以把它们分开走，农民一定要不起。

第一种情况的统计是最花时间的，我的代码在O2条件下要跑2.78s,但足以通过此题。

第二种情况

先枚举一次打出的手牌。（枚举的方法与第一种情况有点像）

按照我的枚举一次打出的手牌的顺序，先枚举对子，不必枚举单牌和火箭，因为炸弹有4张，它和火箭都是偶数张，一次打出的手牌肯定不是单牌和火箭。

然后同样把三张牌视为三顺，枚举三顺和飞机，枚举三顺或飞机的三顺部分的开头数码和结尾数码，如果枚举的是飞机，再用DFS枚举飞机的单牌部分或对子部分，注意结尾数码在不等于开头数码时不能超过A。

接着枚举顺子和连对，枚举开头数码和结尾数码即可，但注意枚举顺子时结尾数码和开头数码的差值必须大于4，枚举连对时结尾数码和开头数码的差值必须大于2。

最后枚举炸弹和四带二，先枚举四张相同的牌，如果要枚举四带二，则再枚举剩下两张牌。

枚举完一次打出的手牌之后，就是向其中添加炸弹和火箭，将一次打出的手牌变为第二种春天牌。

一开始现在的手牌是一次打出的手牌，如果现在的手牌中没有王，则将现在的手牌加上两个王，接着从2开始，按照数码从大到小的顺序判断现在的手牌中是否存在相应数码，否则加上四个数码为相应数码的牌，直到现在的手牌有20张为止，那么现在的手牌就是第二种春天牌。

很明显这种方法是对的，因为否则最后产生的包含20张的现在的手牌必须先走完所有的炸弹再走一次打出的手牌，并且打出炸弹有可能被农民打出的炸弹或火箭接的上。

第二种情况的计数几乎不花时间，我的代码在O2条件下只要5ms。

注意到得到的第二种春天牌会有重复，也会有一些属于第一种春天牌，把两种春天牌去重即可。

计算每个数据属于多少种春天牌也要花大量时间，但不会太长，对于第10个点我的代码在O2条件下大约需要1.44s。

呃……好像写太多了……差不多就写这些吧。代码太丑这次就不附了。