Round 889 Div.2 意识流简记。

太丢人了！D2D 狂吃 6 发罚时，D2C 都不会！不过无所谓，反正老年选手就是打着玩。

D2A. 答案为 \(\lceil \frac{\sum_{i=1}^n [a_i=i]}{2}\rceil\)。

D2B. 我不会啊，猜了一下只需要枚举 \(\le 2000\) 的，莫名其妙过了。

D2C1/C2. 不会。

D2D. 考虑动态维护前 \(i\) 个能凑出的数的集合，适时筛除 \(\le i\) 的。这是一个可行性 01 背包，bitset 维护即可 \(\mathcal O(n^2/\omega)\)，注意 bitset 要开两倍！！11

D2E. 考场上试图发动一眼丁真鉴定为 Min-Max 容斥未果，开始瞎胡猜，没过。其实比较诈骗。新加一个 \(S_{n+1}=m+1\)，最后只要所有 \(x\) 都和 \(x+1\) 重叠就结束了！然后你发现这个过程中我们可以只关注 \(x,x+1\)，至于 \(1\sim x-1\) 合到 \(x\) 上面以及 \(x+1\) 合到 \(x+2\sim n+1\) 上面都是没有影响的！只关注 \(x\to x+1\) 的期望步数的话，我们可以设 \(f_{i,j}\) 表示 \(S_x=i,S_{x+1}=j\) 的期望步数。有 \(f_{i,j}=\frac{(f_{i+1,j}+1)+f_{i,j+1}}{2}\)。答案为 \(\sum\limits_{i=1}^n f_{S_i,S_{i+1}}\)。\(\mathcal O(m^2)\)。我知道有些地方解释的不清楚，但我真的写不出来 qwq。意识流。