题解 P5370 【[PKUSC2018]主斗地】

feecle6418 · 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。