Codeforces Round #359 (Div. 1)

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

 

说点什么

提醒
avatar
Lesphere
Lesphere

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