洛谷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分

比赛

yanQval

期望下不存在块内询问~

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

Alextokc

@yugoslavia

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

Alextokc

@yugoslavie

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

zx2003

@yugoslavie

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

zx2003

@yugoslavie

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

WrongAnswer

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

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

WrongAnswer

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+\cdots+x^{r-l})$，线段树维护最小值及区间和。感觉很靠谱，不知道这个做法能不能卡掉。（另外 @OldDriverTree 题解有一种维护平方和的做法感觉很容易卡掉……？这组数据 8 1 2 2 3 4 5 8 9 9 2 1 8 答案应该是yuanxing）

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

scPointer

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

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

发表评论

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