比赛地址

Lining Up

如果 $n$ 是奇数则应该是 $0,2,2,4,4,\cdots$,否则应该是 $1,1,3,3,5,5,\cdots$,排序后判断即可。

代码

Xor Sum

显然 $u\leq v$。设 $dp_{i,j}$ 表示前 $i$ 位,$v=j$ 时的方案数。考虑当前 $a,b$ 填的情况可以得到

$$ dp_{i,j}=dp_{i-1,\lfloor\frac{j}{2}\rfloor}+dp_{i-1,\lfloor\frac{j-1}{2}\rfloor}+dp_{i-1,\lfloor\frac{j-2}{2}\rfloor} $$

省去第一维后直接递归计算即可。

复杂度据说是 $\mathcal{O}(\log n)$ 的,但是我并不是很会证。

代码

Addition and Subtraction Hard

可以发现超过 $2$ 层的括号嵌套是没有用的。

设 $dp_{i,j}$ 表示前 $i$ 个数,还有 $j$ 个左括号未匹配的最大值,转移讨论一下各种各样的情况即可,具体可以看这里

代码

Contest with Drinks Hard

不会,也不想写。

最后修改:2020 年 09 月 12 日 10 : 32 PM