Round 1
虽然心情不好但是还是来记录一下。
cube
考虑到一个位置只有满足三个方向全部都可以填才能填,此时在立体图形种会生成若干个连通块,对于每个连通块 check 一下是否能够将输入给覆盖满,复杂度是 \(O(n^3)\) 的。
然而由于一些小 case 挂成 \(0\) 蛋了。
chain
首先期望是从后往前考虑,设 \(f_{i, j}\) 表示第 \(i \sim n\) 个门中,有 \(j\) 扇门是打开之后关上在其它地方的期望。
然后发现我们在每个更新地点去计算其开门次数的期望,此时你需要类似于求一个 \(\frac{1}{s} + \frac{2}{s^2} + \frac{3}{s^3} + ...\) 的一个东西,具体方法就是你考虑将它拆成后缀和做一遍等比数列,然后合起来再做一遍等比数列。
写起来就跟吃了屎一样难受。
eri
神秘容斥题。
uika
首先想用单调栈把这个东西描述出来,然后发现神秘异或哈希完后等同于你要数区间最小值和区间最小值个数,你发现相当于把每个询问区间摊到一段区间上去做这个事情,于是你写个历史和,这个东西就很容易维护出来了。
但你考虑到我并不会历史和。
题解是求补集,发现这个东西有很好的意义可以摊到平面上做于是就变成确定性做法了。