Codeforces Round #359 (Div. 1)

2016年6月24日8443
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)的

 

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

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