BZOJ 5121 [2017 国家集训队测试]Hello world!


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5121

题意:

一棵树,有点权,支持两个操作:

  1. 从 s 到 t 每隔 k 个位置都开个方。
  2. 从 s 到 t 每隔 k 个位置加起来求和。

打 LOJ 的 VP 的时候写暴力+卡常拿了 83pts...

其实 YY 出做法是不困难的,考虑维护深度模 K 意义下相同的节点,建 K 颗树即可。

k 较大的时候暴力跳,否则 dfs 序+树状数组统计。

对于修改操作,用并查集将都是 1 的串起来即可,开方 log 次就变成 1 了,和花神游历各国那题是一样的。

然后就没了...

结果巨不好写,BZOJ 也挺卡常的...

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 5121 [2017 国家集训队测试]Hello world!


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,