rqdmap
博客
/
Posts
算法
/
ACM
漫评
/
Anime
归档
/
Archive
关于
/
About
日志
/
Changelog
统计
/
Statistics
博客
/
Posts
算法
/
ACM
漫评
/
Anime
归档
/
Archive
关于
/
About
日志
/
Changelog
统计
/
Statistics
点分治
qko-gym
2021.04.02 21:10
2023.09.01 18:14
ACM
树形背包
乘积压缩
点分治
2247字
Day1 hdu6643 因为例题不仅有点分治还涉及到了树上依赖背包的算法,才发现自己并不太会树形背包的若干优化算法,故学习。 树形背包 模板题 给出一颗依赖树,询问总重量限定下可能获得的最大价值。 物品的数量和重量的限制均不超过100 有不同的做法,复杂度也不同。 向上合并 随意采取$O(nm^2)$的算法即可在 ...
点分治
2021.02.01 19:11
2023.09.01 18:14
ACM
点分治
树
3252字
洛谷 P3806 从一道经典的点分治问题入门 给出n个节点的树,树上的边有边权,进行m次查询,每次查询一个值k,询问是否存在一条两点间的路径使得路径上权值和为k $n <=10^4,m<=10^2,k<=10^7, w_i<=10^4$ 因为该题有多组查询,可以考虑一次点分后同时对m次查询进行处理,也可以考虑每次查询都进行一次点分。时间复杂度同为$O(nmlogn ...
创建时间
修改时间
字数