2018-11-18
转载请注明出处: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。删最大的话,就是次大和最小。