OceanEye's Blog

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

@OceanEye7年前

04/27
09:59
OI

BZOJ4810 莫队+bitset

题目 链接 :http://www.lydsy.com/JudgeOnline/problem.php?id=4810

kry大爷的代码好短……可以看看orz

[bzoj 4810] [Ynoi2017]由乃的玉米田

这题目测只要是根号+压位就能过得去的了……所以不要太在意细节
[然后就被细节骗走了五次wa]
如果我们压了位……
减法就可以直接右移解决 b-c=a
加法的话把它反过来右移解决 大概是变成 a+b=c -> b-c=-a

乘法很simple,直接暴力就好了,根号可是比n/64要小的
而且时限30s,跑起来好像还挺稳的?
代码:

BZOJ4810 莫队+bitset

@OceanEye7年前

04/25
11:23
OI

BZOJ1179

(点我)题目链接

老题。
强连通分量把能一起抢的缩成一个点
然后在图上跑SPFA或者DP都可以
写SPFA写惯了……

BZOJ1179

@OceanEye7年前

04/23
15:45
OI

BZOJ1455

还是可并堆的题目……而且一如既往的很裸
合并,弹出都是log的复杂度
看代码吧……没什么细节但是我还是没有1A

BZOJ1455

@OceanEye7年前

04/21
16:09
OI

BZOJ3262

CDQ分治做三维偏序
很裸很裸
直接看代码吧= =

[CDQ分治的思想就是一段询问有三个维度,离散化两个维度,对第三个维度我们扫一遍来计算贡献]
[通常取mid是比较优秀的]

BZOJ3262

@OceanEye7年前

04/21
13:30
OI

BZOJ3270

这是一份简单的题解
用一个二元组表示两个人的状态 (A,B)
然后在二元组里面跑概率方程
稍微参照了一下黄学长的方程列法
不过还是觉得在 起点(A,B) 那里可以更漂亮的。
都一样啦过了

BZOJ3270

@OceanEye7年前

04/17
08:26
OI

BZOJ2809可并堆裸题

题面大概是这样子的:

很裸,就学了一下可并堆的姿势然后就写了
1A啊:-D
写的是左偏树,安利百度文库的文章
但是不知道为什么跑了3k+ms
不理了可能是vector的原因吧

BZOJ2809可并堆裸题

@OceanEye7年前

04/14
17:38
OI

BZOJ1858: [Scoi2010]序列操作

题目链接

好久没写过这么长的代码了= =

像狗一样看了一个上午终于在下午的时候狠下心来写对拍

对拍大法好qwq

一份暴力一份正解

以后有空再写线段树

暴力

正解

 

BZOJ1858: [Scoi2010]序列操作

@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