AtCoder AGC047 總結(jié)

A

由于小數(shù)位最多九位，我們先乘 \(10^9\)，轉(zhuǎn)化為求 \(10^{18}\mid a_ia_j\) 的個(gè)數(shù)。

考慮分解質(zhì)因數(shù)，要求 \(2,5\) 的次數(shù)都至少為 \(18\) 即可。時(shí)間 \(18^2\times n\)。

B

一個(gè)串可以變成的串形如，選一個(gè)字符，再選一個(gè)后綴拼起來。

對(duì)反串建 Trie，只需求子樹內(nèi)包含某個(gè)字符的串有多少個(gè)。

復(fù)雜度 \(O(\sum s_i\times 字符集大小)\)。

C

由于 \(P\) 給定且是質(zhì)數(shù)，考慮其原根（原根為 \(2\)），將 \(a_i\) 表示為 \(a_i=2^{x_i}\)。

乘法轉(zhuǎn)化為指數(shù)相加，枚舉 \(a_i\times a_j=2^{k}\)，我們現(xiàn)在要求 \(\sum [x_i+x_j=k]\)，F(xiàn)FT 即可。

D

相當(dāng)于兩棵樹上的 dist 相乘。套路地，考慮對(duì)一棵樹點(diǎn)分治，另一棵樹建虛樹。

在本題里由于是二叉樹，所以實(shí)際上是枚舉一棵樹上的 LCA，建虛樹葉可以不用建，暴力跳父親即可。

復(fù)雜度 \(O(n\log ^2n)\)。

E

首先 \(A,B\le 10\) 的情況，相當(dāng)于枚舉 \(i,j\) 計(jì)算 \([i\le A\land j\le B]\) 的和。\(A_3<A_{0}+A_{1}\) 即可得到 \(1\)。而那個(gè)表達(dá)式等價(jià)于 \(1<[j\le A]+[j\le B]\)。

正解考慮拆分二進(jìn)制位，那么對(duì)于 \(A_0\) 的第 \(i\) 位和 \(A_1\) 的第 \(j\) 位，若都為 \(1\)，則貢獻(xiàn) \(2^{i+j}\)。處理 \(2\) 的冪與位移是容易的，而前面的條件同上可以轉(zhuǎn)化為 \((1<A_0[i]+A_1[j])^{i+j}\)。

考慮怎么拆分二進(jìn)制位，可以從大到小枚舉位，若 \(x\ge 2^i\) 則將 \(x\gets x-2^i\)，這樣可以得到所有二進(jìn)制位。

考慮怎么減法，對(duì)于 \(x-y\)，考慮從大到小枚舉位，若 \(x\le y+2^i\) 則差中存在 \(2^i\)，并令 \(y\gets y+2^i\)。

實(shí)現(xiàn)時(shí)，可以實(shí)現(xiàn)若干個(gè)函數(shù)，傳入運(yùn)算數(shù)下標(biāo)，返回結(jié)果的新下標(biāo)。

F

\(O(n^2)\)

答案的貢獻(xiàn)是相鄰點(diǎn)的曼哈頓距離減去【點(diǎn)數(shù)減一】。

能到達(dá)的點(diǎn)在 \(x\) 和 \(y\) 上都是一段區(qū)間。那么排序后可以設(shè) \(O(n^2)\) 的 DP：\(f_{l,r,0/1}\)，\(0/1\) 表示當(dāng)前在區(qū)間左端點(diǎn)還是右端點(diǎn)。轉(zhuǎn)移時(shí)需要看 \(\mid y_{l-1}-\max/min \{y_{l\dots r}\} \mid\) 是否等于 \(1\)，這里 \(y\) 為離散化后的值。

\(y_i=i\)

答案為 \(dis(1,n)+\min(dis(1,i),dis(i,n))\)。

正解

\(y_i=i\) 的情況啟發(fā)我們，對(duì)于 \(|y_i-y_{i+1}|=1\) 的連續(xù)段可以一起轉(zhuǎn)移。此時(shí)合法的區(qū)間只有 \(O(n)\) 個(gè)。

這是因?yàn)槿缦聢D給連續(xù)段分層，那么在同一個(gè)極大矩形中，合法的區(qū)間的左右端點(diǎn)一定在同一層或者相同層里，而層數(shù)是 \(O(n)\)，因此合法區(qū)間數(shù)是 \(O(n)\) 的。而對(duì)于一個(gè)連續(xù)段同時(shí)處于多個(gè)極大矩形里的情況，發(fā)現(xiàn)它只會(huì)存在于最多兩個(gè)極大矩形。

用 std::map 保存狀態(tài)可以做到 \(O(n\log n)\)。