点分治 – Tgotp-Blog

P3806 【模板】点分治1

既然已经说了是模板,那么考虑怎么套用点分治。
容易想到记录到所有值的方案数,但是发现瓶颈在于每次结束以后去枚举答案。
因为k在1kw,显然单次统计都会有1kw的复杂度,考虑优化,发现实际上只有不到1w个取值,
那么在每次新增一个取值的时候去更新即可,然后现在又有一个问题在于每次新查找的时候数组[......]

Read more

E. Alternating Tree

尽管 卡了我一早上,我一点都不气….
这数据是真的强.
观察题目发现实际上偶数链是没有任何用的.
然后这种树上路径一般考虑用点分治。
那么记录从一个点跑出去的奇/偶链数量与和,
然后令所有 奇链 偶链 互相链接,然后就得到了从该点延出去的所有边,
但是要注意一开始要把这个点排除最[......]

Read more

T7895 于尽头开拓

暴力出奇迹,骗分过样例。

传递里面的ll没写,100 -> 70

空格打成了换行符 70 -> 0

我的内心是崩溃的。

嗯,正解应该是点分治,没写出来,反正暴力a了ORZ

c++代码如下:

[......]

Read more

BZOJ2152

照着黄学长的博客抄抄改改;

至于点分治的大体模板是成外学的一种。

这个比较好。