\(\mathcal{Preface}\)

分數(shù) \(100+100+100+25=325\)。

菜死了。

\(\mathcal{Problem \space{} A}\)

Tag：循環(huán)，暴力枚舉。

送分題，由于 \(1 \le l \le r \le 3000\) 且 \(1 \le nn \le 3000\)，由此可知平方級別的時間復雜度是完全可以接受的，因此直接枚舉除數(shù) \(k\) 然后挨個算出值取 \(\min\) 就好了，注意如果有相同的取最小一個。

\(\mathcal{Problem \space{} B}\)

Tag：因數(shù)，循環(huán)。

定 \(ans=10^{k}\)，然后看看，\(n\) 中有 \(x\) 個 \(2\) 的因子，就讓 \(ans \to ans \div 2^x\)，有 \(y\) 個 \(5\) 的因子，又讓 \(ans \to ans \div 5^y\)，最終的 \(ans\) 便是答案。

\(\mathcal{Problem \space{} C}\)

Tag：完全二叉樹的性質(zhì)，二叉樹。

記錄以每個點為根的子樹包含的字母的情況。

如果這個包含字母情況中，只有至多 \(1\) 種字母的數(shù)量為奇數(shù)，才可以形成回文。

一開始先預處理最初的情況，算出答案輸出。

然后考慮修改的情況，如果節(jié)點 \(u\) 上的字母被改動了，受影響的子樹只有以自己的祖先節(jié)點為根的子樹才會受到影響（自己以及父親算作特殊的祖先）。而又由于題目給定的是一棵完全二叉樹，因此深度只有 \(\log n\)，暴力修改沒有問題。

先判斷之前有沒有，之前有的話先讓答案減一，然后再看改變之后有沒有，改變之后有的話就讓答案加一。

\(\mathcal{Problem \space{} D}\)

Tag：構(gòu)造，思維，逆序?qū)Α?/p>

好神的題目，好神的做法！

由于要求逆序?qū)晚樞驅(qū)Φ臄?shù)量相同，不難算出逆序?qū)晚樞驅(qū)Φ臄?shù)量都是 \(\frac{n \times (n-1)}{4}\)?？梢韵茸?\(sum = \frac{n \times (n-1)}{4}\)。

首先考慮構(gòu)造足夠的順序?qū)?。如果在序列前面放進一個 \(1\)，那么會貢獻 \(n-1\) 個順序?qū)Γ粫霈F(xiàn)逆序?qū)?；如果接著放進一個 \(2\)，那么又會再貢獻 \(n-2\) 個順序?qū)?，同樣不會出現(xiàn)逆序?qū)Γ灰源祟愅疲绻樦鴣淼脑?，放一個 \(x\)，就會貢獻 \(n-x\) 個順序?qū)Α?/p>

那么考慮依次枚舉 \(i\) 從 \(1\) 到 \(n\)，如果當前的順序?qū)?shù)量 \(cnt\) 加上這一輪新加的 \(n-i\) 個之后還沒有夠到 \(sum\)，也就是說當 \(cnt+(n-i) < sum\) 的情況下，直接讓 \(a_i = i\)，標記 \(i\) 數(shù)字已經(jīng)填寫，然后讓 \(cnt \to cnt+(n-i)\)。但是如果超過了，就要往后找到一個恰好的 \(x\)，使得 \(cnt + (n-x) = sum\)，并讓 \(a_i = x\)，標記 \(x\) 已經(jīng)填寫；標記完了之后，順序?qū)Φ臄?shù)量也就已經(jīng)達標了，這個時候只要填入足夠多的逆序?qū)涂梢粤耍芎唵?，把還剩下沒填的數(shù)字全部倒序挨個填進 \(a\) 里就行了。

最后輸出即可，代碼很簡單。

\(\mathcal{Summary}\)

T4 的構(gòu)造方法確實挺厲害的，構(gòu)造也確實不是強項，之后繼續(xù)加油吧。正好又多知道一個構(gòu)造的方法了，不斷累積經(jīng)驗肯定也是有幫助的！