我不好说。晚起的星星或许也是星星，哪怕它是被别人拿鞭子抽升起的。
因为很菜，所以可能也会记录很多 naive 的题目。
「ARC104C」
想歪了，构造方案非常繁琐。考虑到题目只要求是否可行，所以思考可达性 dp。如果给 \(-1\) 的空位填数就回到了构造方案的思路上，不妨转而考虑每个楼层的上下情况。
记 \(f_i\) 表示前 \(i\) 层是否有合法方案，转移有 \(f_i = \vee \{ f_{j - 1} \wedge \mathrm {check}(j, i) \}, 1 \leq j \leq i - 1, 2 | i - j + 1\)。且有 \(f_0 = 1\)，需求 \(f_{2n}\)。
那么对于区间 \([j, i]\)，如果有 \(j\) 以下楼层到达该区间的，或者从该区间出发到 \(i\) 以上的，则该区间不合法。以此去重。
为保证区间内的长度全相同，考虑模拟合法状态的阶梯型，则合法的区间需满足在前半段都是上电梯，后半段都是下电梯。最后特判一下已有的是否符合即可。
「ARC104E」
读错题了，英语非母语劣势区间。似乎读对题了也不是很难顶。
观察值域 \([1, n] \to [1, x - 1] \vee \{x\} \vee [x + 1, n]\)。\(x\) 可以随便取，这里有 \(k + 1\) 种方案。
剩下的就是在 \([1, x - 1] \vee [x + 1, n]\) 里选出合法的可重集使得和为 \(0\)。不妨考虑把值域减掉 \(x\)，则有 \([1 - x, -1] \vee [1, n - x]\)。记 \(f_{i, j}\) 表示选择 \([1, i]\) 里的合法可重集和为 \(j\) 的方案数，则答案为
\[(k + 1) \times \sum \limits _{i = 0} ^{\frac {n (n + 1) k} {2}} f_{n - x, i} f_{x - 1, i} - 1 \]多重背包即可，顺便学习前缀和优化多重背包。
标签：方案,板刷,合法,leq,vee,归档,区间 From： https://www.cnblogs.com/STrAduts/p/17732889.html