自己会做ABCDEFG，主要是这场 Edu 太水了，做起来和 Div3 感觉一样。。A选择第一个，第二个和最后一个。判断是否可行即可。B显然每次都会选择最长的 $1$ 的连续段。模拟即可。C设前缀和为 $s_i$。一个区间合法的条件是 $s_r-s_{l-1} = r-(l-1)$，推一下式子是 $s_r-r = s_{l-1}-(l-1)$，直接 map 记录一下就好了。D每次肯定会取出两...
题意$n$ 个点的树 每个点有一个体积 $v_i$ 和收益 $w_i$。只能选择不相邻的物品 要求你输出 $\forall i \in [1,m]$，容量为 $i$ 的背包收益最大的方案数$n \leq 50,m \leq 5000$题解很 naive 的 dp 大概是 $f[i][j][0/1] $ 表示处理 $i$ 号点子树 已经用了 $j$ 容量，是否选择这个点的方案数 转移的时候搞个...
题目链接题目大意$n \times m$ 的网格图 要求你求一个大小为 $k$ 的最小权匹配。$n \leq 40000,m \leq 4,k \leq \frac{nm}{2}$多组数据 数据组数 $T \leq 1000$，保证只有三组数据 $n > 100$。题解首先这个题是可以二分图染色跑费用流的。所以设 $w_i$ 表示 $i$ 条边的答案。很容易有 $w_i-w_{i-1}...
主要是为了学习一波 wqs 二分。首先发现这个题目等价于把树切成 k+1 块 每块内选个直径加起来，也就等价于在树上找 $k+1$ 条不相交的链使得收益最大。考虑树上每一条链都可以拆成两条深度单调的链，所以我们可以设 $f[i][j][0/1/2]$ 表示现在在 $i$ 点 已经选择了 $j$ 个链 当前 $i$ 点的状态是（没有链经过/有一条单链待匹配/有链经过），转移一下就可以了，复杂度...