OceanEye's Blog

很多人即使只见过一面,已经算见过了最后一面。

@OceanEye7年前

04/13
21:39
OI

BZOJ4816 莫比乌斯反演

nlogn狄利克雷卷积打表

和普通的差不多,就是和换成积,贡献算一算就可以了

然后死活想不起来  写 O(n根号n) 的TLE到死

安利 金策大爷 的教程

贴完代码跑路qwq

 

BZOJ4816 莫比乌斯反演

@OceanEye7年前

04/12
23:33
OI

BZOJ4299 CodeChef FRBSUM

很强的题目= =超级烦

想来想去想不懂怎么写

一个很朴素的想法就是排序然后一个一个加进去

假设当前已经满足可以取[0,P]之间的取值

新进来一个数q

如果q在[0,P+1]之间的话就可以拓展 P -> P+q

否则停止拓展,因为显然后面那一堆都不满足要求

然后我就不会了= =跑去翻了翻题解  [传送门]

发现可以连着处理一段的sum,时间复杂度大致是单次log方的。

真神奇

 

BZOJ4299 CodeChef FRBSUM

@OceanEye7年前

04/11
23:03
OI

BZOJ2820

莫比乌斯反演

普通的莫比乌斯反演就是搞出一个分式然后利用[n/i]的连续性制造根号复杂度的东西啊= =

这里的推导也是一样的

先找到simple的f(x) & g(x)

f(x)=sigma(i)sigma(j) gcd(i,j)==x

g(x)=sigma(i)sigma(j) x|gcd(i,j)

上面这个东西随便反演吧= =然后把所有的质数尝试带进x里面

sigma(prime -> p) f(x) == sigma(prime -> p) sigma(dx<=p) g(dx) * μ(d)

把dx换成C,会发现一个C对应着几个 μ(d),这里是一个质因子对应一个 μ(d)。

这里把上面那行东西的值想成一个奇奇gaygay的数论函数h(C)就可以了。

【最神奇的是这个函数居然可以线性求= =太神了不仔细看都看不出来】

这里就可以对于1-N中的每个数来计算贡献了= =

即是 sigma(C = 1 to N) [N/C]*[M/C] * h(C)

然后套一套根号前缀和就可以了。

 

BZOJ2820

@OceanEye7年前

04/10
21:14
OI

BZOJ2705

目测这题很水,那么多人都A了= =

确实也是比较水的。只要有些数论函数的基础就可以做了

gcd(i,N)==k的个数是phi(N/i),所以每一个因数对sum的贡献就是i*phi(N/i)

就酱。

 

BZOJ2705

@OceanEye7年前

04/8
18:51
OI

POJ 2777 线段树+bitset

妈呀这题真卡时。
不得不承认这是我第二道用递归线段树AC的题目qwq太感动了
这题差不多是线段树的裸题了,,只需要bitset维护每一条线段上的颜色还有记得维护PushDown标记就好了。
其他都是细节问题,但是不知道为什么我加了读入优化之后就爆炸WA,,
所以只贴一份AC的无读入优化的代码好了qwq

 

POJ 2777 线段树+bitset

@OceanEye7年前

04/8
18:43
OI

51nod 1681 主席树

这题主席树的处理还是有点神的,,
maya我直接抄题解就好了,,反正我方法的和题解是一样的。
但是我比好多人都慢啊QAQ不服气

首先转化问题。两棵树的公共祖先,很扯淡。计算出每两个点的两棵树上的公共祖先我用的复杂度是n^2·logn
妈呀根本不能接受,妥妥的TLE
那么我们计算祖先的贡献怎么样?
首先假设某个点有x个公共儿子,那么他对总的亲密度的贡献是x*(x-1)/2【自己脑补组合数】
但是看一眼数据范围,首先O(n)应该是不可能的了。那么我们能不能在nlogn的时间内瞎搞出所有节点的公共儿子呢qwq
平衡树?搞毛,,线段树?搞毛,,树剖?不好意思不会,,主席树?于是又神奇的想到了转化问题

他的标号是混乱的,这很不清真,,换成DFS序怎么样?
第二棵树呢?还是混乱的,,

混乱又怎么样,,再标一次就好了。这个时候我们要的就是完成两个集合求交集的工作。
那么主席树出场了!

第一棵树的节点先按照dfs序重新编号,记节点A的子节点为l到r
然后第二棵树也这么做,,记节点A的子节点为L到R
这个时候,会惊奇发现他们的公共儿子【交集】不就是求[L,R]中有多少个元素属于[l,r]的么,,
由于这个东西目测满足区间加法,所以主席树应该是可行的。
那么就主席树瞎搞一下,,A掉。
爽!

51nod 1681 主席树

@OceanEye7年前

04/8
18:42
OI

Tyvj4538 矩阵快速幂裸题

伤心事.裸题居然还交了6次才A。

感觉如果不压行的话我的代码应该还是很容易懂的吧……

Tyvj4538 矩阵快速幂裸题

@OceanEye7年前

04/8
00:03
OI

BZOJ1834

嘛……几万年没好好写过网络流了……
gap优化真的强,把我的1s的代码降成了0.05s
相信前面榜上的就是gap的吧……

BZOJ1834

@OceanEye7年前

04/7
23:56
OI

SPFA的几个优化

SPFA自问世以来,就一直活跃在奥赛各界。因为其极其优化的复杂度和很短的编写代码,各大OI主流媒体都称其为最短路利器。但是,有人闲来无聊之时,在举办模拟赛的时候,会用大量的功夫用于卡掉普通的SPFA(个人觉得比较蛋疼,按理来说是不应该阻碍新技术的推广)。使用我收集了几个比较常见的优化,可以优化SPFA,更重要的是,这个就如随机化快排一般,使SPFA不太会受数据的限制。

1.循环队列

循环队列是因为SPFA的另一个优化,对于队列中已经存在的点,在SPFA的拓展过程中,这个点是不能重复加入的。这样的话,最坏的情况是所有的点都在队列中,队列长度最多与N同级别。这时,可以用循环队列保证队列的长度于N同级别。实现方法就是在head,tail的更新过程中,如果发现大于队列最大允许长度,那么就将其变为1。因为head,tail每次最多加1,所以这样做就可以了。需要注意的是,SPFA的结束条件要变为Head=Tail,有些同学喜欢写Head>=Tail,如果写循环队列的话,这样写是有可能出错的。

2.SLF即Small Label First策略。

实现的方法很简单,即当你要向队列中添加节点的时候,先将其与队首元素比较,如果其比队首元素要优(当前已知的最短距离更小一些),那么将其放在队首的位置,否则放到队尾。这样保证较小距离的节点优先得到拓展。可以使SPFA更快的结束。

3.LLL即Large Label Last 策略。

表示不会,请移步这里

4.还有一个不知名的优化(没有验证过)

若当前元素没有目标节点优,则不更新。

以上。


转自:http://www.blogbus.com/oibltx-logs/125657995.html

 

SPFA的几个优化