ABC196 题解

[toc]

AC代码

A – Difference Max

B – Round Down

C – Doubled

给定一个正整数 $N$ ，询问 $N$ 以内有几个对偶正整数。

一个数被称为是对偶的当且仅当：

这个数长度是偶数；

这个数前一半等于后一半，例如 $123123$ 。

$N\leq 10^{12}$ 。

因为这个数是对偶的，因此我们可以暴力枚举前一半，然后算出整个数并判断是否 $\leq N$ ，复杂度 $O(\sqrt{n})$ 。

D – Hanjo

给定一个 $H\times W$ 的网格图，有两种不同尺寸的榻榻米，第一种尺寸为 $1\times 2$ 有 $A$ 个（可以旋转为 $2\times 1$ ）；第二种尺寸为 $1\times 1$ ，有 $B$ 个。询问有几种不同的摆放方式使得榻榻米恰好铺满了网格图。

$HW\leq 16,2A+B=HW$ 。

数据范围极小，直接暴搜！

注意到 $1\times 2$ 的榻榻米本质上可以看作在网格图中选择一条分隔边，而 $H\times W$ 的网格图中最多也只有 $24$ 条（$4\times 4$），同时 $A_{\max}=8$ ，因此可以写出一个复杂度为 $O(24\times \binom{24}{8})$ 的搜索。

E – Filters

给定两个长度均为 $N$ 的序列 $A=(a_1, a_2, \dots, a_N),T=(t_1, t_2, \dots, t_N)$ 和一个长度为 $Q$ 的序列 $X=(x_1, x_2, \dots, x_N)$。定义函数 $f_i(x)$ 为：
$f_i(x) = \begin{cases} x + a_i & (t_i = 1)\\ \max(x, a_i) & (t_i = 2)\\ \min(x, a_i) & (t_i = 3)\\ \end{cases}$
对于每个 $x_i$ 求出 $f_N( \dots f_2(f_1(x_i)) \dots )$ 的值。

$2\leq N,Q\leq 2\times10^5,|a_i|,|x_i|\leq 10^9$ 。

观察函数 $f(x)$ 三种操作的特性后发现：

操作一实际上就是垂直方向上偏移 $a_i$ 个单位；
操作二可以视为一个二极管，$x$ 想要通过就必须 $\geq a_i$ ，否则会被强制拉成 $a_i$ ；
操作三同理，$x$ 想要通过就必须 $\leq a_i$ ，否则会被强制拉成 $a_i$ ；

因此，该函数最终的图像一定表现为下图的形式：

中间那段函数显然是 $y=x+k$ 因此，只需要找到两个发生变化的分界点即可解决本题。这两个分界点可以二分搜索也可以直接线性模拟得到。

F – Substring 2

给定两个 $01$ 串 $S,T$ ，询问最少修改 $T$ 串中几个字符才能让 $T$ 变成 $S$ 的一个子串。

$10^6\geq|S|\geq|T|$ 。

FFT做字符串匹配的经典应用，直接套用这篇文章的内容就行。