贪心、动态规划缺少转化问题的意识。由于 $n,W$ 同阶,直接枚举第 $i$ 种物品拿几个再跑完全背包的时间复杂度为 $O(n^3)$,不可接受。第 $i...
贪心、动态规划缺少转化问题的意识。由于 $n,W$ 同阶,直接枚举第 $i$ 种物品拿几个再跑完全背包的时间复杂度为 $O(n^3)$,不可接受。第 $i...
数据结构从前缀和角度考虑,使用 $sum_{i,j}$ 表示前 $i$ 天第 $j$ 项能力的提升次数。假设一段均衡时期从第 $l$ 天开始,到第 $r$...
树形动态规划、二次扫描使用 $a_i$ 表示节点 $i$ 的点权,将黑点的点权改为 $-1$,问题转化为对每个 $i$ 求树上包含 $i$ 的连通块的点权...
悬线法、极大子矩形类问题二维悬线法维护符合条件的极大子矩形取最大面积。具体地,维护 $h_{i,j}$ 表示以第 $i$ 行为底边且包含位置 $(i,j)...
数学、前缀和考虑 $b_i$ 的贡献时间复杂度 $O(n)$。#include<bits/stdc++.h> using namespace ...