有 n 个物品，第 i 个物品价值为 a_i，要求选一部分物品，使得总价值不超过 m，求总价值的最大值。
直接暴力做是 O\left(\dfrac{nm}{\omega}\right) 的。
将 a_i 从小到大排序。
先贪心地从前往后选物品，直到不能再选。此时我们得到了一组 \in [m-a_n,m] 的解。
接下来我们需要新选一些物品并回退一些物品。
考虑一组最优解中的所有新选的物品和回退的物品，可以发现一定存在一种把两个物品序列归并起来的方式使得任何一个时刻总价值 \in [m-a_n,m+a_n]。
因此我们可以设 dp_{i,j,k} 表示当前新选到 i，回退到 j，当前总价值为 k 是否可以取到。
直接做的时间复杂度并没有优化，但我们发现对于一组固定的 i,k，只需要保留最小的 j 即可。我们考虑改变一下状态：设 dp_{i,j} 表示当前新选到 i，总价值为 j，最后一个回退的物品的最小位置。
这样状态数就被优化到了 O(na_n)，但是时间复杂度依然没有优化。
可以发现对于一个固定的 j，dp_{i,j} 是单调不增的。而用 dp_{i,j} 去转移其它状态的时候只需要考虑 (dp_{i,j},dp_{i-1,j}] 这段区间中的物品的回退情况。这是因为 >dp_{i-1,j} 的物品的影响在 i-1 这一行已经计算过了，而 \le dp_{i,j} 的物品本就不能参与转移。
这样时间复杂度就被优化到了 O(na_n)。做法还是很精妙的，感觉第一次遇到时很难想得到。
有 n 种物品，每种物品都有无限多个，第 i 种物品有重量 a_i 和价值 b_i。问选出一些重量不超过 m 的物品的最大价值和。
方法 1：
设 dp_{i,j} 表示前 i 个物品，总重量为 j 的最大价值。时间复杂度 O(nm)。
方法 2：
考虑数位 dp。
在二进制下从高往低依次考虑每种物品选取的数量的每一位。状态中记录当前剩余的值，这可以对 \sum a_i 取 \min。每一层的转移是 O(n\sum a_i) 的 01 背包。时间复杂度 O(n\sum a_i\log m)。
方法 3：
设 c=\max\{a_i\}。
先贪心地按照 \dfrac{b_i}{a_i} 从大到小取。设当前取的总重量为 m'，那么显然 m-m'<c。
考虑使用 dp 调整当前的方案得到最优解，我们会加入一些未选取的物品并删除一些已选取的物品。
设 S_1 为所有加入的物品的重量组成的可重集，S_2 为所有删除的物品的重量的相反数组成的可重集。
如果存在 S_1 的一个子集 T_1 和 S_2 的一个子集 T_2 满足 T_1 和 T_2 中所有元素的和为 0，那么可以将方案调整为 S_1\leftarrow S_1\setminus T_1,S_2\leftarrow S_2\setminus T_2。因为 S_1 中的物品 \dfrac{b_i}{a_i} 更大，所以这样一定不劣。因此我们可以认为不存在这种情况。
考虑将 S_1,S_2 中的所有元素按照一定顺序排成一个序列，使得每一个前缀和的绝对值都不超过 c。通过分析可以发现 S_1,S_2 中的所有元素之和在 (0,m-m'] 中。可以得到如下构造方式：初始序列为空，如果当前总和 <0 就在末尾加入任意一个 S_1 中的数，否则在末尾加入任意一个 S_2 中的数。显然这个构造是合法的。
在这个序列中如果存在两个前缀和相同，那么一定与上面的性质矛盾。又因为之前的构造方式保证了前缀和的值域大小为 O(c)，所以 S_1,S_2 中的元素数量之和为 O(c)。
因此我们可以将背包的容量上限设为 O(c^2)。时间复杂度 O(n\log n+nc^2)。
进一步地，我们可以发现重量相同的物品一定是选择 b_i 最大的若干个，而我们已经证明 |S_1|+|S_2|=O(c)，因此最优解在这种 a_i 中的决策只有 O(c) 种可能。所以我们对于每种不同的 a_i 进行转移即可做到 O(c^4).
因此时间复杂度为 O(n\log n+\min(nc^2,c^4))。
给定一个 n 个点 m 条边且有边权的 DAG，进行 c 次询问，每次给定 u,v,l,r，求出从 u 开始只经过边权在 [l,r] 内的边是否能到达 v。
第一眼看上去是高端数据结构题，然后想了一年完全不会。。。
正解非常简单，但是可能真的不太容易想到。
设 dp_{i,j} 表示从第 i 个点开始只经过 [l_j,r_j] 中的边是否可以到达 v_j。
只需要计算这个 dp 数组即可得到答案，而这是非常容易的。再用 bitset 优化一下即可。
时间复杂度 O\left(\dfrac{(n+m)c}{\omega}\right)。
如果要节省空间可以把每 \omega=64 个询问分成一组在 DAG 上跑，直接用 ull 存就行了。
其主要思想可以看作把两维换一下（抽象）。
具体来说，暴力的做法是对于每个询问在 DAG 上做一遍，现在把它改为按照某种顺序加入 DAG 中的边，并计算它对询问的影响。
给定一棵 n 个点的有根树，根为 1。每个点 u 有两个正整数权值 a_u,b_u 和一个颜色 c_i\in\{0,1\}。
要求选一个点的子集 S，满足：
求 \sum\limits_{u\in S} a_u\le m 的情况下 \sum b_u 的最大值。
对于每个点 u 求出只保留 u 的子树时的答案。
设 dp_{u,i,j} 表示考虑 u 的子树，最顶上选的一层点颜色均为 i 的答案，且当前 \sum\limits_{u\in S} a_u=j。
但直接 dp 的时间复杂度为 O(nm^2)，无法通过。
我们希望避免两个 dp 数组的合并，因为合并一次就会带来 O(m^2) 的巨大代价。
设 dfs 函数可以计算 dp_u，考虑按照如下方式进行计算。
function dfs(u, z)
if u is not leaf then
hv = (heavy child of u)
z1 <- dfs(hv, z)
for v in {children of u} / {hv} do
z1[0] <- dfs(d, z1[0])[0]
z1[1] <- dfs(d, z1[1])[1]
end for
else
z1[0] <- z
z1[1] <- z
end if
for i = 0 to m - a[u] do
chmax(z1[c[u]][i + a[u]], z1[c[u] ^ 1][i] + b[u])
end for
return z1
dfs 函数的意义是，考虑 u 的子树，给定序列 z 表示初始值，返回两个序列分别表示 u 的子树内选择的最顶上一层点颜色全为 0/1 的答案序列。
考虑一次对根节点的 dfs 的时间复杂度。
每访问一个点就会产生 O(m) 的代价，设 k 为 u 到根节点上的轻边条数，那么 u 被访问的次数为 2^k。可以证明访问次数总和是 O(n^{\log_23}) 的，在满二叉树下基本卡满。
通过调用 dfs 我们可以计算出一条重链上所有点的答案。
对于每个轻儿子都调用一遍 dfs 即可求出所有答案，总时间复杂度依然为 O(n^{\log_23}m)。