被吓跑了
A
正着做不好做，考虑倒着做。我们有一个最大的往前面加东西，考虑到\(i\)的时候最大的是\(ans\)，那么我们要在\(ans\)前面加入若干个数字使得\(ans\)前面满足删除序列。
- Case \(ans<a_i\)：这个时候显然不用在\(ans\)前面加任何东西
- Case \(ans\ge a_i\)：我们发现\(a_i\)加的位置是\(a_i,a_i+i,a_i+2i,\cdots\)
- Case \(ans\ge a_i+(k-1)i\)：我们需要把\(a_i\)全部加到\(ans\)前面，故\(ans+=k\)
- Otherwise ：由于是同时加入的，所以式子就是\(ans+=(ans-a_i)/i+1\)
B
先盲猜一个结论，可以在\((n,-n),(n-1,-n+1),\cdots,(1,-1)\)这\(n\)个对中每个对挑选一个数来解决这个问题。场上想到了这里后面就没细想了。
我们考虑对于目前最大的\(b_x\)，显然有\(a_x=0\oplus a_x=n\)成立，若两者均成立则意味着同时存在\(n\)和\(-n\)。若\(a_x=0\)则\(b_x=-n\)，反之\(b_x=n\)，我们依据这个把\(b_x\)的值判断出来后就可以把\(b_x\)消除掉，同时记录一下影响就好，之后就是子问题了。
C
考虑已经确定了每个位置需要减几次，那么这个时候总的减的次数是好求的，那么显然有一个\(O(n^2)\)的\(\text{dp}\)，令\(f_{i,j}\)为考虑到了第\(i\)个，第\(i\)个所需次数加了\(jk\)次时的最优解，答案就是\(f_{n+1,0}/2\)。同时有一个显然性质，相邻两个数所需减的次数的差的绝对值不会超过\(k\)，不然一定不优，根据这个性质我们就可以实现\(O(n^2)\)的\(\text{dp}\)。
考虑如何优化上述\(\text{dp}\)，注意到我们总是需要把这个数字减到\(0\)，那么每一步显然是能减就减，只有不能减的时候才需要考虑，注意到改变一个路径中的一个减为加并不会对其他地方产生影响，那么有个经典的东西叫做反悔贪心，故我们直接拿一个优先队列存一下之前改减为加的代价，每次不能减的时候拿出最小的考虑一下就能选择当前这步是减还是加，就可以在\(O(n\log n)\)的时间复杂度内完成本题。
D
显然有\(\text{bitset}\)优化\(\text{dp}\)，\(f_{i,j}\)表示到了第\(i\)位为\(j\)时能够达到的数，转移为：
\[ \begin{align*} f_{i,0} &= \text{LeftShift}(f_{i-1,0}, s_i\neq 0)\lor \text{LeftShift}(f_{i-1,1},s_i\neq 0+1)\\ f_{i,1} &= \text{LeftShift}(f_{i-1,1},s_i\neq 1)\lor\text{LeftShift}(f_{i-1,0},s_i\neq 1+1) \end{align*} \]
打表发现每个状态都是连续的\(O(1)\)段，原因显然，因为每次转移的时候只会左移\(\{0,1,2\}\)次，自然段数不会很多。那么直接把所有段存下来转移即可，倒序构造答案。