比赛地址

Wanna go back home

如果 EW 仅存在一个,或者 NS 仅存在一个,则一定无法回到原点,否则一定可以回到原点。

代码

Simplified mahjong

直接扫一遍,能凑就凑即可。正确性显然。

代码

BBuBBBlesort!

注意到使用操作 2 后不改变元素下标的奇偶性,而每个元素应该还原到的下标是已知的,因此我们可以统计出有多少个元素始末位置奇偶性不同,记为 $s$。

再注意到使用操作 1 可以交换改变两个元素下标的奇偶性,因此答案即为 $s/2$。

证明感觉比较简单,可以自己试着想一下。

Anticube

为了方便,定义 $f(x)=p_1^{c_1\bmod 3}\times p_2^{c_2\bmod 3}\times\cdots\times p_k^{c_k\bmod 3}$,$g(x)=p_1^{(3-c_1)\bmod 3}\times p_2^{(3-c_2)\bmod 3}\times\cdots\times p_k^{(3-c_k)\bmod 3}$,其中 $x=p_1^{c_1}\times p_2^{c_2}\times\cdots\times p_k^{c_k}$。

容易发现一件事:如果 $a\times b$ 是完全立方数,那么一定会有 $f(b)=g(a)$ 或者说 $g(b)=f(a)$。

因此我们只需要开一个桶记一下所有的 $f(x)$,然后枚举所有的 $f(a)$,在 $f(a)$ 和 $g(a)$ 中选较多的那个即可。

现在的复杂度瓶颈实际上在于计算 $f(x)$ 和 $g(x)$。可以直接上 Pollard-rho,但有一种比较高超的方法:用三次方根内的所有质数分解一遍,然后至多剩下两个质因子,它(们)的贡献就很好计算了。具体可以参考一下代码。

代码

Sequential operations on Sequence

首先可以注意到,先变长再变短等价于直接变短,因此我们可以用原操作序列的一个单调递增的单调栈替换掉操作序列。

考虑从 $a_{i-1}$ 变长到 $a_i$ 时发生了什么。首先我们把整个序列重复 $\left\lfloor\frac{a_i}{a_{i-1}}\right\rfloor$ 遍,然后再在后面接上最前面的 $a_i\bmod a_{i-1}$ 个元素。

我们考虑对于每个操作计算一个系数 $w_i$,表示这一段完整地重复了多少遍。

考虑怎么算这个东西。因为整个序列是越变越长的,所以我们从后往前推。

前面完整出现的部分比较好处理,直接将 $w_{i-1}$ 加上 $w_i\times\left\lfloor\frac{a_i}{a_{i-1}}\right\rfloor$ 即可。现在重点考虑如何计算后面 $a_i\bmod a_{i-1}$ 个元素的贡献。

我们二分出一个最大的满足 $a_k<a_i\bmod a_{i-1}$ 的 $k$,那么相当于 $a_k$ 重复了一些并在后面多出来了一些。于是我们给 $w_k$ 加上一个系数,然后把后面多出来的一些递归处理下去即可。

递归到最后时相当于一段前缀出现次数加上一个值,直接差分即可;然后前 $a_1$ 个元素完整出现了 $w_1$ 次,将这一部分加上去即可得到答案。

感觉描述起来很抽象,可以结合代码理解一下。

代码

Fraction of Fractal

一些定义:

  • 如果某一行最左和最后都是 #,则称该行为一个「左右接口」。
  • 如果某一列最上和最下都是 #,则称该列为一个「上下接口」。

我们先考虑一些特殊情况。

如果原图既没有左右接口,也没有上下接口,则答案为 $c^{k-1}$,这里的 $c$ 为 # 的数量。

如果原图既有左右接口,又有上下接口,则答案为 $1$。

那么现在仅剩下仅有左右接口或仅有上下接口的情况。两种情况本质上是一样的(旋转 $90^\circ$ 即可相互转化),因此我们只考虑仅有左右接口的情况。

首先可以做一个转化:$k$ 阶分形图中连通块数等于 # 的数量减去左右相邻的 # 的数量。

设 $V_i$ 表示 $i$ 阶分形图中的 # 数,$E_i$ 表示 $i$ 阶分形图中左右相邻的 # 的数量,$a$ 为原图中左右接口的数量,可以得到

$$ \begin{aligned} V_i&=V_{i-1}\times c\\ E_i&=E_{i-1}\times c+E_{i-1}\times a\\ \end{aligned} $$

$V_i$ 的递推式不难理解。$E_i$ 实际上分为两部分:$i-1$ 阶分形图内部产生的贡献,以及边界上产生的贡献。第一部分贡献不难计算,第二部分是因为每对左右相邻的 # 都会产生 $a$ 个左右相邻的 #

发现这个东西可以矩阵快速幂计算。设 $b$ 为原图中左右相邻的 # 的数量,则

$$ \begin{bmatrix}c&b\\0&a\end{bmatrix}^{k-1} $$

的第一行第一列为 $V_k$,第一行第二列为 $E_k$。于是即可得到答案 $V_k-E_k$。

代码

最后修改:2020 年 01 月 11 日 08 : 45 PM