AtCoder Beginner Contest 196 個(gè)人題解

2021-03-20 22:57 作者:俊杰_Charles 0人讀過(guò) | 我要投稿

比賽鏈接：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

題意：高精度小數(shù)取整。

題解：把小數(shù)點(diǎn)前的內(nèi)容輸出即可。

C. Doubled

題意： $1$ 到 $n$ 中有多少整數(shù)，它的位數(shù)為偶數(shù)，且前半部分和后半部分相同。

題解：枚舉前半部分即可。

D.?Hanjo

題意：有一個(gè)? $n$ 行? $m$ 列的方格圖，用? $a$ 個(gè)? $1%5Ctimes2$ 的矩形和? $b$ 個(gè)? $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$ ，詢問(wèn) $q$ 個(gè) $x$ ，求出 $f_n(%5Cdots%20f_2(f_1(x))%5Cdots)$ 。

題解：吉司機(jī)線段樹(shù)沖沖沖。時(shí)間復(fù)雜度 $O((n%2Bq)%5Clog%20q)$ 。

F. Substring 2

題意：給定兩個(gè)? $01$ 串? $s$ 和 $t$ ，求至少改變? $t$ 中的多少位，使得? $t$ 成為? $s$ 的一個(gè)子串。

題解：題目可以轉(zhuǎn)化為用? $t$ 對(duì)? $s$ 進(jìn)行字符串匹配，求最少失配位數(shù)。樸素做法時(shí)間復(fù)雜度為 $O(n%5E2)$ ，無(wú)法通過(guò)此題，需要使用多項(xiàng)式算法進(jìn)行優(yōu)化。令 $f(i)%3D%5Csum_%7Bk%3D0%7D%5E%7Bm-1%7D(s_%7Bi%2Bk%7D-t_k)%5E2$ ，表示從? $s$ 串的第? $i$ 位開(kāi)始對(duì)? $t$ 進(jìn)行匹配的失配位數(shù)。式子可化為 $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$ ，前兩項(xiàng)可以預(yù)處理得到，而最后一項(xiàng)需利用多項(xiàng)式算法進(jìn)行計(jì)算。若我們將 t 串反轉(zhuǎn)，則原式變?yōu)? $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$ ，最后一項(xiàng)便是經(jīng)典的卷積形式，使用 FFT 或 NTT 算法即可得到結(jié)果，時(shí)間復(fù)雜度 $O(n%5Clog%20n)$ 。