UOJ Logo Gromah的博客

博客

NOIP day1 扯淡

2015-11-07 19:01:20 By Gromah

第一题是题?

第二题的话,找最小环应该就可以了吧。这个感觉是比较经典的。

第三题的话:

首先,我们考虑出牌顺序是否会对出牌次数产生影响。显然不会。

既然这样,我们不妨先出顺子,包括单顺,双顺,三顺。具体就是直接暴力枚举每一个顺子,然后出掉,再枚举顺子,再出掉$\dots\dots$这样会不会很耗时间呀?事实是不会的。因为一个顺子至少也有 5 张牌,所以最多出 4 次顺子,递归层数是很小的。然后在一组牌内可以产生 $O(K^2)$ 个顺子,其中 $K$ 表示能成为顺子组成部分的牌的种数,在这里 $K = 12$,然后这里的复杂度就是 $O(K^8)$,然而常数是极小无比的,可以很快地运作。

然后我们就可以不考虑顺子了,那么对于剩下的牌,我们就只能一个一个或者一对一对或者一带一带地出了。总而言之,出牌的次数与牌的点数无关了。那么我们可以预处理一个 $Time[a][b][c][d][e]$,表示手牌有 $a$ 张单牌,$b$ 个对子,$c$ 个三张,$d$ 个炸弹,$e$ 张王时,把牌出完的最小次数。这个东西可以通过动态规划求解。

时间复杂度:$O(n^4 + T\times K^8)$。

尽管我是这么 BB 的,然而考场上各种浪,后边这一部分是各种贪心各种分类讨论。。。还好据说数据随机,被卡的几率应该比较小吧。。。。。。

毕竟 Gromah 果弱嘛,只会这么 BB。

评论

OnlyaDouBi
蒟蒻表示第三题我会被卡到乱七八糟。。
Picks
666!看上去能过。
MedalPluS
LZ AK前留名%%%
HJWJBSR
前排%%%
zhouzixuan
T3直接2^n状压dp不行吗?
zhouzixuan
我的做法是存下每张牌剩余个数,然后hash的话就用二进制,2^n,然后dfs暴力转移,极限数据刚好2s
zzyu5ds
我也想到了这个解法,可惜由于IDE(次要),自己代码能力太差(顺子有连5个的,连6个的,连3对的,连4对的,连3*2的,......),想暴力枚举,心里好乱,于是gg;
Edward
后排%%%

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。