4
27
2015
1

搞点新科技

发现最近写博客好随意啊,想怎么写怎么写

 

求miu函数以及fai函数的前缀和

 

BZOJ3944sum

 我看的是这里的题解:Gromah  Li Zhuohan  

不得不说这种变换实在太科幻了。。。

复杂度估计什么的不会证明。。。用hash应该是O(n^2/3),然后加了个map就成了O(n^11/12)了。。。但是两实测跑起来一样快。。。

爆int调了我3h最后在Gromah的help下才AC了 Orz

BZOJ3930: [CQOI2015]选数

先推莫比乌斯反演,然后发现我们需要知道miu函数的前缀和,而范围是1e9.。。预处理显然就挂掉了。那么我们的O(n^2/3)大法就派上用场啦!

虽然整个复杂度看起来很不靠谱的样子,但是还是1s跑过了

 

斯坦纳树

 

求一张图中使得给定点集连通的最小代价。点集的大小很小,一般都<=10.

然后dp[i][j]表示在i点点集连通状态为j的最小花费,那么有dp方程组:

dp[i][j]=min(dp[i][j],dp[i][k]+dp[i][j-k])其中k是j的一个子集。

dp[i][j]=min(dp[i][j],dp[k][j]+w[k][i])其中k与i相邻,w[k][i]表示k到i的代价。

然后我们枚举j,先用子集更新ans。然后再在整张图上跑spfa来更新每个点的j状态的最优值。

其实我并不了解正确性

最后的最优解一定是一棵树的形态,而它的任何一部分也是一棵树的形态。

我们按论文上的来理解,dp[i][j]表示这棵树的根为i,然后连通的点集为j的最小代价。

考虑两种转移,第二种就是将这个根向上拓展(向下显然不优)

第一种就是合并两颗有根树。什么?你说重复的?我们自然可以把有重复的归到一个点集,然后用不重复的来得到更优的答案。

然后逐渐得到我们的最优解。好像很有道理的样子。。。原谅我是蒟蒻

BZOJ2595: [Wc2008]游览计划 

那么这题就是裸的斯坦纳树了。当然代码很好写。理解的不是太清楚总感觉怪怪的QAQ

 

BZOJ3205: [Apio2013]机器人

这题也是可以斯坦纳树搞的。

我比较二没想到DP方程QAQ

设dp[i][j][l][r]表示处在(i,j)使l-r合并的最小代价。那么有dp方程组

dp[i][j][l][r]=min(dp[i][j][l][r],dp[i][j][l][k]+dp[i][j][k+1][r]) 类似于上面的枚举子集

dp[i][j][l][r]=min(dp[i][j][l][r],dp[i'][j'][l][r]+1)其中(i',j')一步可以走到(i,j)

然后后面这一部分就spfa做。。。

UPD:其实我觉得这个不能叫斯坦纳树233 只是在列出dp方程之后采用了与斯坦纳树一样的处理方式。

然后就TLE了!

PoPoQQQ大爷教导我们


维护两个队列,将初始所有的点按照距离排序后从小到大加入队列1

每次拓展出的点加入队列2
每次取出点的时候,如果队列1队尾元素的距离小于队列2 就把队列1的队尾元素拿去松弛 否则就用队列2的
这样做之后除了排序之外复杂度是线性的
 
于是我RE了,检查了好久记忆化。最后发现被define坑了,数组开小了。
但是我还是T了。拿来数据一测,我和PoPoQQQ都T了5个点。交上去,他A了,我T了。
 
 
自己没亲手AC真是太不爽了
 
 
BZOJ4006: [JLOI2015]管道连接
 
 
这题好神啊。斯坦纳树可以求出使给定点集连通的最小代价。
 
 
那么最后的ans一定是一片斯坦纳生成树森林。
 
我们枚举这片森林的形态,即分成了哪些连通块。
 
显然同一种颜色在同一个连通块里。
 
那么令f[i]表示i集合的所有颜色互相连通的最小代价。那么f[i]可以通过一次斯坦纳树求出。
 
而g[i]表示i集合的颜色中相同颜色的点互相连通的最小代价,那么初始值g[i]=f[i]。
 
然后我们发现不一定需要全部连通,所以考虑将i集合分成两个集合,即g[i]=min(g[i],g[j]+g[i^j]) 其中j是i的子集。
 
重复计算的一定不会出现在最优解中。
 
 
 
 
Category: 涨姿势 | Tags: | Read Count: 691
Avatar_small
Tunix 说:
2015年4月28日 21:13

zyf大爷太神辣~


登录 *


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

| Theme: Aeros 2.0 by TheBuckmaker.com