自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 22:10:05，当前版本为作者最后更新于2019-12-17 08:34:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一道大力出奇迹的题。

首先题目的 $\mathrm{mod}\ 998244353$ 是来吓人的。其实在去掉 $3$ 之后， 九条可怜的牌至多只有几百万种，因此完全可以枚举九条可怜的牌，然后暴力判断是否可行。

如何判断是否可行呢？明确一个事实：顺子是无用的，可以拆成单牌。于是不需搜顺子，首先搜索三个和四个的数量（因为他们可以带牌）；然后枚举有几个三带对，剩下的全部三带一或者四带二（因为如果不带，则可以拆成单牌来打），九条可怜带大牌，网友带小牌，剩下的牌从小到大扫一遍，看是否可行即可。

但是这样写在评测机极慢的本校 oj 上过不去。

因此加入以下优化：

1. 假如说要带的牌已经超过了 $17$ 张，直接返回；
2. 用 memset 和 memcpy 让常数乘上 $\frac{1}{8}$；
3. 本来“剩下的牌从小到大扫一遍，看是否可行即可。”这一部分我是用的两个数组，一个存九条可怜的，一个存网友的，但是这样极慢。我们可以差分，只用一个数组 $c$，假如九条可怜有 $x$ 张 $y$，则 $c_{y+1}\leftarrow c_{y+1}-x$；假如网友有 $z$ 张 $w$，则 $c_{w}\leftarrow c_{w}+z$。最后做一遍前缀和，假如有 $>0$ 的，则说明九条可怜牌太多了，不可行；否则可行。常数又乘上 $\frac{1}{2}$；
4. 假如对子数已经超过了 $\min(j,w)$（$j$ 为九条可怜的对子数，$w$ 为网友对子数），则直接返回。
5. 三张和四张只用搜到 2 就好，不用搜 w 和 W。

加入以下优化后，在本校 oj、洛谷、loj 上均跑到了 Rank 1。（洛谷上显示为 Rank 2，但是其实我的总用时比 Rank 1 少，是总用时计算机制的问题）

代码直接去看 loj Rank 1 就好。提交者叫做 2。