Codeforces Round #359 (Div. 1)

2016年6月24日1,2993
A. Robbers’ watch
可以先算出n-1,m-1所需的位数
如果位数和超过7,根据抽屉原理,则一定会存在相同的数字
特判一下输出 0 后,位数小等于 7 的情况暴力即可
枚举 i<n , j < m,七进制拆分一下看有没有相同数字

B. Kay and Snowflake
题意是询问一棵树某些子树的重心
树的重心定义为,删去这个结点后,剩下的连通块大小不超过1/2*(总结点数)
用yi表示x结点的儿子
预处理size[x]和mx[x]表示树的大小,yi树的最大结点数,用于判断一个结点是不是重心
根据性质,x的重心应该在yi的重心之间的路径上
转移的时候只要把每个树yi的重心到x的路径从下往上暴力判断一下,发现重心就退出
复杂度相当于从每个叶子走向根,也就是遍历一棵树,显然是O(n)的

 

  • Lesphere2016年6月27日 上午10:50 回复

    B题复杂度应该是Σ(每个叶子到整棵树的重心的距离)
    能不能证明这是O(n)的

    #1  
    • hzwer2016年6月27日 下午3:06 回复

      并不是这样的,每个结点从它儿子的重心开始往上找,也就是说重心移动不会重复走一条边

      #11
      • Lesphere2016年6月27日 下午9:50 回复

        懂了,每个点的儿子中,只有重儿子会有代价,其他儿子无关
        相当于树链剖分一样分成很多条链,重心最多经过链上每条边一次

        #12