cojR9 & X Round 3

Source

好题:D、E

和xgc合作愉快,靠D拿到rk10,过的时候还剩15min,当场就所有人激动得大吼出来……

主要是comet的王太多了……终于拿到短裙给lxgay穿了嘻嘻(可惜不能给tyb穿了)

D 系统设计

请先思考后再展开

题解做法(log):

考虑处理好从根到当前节点的hash值Sx,每次询问就在数据结构(如线段树)上二分,然后把Sx与now合并,放到S的hash表里面询问就好了

我的做法(log方):

考虑跳的过程考虑怎么加速,如果能快速做重链,那么只会有log次重链,而重链是可以剖的,得到连续的dfs序,然后你注意到树是静态的,而序列会修改,考虑即树上节点的aa为这个节点重儿子的编号排名,于是就是一个匹配的问题,考虑怎么快速匹配,无脑二分+线段树是log方的,加上外面的重链就是log3方的,考虑怎么在线段树上二分

首先线段树上区间hash维护好,记real为dfs序上当前从哪里开始与起点st匹配且长度限制为mxlen
如果设计函数gethash(l,r)来获得st->mid上的hash判,这样依然是log3方的2333

如果把gethash去掉,就更gg了,因为它不是普通的区间修改,你啥也不判的话一次就是nlogn的;但我们可以考虑怎样让它的复杂度和区间修改一样,如果st是当前线段树区间的左端点,用区间hash判断掉完全匹配的情况;于是如果没断开,他就是区间修改的立刻返回,而断开了则调用它的那些母函数就不会往右走了,所以复杂度是对的。

总之这道题其实70%的idea都是xgc想的,我就是一只猿
其实细节不算特别多,也不算真的很难写,但我再次一个sb错误调一年……

code

E Namid[A]me

请先思考后再展开

首先怎么快速计算 $x^x(\%p)$ ,其实连题面都提示了原根是10了且模数很小,预处理指数后费马小定理即可

因为是按位与,对于某个端点,肯定是只有位数(w)段不同的取值,显然就是存每个状态的数量

然后我就自闭了……只能想到log方的做法

瞎选一个点作为根,dfs递归处理,维护w段取值,向上保留的话很好维护;考虑合并链的情况,暴力合并的话要做$d^2$次,每次是$w^2$,但你需要敏锐地意识到一个上界: $min(d^2w^2,n^2) \geq \sqrt {(dwn)^2}=dwn$,然后每次扫完一个子树合并状态要 $O(nwlogw)$

code

F

请先思考后再展开

一看就没法直接做……让我们分析一下用bitset做的复杂度……

首先如果求出S,那么就是 $(S\&(S>>1)\&(S>>2)).count()$

考虑怎么求,枚举每个元素,如果小于32就搞个lcm求出多少个int是循环节,手写bitset来做或运算,否则暴力跳

$O(n|S|/w+稍微大一点的常数*n/w)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/430f.html
转载请注明出处,谢谢!