转载请注明出处:http://tokitsukaze.live/

题目链接:http://codeforces.com/contest/1062


A:
前面补个0,后面补个1001,然后直接n*1000暴力,最后输出max(0,ans-2)。

B:
最小答案肯定是质因子的乘积。

最小次数为x+flag。x为出现最多质因子的出现次数,转换为二进制的长度减1。flag为0或者1,表示是否要补。

C:
cnt0表示区间0的个数。cnt1表示区间1的个数。

ans=2^cnt1+(2^cnt1-1)*(2^cnt0-1)-1

D:
x -> y -> -x -> -y -> x,贡献是4*(y/x)。
若x与x的倍数连边,所有边都能走到。

所以直接埃氏筛暴力枚举x的倍数统计答案。

E:题意:给一棵树,q次询问,每次询问节点[l,r]中,只删除一个节点,剩下节点求LCA深度最深,输出删除的节点编号和LCA的深度。

dfn越接近,LCA越深。所以删一个点,只可能删这个区间的dfn最小或者最大的点。

线段树维护区间dfn的最值与次值。删最小的话,LCA就是dfn次小和最大的LCA。删最大的话,就是次大和最小。

代码:
https://github.com/tokitsu-kaze/ACM-Solved-Problems/tree/master/Codeforces/Codeforces%20Round%20%23520