\(\mathcal{Preface}\)

分數 \(50+100+40+100=290\)，甚至比去年低 \(15\) 分，有點受不了了。

A 題代碼上掛了 \(50\) 分，C 題思維上掛了 \(60\) 分。
簡稱：掛了 \(50\) 分，還“掛了”\(60\) 分。

掛的最猛烈的一次。挺憤怒的。

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

Tag：暴力枚舉。

水題，算出總和 \(sum\)，然后枚舉每個 \(i\) 算出當讓 \(a_i\) 異或上 \(k\) 情況下的答案 \(sum - a_i + a_i \oplus k\)，全部的取 \(\max\) 即可。

但是這里有一個坑點——也許只有我這么糖——異或的優先級是很低的。也許之前用得少，大多也是用在狀壓里，不會出現多種符號所以沒有管過優先級，不過總之這里一定不能寫 sum-a[i]+a[i]^k，乍一看沒問題但異或的優先級沒加減法高，所以這里會直接轉化為 (sum-a[i]+a[i])^k……一臉懵。總之之后長個心眼，注意位運算優先級。

upd：What？不是哥們別嚇我，按位或、與和異或的優先級還沒左移右移高？我死了，原來我學 OI 這么久了才知道原來它們優先級這么低？我怕是成井底之蛙了——對我就是井底之蛙！

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

Tag：暴力枚舉，模擬 / 貪心，高精度比較。

可以暴力枚舉第一種操作執行多少次（因為最多執行 \(9\) 次，第 \(10\) 次的時候就轉回來了，沒必要）以及第二種操作在哪個位置執行，然后挨個算出數，高精度比較，求 \(\max\)。

但是賽時腦抽沒想到這么水的做法，直接貪心上了。

只要高位高，低位再低也無所謂。因此肯定要求高位為 \(9\)。

高位為 \(9\)，有且僅有兩種方案，一種是使用第一種操作將最高位調成 \(9\) 然后再在后面調一個位置做第二種操作，還有一種是使用第一種操作將最高位調成 \(8\)，然后再使用第二種操作把最高位弄回 \(9\)。

兩種方案取 \(\max\) 即可，同樣的，高精度比較。

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

Tag：簡單思維推導，DP，調和級數，二分。

我暈。我賽時代碼只要 DP 順序反個邊，查詢的時候再加個二分就成功 \(40 \to 100\) 了。這還玩得下去？

易知有一個式子，$ \lfloor \frac {\lfloor \frac{k}{x} \rfloor} {y} \rfloor = \lfloor \frac{k}{x \times y} \rfloor $，也就是向下取整這玩意兒存在結合律。

那么只要找到最小的 \(p\) 使得 \(\lfloor \frac{x}{p} \rfloor \le y\)，就只需要判斷如何用最小代價湊出 \(p\) 這個數了。

首先對 \(a\) 取后綴 \(\min\)：因為如果可以用 \(2\) 的代價 \(\div 3\)，絕不會有人傻傻用 \(3\) 的代價 \(\div 2\)。

然后定義 \(dp_x\) 表示要湊出 \(x\) 最少需要多少的代價，最初有 \(dp_x = \infty\) 卻 \(dp_1 = 0\)。

接著我們枚舉 \(x\)，范圍 \(2 \sim 10^5\)，那么下一步就是看如何用 \(dp_x\) 去更新其他 DP 值了。容易想到枚舉 \(i\)，范圍 \(2 \sim n\)（為什么不是 \(1 \sim n\)？因為絕不會有人花錢去做無用功），不過有一點需要保證，那就是必須得滿足 \(x \times i \le 10^5\)，不然超出了范圍，也就更不可能查詢這個位置了。

然后……你以為時間復雜度是 \(O(n^2)\) 的？如果你這么想，你就大錯特錯了！因為 \(i\) 必須要 \(\le \frac{10^5}{x}\)，這是什么？對極了！調和級數！所以時間復雜度其實是 \(O(n \log n)\) 的……然后你就這么水靈靈的過了。

注意找 \(p\) 的那會兒需要用二分。

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

Tag：思維，枚舉，排序，區間并集（？）。

考慮標定 \(l\)，尋找有多少個滿足條件的 \(r\)。

不難發現，\(r\) 可取的區間，其實就是所有字母在 \(l\) 往后的后綴中出現的第一次到第二次之間的這段區間；換言之，將所有字母編碼為 \(1 \sim 26\)，編碼為 \(i\) 的字符在 \(l\) 往后的后綴中出現的第一次和第二次的位置分別是 \(a_i\) 和 \(b_i\)，那么 \(r\) 可取的范圍就是 \([a_1,b_1] \cup [a_2,b_2] \cup \dots \cup [a_{25},b_{25}] \cup [a_{26},b_{26}]\)。

這些區間很好找，一開始記錄下就行，但問題在于如何計算并集？可以考慮把所有區間信息存進 pair 里從小到大排序，然后一個個計算，注意不要和之前的區間重合即可。

注意這題挺卡人的——至少我這么認為——不能開數組維護字母信息！要用 vector——不能二分找字母！只能用指針掃——總之我覺得是挺卡人的，幸好我卡過了。

\(\mathcal{Summary}\)

A 題掛分太可惜，之后一定要注意；
位運算的優先級，高高低低要分清。

B 題貪心沒失分，可惜沒有打暴力；
D 題卡人過于猛，幸好卡過無影響。

C 題暴力已全出，只要最后小思維；
沒能拿滿挺可惜，幸好暴力沒丟分。

A 題源于小輕敵，小小思維掛 C 題；
其實這場能 AK，只因小錯掛全場……

行吧，那就記個教訓吧。