比赛地址

Make a Rectangle

求出每种边的数量,$\geq 4$ 的看成 $2$ 个,$\in[2,3]$ 的看成 $1$ 个,将最大值和次大值作为长和宽即可。

代码

Coloring Dominoes

根据当前列和上一列的情况算出当前的方案数,用乘法原理乘起来即可。

代码

Don't Be a Subsequence

设 $nxt_{i,j}$ 表示 $[i,n]$ 中最靠前的 $j$ 字符的位置,$dp_i$ 表示最短的不是 $[i,n]$ 子序列的串长。

那么当 $[i,n]$ 中有一种字符不存在时,$dp_i=1$;否则枚举子序列第一位 $j$

$$ dp_i=\min\left\{dp_{nxt_{i,j}+1}+1\right\} $$

构造方案的话,如果当前为填的是字符 $j$ 则应有 $dp_i=dp_{nxt_{i,j}+1}+1$,顺序构造即可。

代码

Flip and Rectangles

结论:一个矩形能变成全黑的当且仅当其每个 $2\times 2$ 的子矩形中都有偶数个黑色块。

那么我们就把问题转化为了求最大子矩形,直接悬线法解决即可。

注意答案要对 $\max(n,m)$ 取个 $\max$,因为上面求出来是至少两行/两列的,而一行/一列的黑色矩形是一定能构造出来的。

代码

最后修改:2020 年 09 月 23 日 05 : 05 PM