AtCoder Beginner Contest 196 个人题解

2021-03-20 22:57 作者:俊杰_Charles 0人读过 | 我要投稿

比赛链接：https://atcoder.jp/contests/abc196

官方题解：https://atcoder.jp/contests/abc196/editorial

A. Difference Max

题意： $a%20%5Cle%20x%20%5Cle%20b$ ， $c%20%5Cle%20y%20%5Cle%20d$ ，求 $x-y$ 的最大值。

题解： $(x-y)_%5Cmax%3Db-c$

B. Round Down

题意：高精度小数取整。

题解：把小数点前的内容输出即可。

C. Doubled

题意： $1$ 到 $n$ 中有多少整数，它的位数为偶数，且前半部分和后半部分相同。

题解：枚举前半部分即可。

D. Hanjo

题意：有一个 $n$ 行 $m$ 列的方格图，用 $a$ 个 $1%5Ctimes2$ 的矩形和 $b$ 个 $1%5Ctimes1$ 的矩形将其铺满，求有多少种不同的铺法。

题解：爆搜。

E. Filters

题意： $f_i(x)%3D%5Cbegin%7Bcases%7D%0Ax%2Ba_i%2C%20%26%20t_i%3D1%20%5C%5C%0A%5Cmax(x%2Ca_i)%2C%20%26%20t_i%3D2%20%5C%5C%0A%5Cmin(x%2Ca_i)%2C%20%26%20t_i%3D3%0A%5Cend%7Bcases%7D$ ，给定 $a_1%2Ca_2%2C%5Cdots%2Ca_n$ 和 $t_1%2Ct_2%2C%5Cdots%2Ct_n$ ，询问 $q$ 个 $x$ ，求出 $f_n(%5Cdots%20f_2(f_1(x))%5Cdots)$ 。

题解：吉司机线段树冲冲冲。时间复杂度 $O((n%2Bq)%5Clog%20q)$ 。

F. Substring 2

题意：给定两个 $01$ 串 $s$ 和 $t$ ，求至少改变 $t$ 中的多少位，使得 $t$ 成为 $s$ 的一个子串。

题解：题目可以转化为用 $t$ 对 $s$ 进行字符串匹配，求最少失配位数。朴素做法时间复杂度为 $O(n%5E2)$ ，无法通过此题，需要使用多项式算法进行优化。令 $f(i)%3D%5Csum_%7Bk%3D0%7D%5E%7Bm-1%7D(s_%7Bi%2Bk%7D-t_k)%5E2$ ，表示从 $s$ 串的第 $i$ 位开始对 $t$ 进行匹配的失配位数。式子可化为 $f(i)%3D%5Csum_%7Bk%3D0%7D%5E%7Bm-1%7Ds_%7Bi%2Bk%7D%5E2%2B%5Csum_%7Bk%3D0%7D%5E%7Bm-1%7Dt_k%5E2-2%5Csum_%7Bk%3D0%7D%5E%7Bm-1%7Ds_%7Bi%2Bk%7Dt_k$ ，前两项可以预处理得到，而最后一项需利用多项式算法进行计算。若我们将 t 串反转，则原式变为 $f(i)%3D%5Csum_%7Bk%3D0%7D%5E%7Bm-1%7Ds_%7Bi%2Bk%7D%5E2%2B%5Csum_%7Bk%3D0%7D%5E%7Bm-1%7Dt_k%5E2-2%5Csum_%7Bk%3D0%7D%5E%7Bm-1%7Ds_%7Bi%2Bk%7Dt_%7Bm-1-k%7D$ ，最后一项便是经典的卷积形式，使用 FFT 或 NTT 算法即可得到结果，时间复杂度 $O(n%5Clog%20n)$ 。