比赛地址

只会做 A,自闭了

Prefix and Suffix

枚举重叠部分的长度即可。

代码

Median Pyramid Easy

显然 $x=1$ 和 $x=2n-1$ 的情况无解。

我们在中间放上 $x$,在它左边放 $x-1$,右边放 $x+1$ 和 $x-2$,可以发现这样子中间就会出现两列 $x$ 一直通到最顶上。

然而 $n=2$ 时只有三个数,需要特判掉。

代码

Rabbit Exercise

设 $f_i$ 表示 $i$ 的期望位置,在一轮后显然有 $f_i\leftarrow \frac{1}{2}((2f_{i-1}-f_i)+(2f_{i+1}-f_i))$,即 $f_i\leftarrow f_{i-1}+f_{i+2}-f_i$。

看题解后可以想到差分。设 $d_i=f_i-f_{i-1}$,推一推式子发现一轮后 $d_i\leftarrow f_{i+1}-f_i$,$d_{i+1}\leftarrow f_i-f_{i-1}$。

于是一次操作相当于交换了差分数组中的两个位置。我们只要求出一轮对应的置换,然后每个环转一下即可。

代码

Median Pyramid Hard

考虑二分答案,则我们需要判定一个 $0/1$ 序列到最上面是 $0$ 还是 $1$。

手玩一下可以发现大概是这个情况

图片来自官方题解

于是我们只需要找到离中间最近的连续两个相同的即可。显然这个最近连续段只会有一个。

注意特判一下没有连续两个相同的情况。

代码

Rotate 3x3

一次旋转相当于交换两列,再翻转三列。

显然,如果原来的一列是 $a,b,c$,那么最后一定有一列是 $a,b,c$ 或者 $c,b,a$,所以先把不满足这个的判掉。

接着求出原来的每一列到哪一列去了。显然每一列只能移动偶数列,所以再把不满足这个的判掉。

我们记一下一开始奇数列和偶数列各有多少列是翻转的,然后把奇偶列分开求逆序对(同时可以求出过程中有多少个中间列被翻转),就可以求出列归位后奇数列和偶数列各有多少列还是翻转的。

手玩一下可以发现,我们还可以用一些操作使得隔着一列的两列同时翻转,所以如果最后奇数列、偶数列翻转列数都是偶数就合法,否则就不合法。

代码

Blackout

显然可以把一个黑格 $(x,y)$ 看做一条边 $x\to y$,则题意变成:给定一张有向图,如果有边 $x\to y$ 和 $y\to z$ 则连边 $z\to x$,求最后会有多少条边。

显然每个弱连通分量可以单独考虑,我们只考虑连通图。

因为这个连边会连出一个三元环,所以考虑对图循环三染色(即红点连向蓝点,蓝点连向黄点,黄点连向红点),那么有以下几种情况:

  • 不能染色,可以发现此时会连成完全图,答案即为 $n\times n$。
  • 可以染色但没有用三种颜色,可以发现此时不会连边,答案即为 $m$。
  • 可以染色且用了三种颜色,可以发现所有红点都会有连向所有蓝点的边,其它颜色类似,答案即为 $c_r\times c_b+c_b\times c_y+c_y\times c_r$。

代码

最后修改:2020 年 08 月 21 日 10 : 01 PM