考试总结[2021.08]

hzr和wyf的题

100+100+80+100=380 [rk1]

T1是个一眼题，有点码量，以为有什么厉害的简便做法，~~其实没有~~

T2一开始状态是4方的，不大对劲，优化了一下变成3方。考场上犯傻了，以为没法前缀和优化

实际上多个inf加起来也是能存的

T3是个极依赖于值域的题目，变成16进制后就随便 $O(1)$ 做了，考场上并没有把问题模型转化对，写了一个 $O(60*30*16)$ 的做法

T4是道简单题，随便推推就行了

xzy和cyj的题

100+100+100+95?(60)=395(360) [rk1]

前面简单题没什么意思，大概 10:10的时候过了前3题

T4题意：给定一棵树，点有点权 $a_i$ ，多次询问一条直链 $x\to y$ 上的 $\max_{z\in x\to y}\{a_z\bigoplus dis(z,y)\}$

考场上不会做T4，实际上部分分里有一档启发正解的分，但考场上并未深入思考

考场上隐约意识到本题正常做是肯定不行的，ban掉了polylog，一般分块

应该从值域上思考这个问题，考虑一段区间内编号对高位贡献是一样的

值域范围 $2^{16}$ ，那么若从 $2^x$ 处将值域分成两块

对于点 $i$ 预处理 $f_{i,s},s\in[0,2^{16-x}]$ 表示若跳到 $i$ 时前 $16-x$ 位的贡献是 $s$ 的最大答案

考虑每个点向上跳 $2^x$ 次父亲，将点扔进trie里， $s$ 的 $f$ 直接在trie里查即能得到，复杂度 $O(n2^{16-x}(16-x))$

此时对于每次查询仅需每一步跳 $2^x$ 级祖先即可，复杂度 $O(q(\dfrac{n}{2^x}+2^x))$

$n$ 接近 $2^{16}$ ， $x=8$ 时复杂度平衡

感觉这种套路没见过，完全搞不出来，考场上随便写了个暴力有95pts，数据湿度可以

集训队陈题

0(60)+30(100)+20(45)=50(205) [rk8]

没得大样例，输麻了，被各路xxs吊打

一上来开了2hT3没切掉，心态崩，用了1hT2过了，最后fst麻了

感觉T3最后一步差分很妙，不懂咋想到差分

感谢您的支持，我会继续努力的!