UOJ Logo kczno1的博客

博客

zjoi2017游记

2017-04-30 07:54:59 By kczno1

第一次参加zjoi,30+30。我果然太弱了。

感觉这应该是很长一段时间里对我最重要的比赛了,还是记录一下吧。

day1

是在我们学校的。

看到第一题觉得可以dp 之后就花了大概3个小时想了现在也不知道对不对的dp

后来虽然过了很小数据的对拍,但忘了测大样例

最后也只有20分

第三题本来想打30分,但fft有点记不清了,后来就打了10分。

第二题我没发现他就是个单点修改,后缀求和。

不知道他在干什么,然后就在最后快没时间的时候想打个10分,结束时还差个逆元没打,所以就0分了。

龙爷t2发现了那个性质,似乎拿了70分。

day2

t1,我想先把n-1块看成一块,假如得到了他移动的代价,

之后就记忆化搜索搜出来他和第n块一起移动的代价。

但我没考虑到移动的过程是先颠倒在最后才达到目标的。

最后拿了10分。

不少人推出了k=2时如何移动,拿了40分。

t2,我就打了20分。先把询问的人在线段树走一遍打上标记,之后把[l,r]走一遍,走的时候顺便得到lca。

龙爷想了个O(nlog^2)的做法,

就是发现如果一个左端点被区间[l,r]覆盖,那么l<=他的l,r>=他的r且r<他爸爸的r。

而求的东西类似带权距离和,是可以用点分树做的。

那么这题就是个矩形修改单点询问。

枚举右端点,线段树套点分树维护左端点。

然而实际上常数较大,很难跑过去,最后也只拿了10分。。。。。

以为稳进队的龙爷就这样挂了。

第三题我随便打了个线段树维护区间最小后缀,比较两个后缀的时候用二分lcp,线段树维护hash来检验的方法。

不知道怎么支持区间加,所以也不知道怎么才能拿随机和10^4的分(现在还是不知道这两个部分分什么意思)

但没修改是nlog^2的,以为30分总有的吧。

然而会t。原因大概是我觉得数值太大,hash有点虚,于是用了3个取模的hash。

如果用后缀数组初始化复杂度就是nlogn+mlog^2,应该就没问题了。但我也没时间打了。

特别厉害的sjj学长也没能进队。

zjoi怎么这么难啊。

评论

TLEbyc
随机 暴力就可以跑 只要常数不太丑
ztr
哇原来day2T2跟我一个做法的不只是我= = 10分有点惨= =我常数优化了一波然而也只有40= =拆了去打满暴力还60呢
laosb
stO

发表评论

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