今日学习：测试+修改测试+CF#831今日总结：今天的T1完全就是猜的结论，然后验证了一下发现真的是对的。看来有的时候猜也不失为一种妙计。真的就是应了之前CF比赛题解里的那句 "Programmers are not mathematicians, you do not need to prove it"。不过赛后发现确实证明也很简单，只用考虑为把一个人分成四个，每一个占1/4的概率，然后对于每一个1/4人期望有多少个1/4人比他大。今天的T2赛时打的是正向的A*算法，后来赛后才知道其实倒着来可以大大的降低时间复杂度和空间复杂度。所以正难则反并不一定只用于推规律的时候，有的时候搜索也可以用上。最后题解是用了 "3n + 1" 猜想，这确实不在知识范围内了，不过倒着搜索已经非常接近答案了。今天的T3需要先把原式写出来，然后化简，把相同的部分合并，然后就可以发现其实有一些部分可以利用前缀和来维护，只需要乘上一个共同的权值就可以了。同时应用了一个特殊的求 lca 到根距离的方法，例如求 dis[lca(i, j)] ，那么就在点 j 到根的路径上都给权值加上一个 1，然后算 i 到根的路径上的权值和就可以了，lca到根的距离平方和也可以利用相同的方法，但是要注意这里其实是从根到每个点上加上一个等差数列(1, 3, 5, 7, ...) 你会发现这个等差数列的前缀和就是平方数。我们可以利用树剖 (重链剖分和实链剖分(LCT)都可以，但在这个数据范围下实测重剖会更快) 维护这些信息，当然这个问题还涉及滑窗，这只需要按时减掉已经过时的信息即可。T4我写的DP其实完全就是假做法，但却骗到了10pts，十分不错。但其实有一些细节没实现好，不然其实可以骗到 45pts，再加入一些优化就可以骗到 75pts 的好成绩！！！明日计划：测试+修改测试+继续CF#831