洛谷5月月赛 - 博客 - kczno1的博客

洛谷5月月赛

2017-05-30 21:50:18 By kczno1

打了这么久，好像第一次rank1啊

我打的50分dp

不过好像加常数优化后可以拿60-70分(我拿了60)

f[i]表示gcd(边权)是i的倍数的方案数

如果把f[i]搞出来了，那么就可以nlogn求出答案。

f[i]其实就是矩阵树n^3求啊

不过加一个，如果不连通就直接退出

我也不会算复杂度

一开始想打fwt拿50分，不知道为什么拿了40

后来想到，就枚举i,j和n,m的二进制的最长公共前缀

之后就可以搞了

就是max-min=r-l

且不存在重复的数

把每对相邻重复的数l,r

以r为下标放到线段树里

就可以了

分治

对两边所有不同的gcd,or暴力枚举

似乎是nlog^3的

但跑的挺快。。

一开始把那个o(N)的方法看了一遍

后来发现构建笛卡尔树空间会开不下

分块块间st+前后缀min是可以o(1)的

但询问在块内怎么办呢

答案就是块内直接暴力(因为随机，假设块大小为k，那么复杂度就是k/n n k=k * k)

upd:

t5复杂度是nlog的

t4 fwt中间没有取模爆了long long 加了后拿到50分

比赛
好评差评[+4]

yanQval

好评差评[0]

期望下不存在块内询问~

2017-05-31 07:42:00
回复

评论回复
Lucida：为什么？不应该是概率\frac {1}{\sqrt N}吗 2017-05-31 21:11:48 回复
yanQval：回复 @Lucida：这不就可以忽略了么qwq 2017-06-01 15:01:24 回复
Lucida：回复 @yanQval：\dfrac{1}{4000}在2e7组询问还能忽略。。？？应该是期望O(1)的啊 2017-06-01 20:45:02 回复
yanQval：回复 @Lucida：怎么不能忽略。。。这不就是1/sqrt(N)*Olog? 2017-06-02 07:34:08 回复

Alextokc

好评差评[-2]

@yugoslavia

2017-06-02 18:25:35
回复

Alextokc

好评差评[-2]

@yugoslavie

2017-06-02 18:25:48
回复

zx2003

好评差评[-2]

@yugoslavie

2017-06-02 19:21:54
回复

zx2003

好评差评[-2]

@yugoslavie

2017-06-02 19:22:00
回复

WrongAnswer

好评差评[0]

T6由于数据随机，笛卡尔树是可以过的……还相当好写……

2017-06-02 22:11:10
回复

评论回复
OldDriverTree：似乎被笛卡尔树打败了啊本来还以为这个rmq应该是跑得最快的 2017-06-03 14:21:27 回复
kczno1：请问有没有笛卡尔树方法的代码啊我不知道空间如何开得下。。 2017-06-04 17:55:04 回复
kczno1：好吧我把比赛的代码再交一遍就能看t0vd的代码了请问这样复杂度为什么是O(n)呢 2017-06-04 18:16:18 回复
kczno1：好吧我好像知道了考虑每层被访问的概率 1+1/2+1/4+..=1 2017-06-05 14:22:02 回复

WrongAnswer

好评差评[0]

T4我的做法好像不是一个路子的……我用的是随机化算法…… 把序列每个数

a_{i}

表示为一个项

x^{a_{i}}

，然后随机两组质数

x_{1}, p_{1}

和

x_{2}, p_{2}

，分别在模

p_{1}, p_{2}

意义下把

x_{1}, x_{2}

代入求区间和判断是不是

x^{m} (x^{0} + x^{1} + \dots + x^{r - l})

，线段树维护最小值及区间和。感觉很靠谱，不知道这个做法能不能卡掉。（另外 @OldDriverTree 题解有一种维护平方和的做法感觉很容易卡掉……？这组数据 8 1 2 2 3 4 5 8 9 9 2 1 8 答案应该是yuanxing）

2017-06-04 12:39:22
回复

评论回复
WrongAnswer： $x^{m} (x^{0} + x^{1} + \dots + x^{r - l}$ 的 $m$ 表示区间 $[l, r]$ 最小值。 2017-06-04 12:40:08 回复
kczno1：但是他还维护了和你这个和就不对了吧等待反例或证明。。 2017-06-04 18:04:41 回复
WrongAnswer：回复 @kczno1：把序列改成2 2 5 6 6 7 7 9呢？ 2017-06-04 21:40:58 回复
OldDriverTree：回复 @WrongAnswer：维护区间hash的做法其实很难卡掉，因为我可以维护和，平方和，乘积等等 2017-06-05 08:57:15 回复
WrongAnswer：回复 @OldDriverTree： $x (x + 1) (x + 2) \dots (x + k)$ 有没好的求法？ 2017-06-05 11:56:18 回复

scPointer

好评差评[0]

那个，其实 T1 的 70 分出题人本意不是 dp 的，不过赛时好像大家都卡进去了（

2017-06-05 09:56:19
回复

评论回复
WrongAnswer：出题人为什么不放 $n$ 范围 $10^{18}$ ， $k$ 不大的数据……这样就可以卡暴力DP了…… 2017-06-05 14:16:51 回复
scPointer：回复 @WrongAnswer：应该只是没想到能卡进去辣。 2017-06-06 22:53:52 回复
scPointer：回复 @scPointer：顺便一提这个有 $O ((n + k) \log n)$ 和 $O (k \log n \log k)$ 两种写法， 2017-06-06 22:55:30 回复
scPointer：回复 @scPointer：所以 $n, k$ 都稍微大一点也可以，比如加个零 2017-06-06 22:55:40 回复
scPointer：回复 @scPointer：（uoj 这个字数限制为什么这么卡，这么短一句要分三回发 2017-06-06 22:56:41 回复

发表评论

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