CodeforcesLuogu分析一个不要脑子的做法是线段树分治,即以时间为下标将所有物品与询问挂到线段树上,在线段树上递归时维护一个长度为 $4000$ 的 0/1 背包的 DP 数组即可。标解给的是一个奇妙的分块做法,大概是分成 $p$ 块,从每个交界点往左右跑 0/1 背包,然后每个询问一定会包含一个交界点,直接将左右合并即可。代码因为我懒所以只有第一个方法的代码。// =======...
Luogu分析枚举一个答案 $ans$,那么我们相当于要求在删去边权为 $ans$ 的边后图是否存在一棵生成树,即图是否连通。显然可以考虑线段树分治。具体的,建一棵以边权为下标的线段树,对于每条边权为 $w$ 的边将其放到 $[0,w-1]$ 和 $[w+1,10^5]$ 上。然后在线段树上遍历,遍历到一个节点就将它上面挂着的边连上,这样子到叶结点时就连上了所有不包含该边权的边,判断图是否连...
LOJ分析线段树分治板子题?考虑每条边出现的时间都是若干段区间。我们以时间为下标建一棵线段树,然后在每条边出现的区间挂上这条边。然后我们把询问挂在叶节点上。DFS 这棵线段树,每次到一个节点后就把这个节点上挂的所有边连上。这样子到叶节点时该时间点所有的边都已经连上了,直接询问是否连通即可。这个过程中用一个可撤销并查集维护连通性即可。代码// =========================...