一些小学就该会的姿势
GoogleCodeJam乱做

清华集训2013 BZOJ3581 扑克牌

Recursion posted @ 2016年3月13日 15:12 in 题解 with tags bzoj 清华集训 计数 , 730 阅读

STL狗的胜利(大雾>_<)!

 

搞了三天终于把这神题A了。当然只是在bz卡过而已,tsinsen上只有80分...

由于网上不大能搜到题解,官方题解又比较意识流,我来写一发骗骗访问量。

题意

题解

注意到同一数字的牌至多只有9张,考虑将牌之间的边分成两种:

1.数字相同颜色不同。

2.颜色相同数字无所谓

我们把一种最后的方案中数字相同的连续一段称为一条链。由于只有9张牌,直接爆搜把这些牌拆成若干条相邻颜色不同的链的方案数,并统计进数组[tex]g[i][j][/tex]。[tex]g[i][j][/tex]表示头尾颜色分别为[tex]i,j[/tex]的链有[tex]g[i][j][/tex]条。注意到[tex]g[/tex]实质上是一个3个点的有向图的邻接矩阵。

显然如果每条链内的方案数考虑过了,用链把三种颜色连起来就行了。

我们来一发dp,[tex]f[i][g][/tex]表示数字不超过[tex]i[/tex],链的状态为[tex]g[/tex]的拆分方案数。转移时爆搜每个当前的数字的拆分就行了,然后用一个背包状的东西合并(这是时间瓶颈,由于窝用的unordered_map,光合并的时间就要占7~8s...)。

这样我们就把经过每个点一次变成了经过每条链一次。所以答案就是对[tex]f[9][g]\times calc(g)[/tex]球和,[tex]calc(g)[/tex]表示图[tex]g[/tex]的欧拉路个数。

计算欧拉路同样可以大暴力+记忆化。爆搜一下可以发现图[tex]g[/tex]的数量在[tex]10^6[/tex]级别(别问窝怎么知道的),直接搞就行了。

还有,记得手写hash。

总结一下,就是从头大暴力到尾→_→。

(感觉窝写的比官方题解还意识流...)

pear 说:
2016年3月15日 15:31

,分块!!!!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter