NOIP集训-10.29总结

跪跪跪跪跪跪
---------------------------------------------------------------------------------
 
Sequence:SuperOjP974
死神:人的直觉是很准的
然而我想了个错误的贪心..
外加随机排列拿了30分
---------------------------------------------------------------------------------
Cut:SuperOjP975
显然可以二分ABC吃到的个数
然后贪心地验证:每次尽量切得靠上、靠左,这样一定是最优的
---------------------------------------------------------------------------------
Xor:SuperOjP976
我拿到题又想都没想就写了个点分..然后又因为常数T掉了...
这是我第几次点分因为常数T掉?
 
nlog^2的点分作法:
对于重心的每一个子树,首先把它到根路径长度的二进制拿到字典树里面跑一遍(这个等会说),
然后将其加入字典树,然后接着分治。
这个到字典树里面跑,就是从高位到低位贪心地选择,显
然对于一个数v,和它xor起来最大的数是从高位到低位和它位取反之后匹配的更多的数(并且,高位的优先级远大于低位)
那么只需要将其取反然后去字典树里面跑,这一位如果是p,
如果当前节点有p这个儿子,就往这个儿子走,否则往仅有的儿子走,这样走到叶子为止,这个路径就是和v xor起来最大的数
 
nlog标算:
首先任意定一个根,对于任意两个点,显然它们之间的的路径长度的xor和就是它们到根路径长度的xor和
(因为LCA以上的部分xor了两次,相当于没有)
因此对于任意一个点,只需要看它前面哪些点的到根路径长度和它的xor起来最大
还是可以用字典树那个搞法,每个点,先去字典树里面跑一遍,然后加入字典树
---------------------------------------------------------------------------------