版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - Codeforces Round #639 Div. 2 (A-D)" categories:
打一半改成 unrated 了海星
惨 Monogon 惨
<!--more-->有 $n\times m$ 个完全相同的拼图块, 每个均一凹三凸, 如图
问对给定的 $n$ 和 $m$, 能不能拼出 $n\times m$ 的矩形
不妨假设 $n\leqslant m$
首先当 $n=1$ 时和 $n=m=2$ 时显然可以
而如果想拼出 $n\times m,2<n\leqslant m$ 的矩形, 必然需要先拼出 $(n-1)\times m$ 和 $n\times(m-1)$ 的矩形
观察发现, 如果矩形可以拼出, 则每条拼图块的公共边必然为一凹一凸, 可以发现 $m=3$ 和 $n=3$ 时的矩形一共 $7$ 条公共边, 但所有拼图块一共只有 $6$ 个凹边
故可能的情况只有 $n=1$ 时和 $n=m=2$ 时
输入 $n$, 计算能搭出几个卡牌金字塔
图示即为卡牌金字塔高度 $h=1,2,3$ 时的情况
易得高度为 $h$ 的卡牌金字塔所消耗的卡牌总数为 $\frac{1}{2}(3h^2+h)$
所以直接打个表然后二分查找就好了
其实不用二分也能过, 直接从高到低遍历一遍就行
不需要二分就可以做到单次 $O(\sqrt n)$ (实际上我比赛时的二分做法也是 $O(\sqrt{n})$ 的, 常数反而更大些)
此时的总体复杂度显然是 $O(\sum_{i=1}^t\sqrt{n_i})$, 不过可以将其写成更好看的形式
令 $N=\displaystyle\sum_{i=1}^tn_i$, 由 Cauchy-Schwarz 不等式可知
$$ \sum_{i=1}^t\sqrt{ni}\leqslant\sqrt{\sum{i=1}^t1\cdot\sum_{i=1}^tn_i}=\sqrt{tN} $$
所以可以记作 $O(\sqrt{tN})$
给出 $n$ 和一组数 $a_0,a1,...,a{n-1}$, 问是否 $\exists x,y\in\Bbb{Z}, x\ne y\ s.t.\ x+a{x\operatorname{mod}n}=y+a{y\operatorname{mod}n}$
首先我们可以发现
所以我们只需在 $\Bbb{Z}_n$ 下考虑即可
若
$$ \exists x,y\in\Bbb{Z}n, x\ne y\ s.t.\ x+a{x\operatorname{mod}n}\equiv y+a_{y\operatorname{mod}n}\pmod n $$
则
$$ \exists x,y\in\Bbb{Z}, x\ne y\ s.t.\ x+a{x\operatorname{mod}n}=y+a{y\operatorname{mod}n} $$
单次 $\Theta(n)$
有个 $n\times m$ 的地图, 每个格子都染成了黑色或白色, 每个格子还可以放单极磁铁(当然这玩意现实中不存在), 如果 N 极和 S 极同行或同列, 则 N 级可以向 S 极方向移动一格, 要求
问对给定的地图是否存在放置单极磁铁的方案, 如果有的话一共可以放几个 N 极
如果有方案的话, N 极个数显然为黑格连通块个数
如果在某行/列出现两个黑格中间有白格的情况, 则中间的白格有可能被经过, 否则该行/列没有 S 极
如果某一行/列全白, 则必有某一列/行全白, 从而 S 极可置于交点处. 否则白格有可能被经过, 或该行/列没有 S 极
所以只需要先遍历看看是否存在上述情况, 如果没有再求个连通块个数就行了
$\Theta(nm)$