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