ecf 之前训练纪要

百度之星以赛代练。

cf1917F

将 \(l\) 排序，如果 \(l_n>\frac d2\) 那么 \(l_n\) 必然在直径上，背包一个 \(d\) 即可。如果 \(l_n+l_{n-1}>d\) 那么不行。

如果 \(l_n<\frac d2\) 那么需要满足找到两个子集满足 \(\sum S_1+\sum S_2=d\) 并且 \(\min(\sum S_1,\sum S_2)>l_n\) 使用 std::bitset 加速 dp 即可。这个加速分为两种，\(g_{i,j}\) 从 \(g_{i-l,j}/g_{i,j-l}\) 转移，对应 or“自己右移” 和 orbitset[i-l]