初賽初賽~~~~~

板刷 CF

CF2135B *1700

做一做人類智慧。

想到的：應該是通過與一些特殊的錨點進行計算，然后得到機器人的初始坐標。能否讓機器人先一直往上走，然后這樣就可以得到它與最高的那個錨點的曼哈頓距離，然后再讓它一直往右走，得到它與最右邊的那個錨點的曼哈頓距離，最后通過一些計算得到初始坐標？

待續……

CF1935D *1800

想到的：可以淺推一下式子嗎？即設 \(x+y=c_i\)，則 \(c_i-x=y\)；\(y-x=c_i\)，則 \(x+c_i=y\)。也就是說我們只需要找出這兩種可能的數對 \((x,y)\)，然后用總數減掉這些數量即可。那會有同時滿足：\(x+y=c_i\) 和 \(y-x=c_i\) 的嗎？當 \(x=0,y=c_i\) 時才會出現，所以最后加上 \(n\) 即可。如果有 \(x+y=c_i\)，\(y-x=c_j\) 的情況出現呢？\(x=(s_i-s_j)\div 2\)，\(y=(s_i+s_j)\div 2\)。那我們只需要把原來的所有的不滿足題意的數對求出來，然后容斥一下就結束了？感覺還有一些細節。

待續……

分治

CF2146D2 *2000

想到的：首先貪心的考慮，對于兩個數 \(x\) 和 \(y\)，必然是當 \(x\) 或 \(y\) 后二進制里全為 \(1\) 是最優的，在下文中我們稱其為互補。

對于一段區間 \([l, r]\)，在去除二進制中相同的高位后，必然可以被劃分成兩個區間 \([l, pos]\) 與 \((pos, r]\)，其中第一個區間中的數在二進制表示下的最高位為 \(0\)，第二個區間中的數在二進制表示下的最高位為 \(1\)。此時，不妨令 \(pos - l + 1 \ge r - pos\)。在這種情況下，\((pos, r]\) 這段區間中的數一定可以與第一個區間中進行互補匹配，于是將匹配的數計算進答案，然后令 \(r\leftarrow 2\times pos - r\)，將區間右邊界縮小。若 \(pos - l + 1 < r - pos\)，則令 \(l\leftarrow 2\times pos - l + 2\)。

沒想到的：寫法稍顯復雜。

ds

CF2137F *1900

想到的：數數題。考慮一段區間中怎樣必須把 \(z_i\) 賦值成 \(x_i\)。顯然，當 \(x_i>\max(x_l,x_{l+1},\cdots ,x_{i-1})\) 時要把 \(z_i\) 賦值成 \(x_i\)。所以就是要找到一個數的左邊的第一個大于等于它的數，然后用這段長度（不包含比它大的數）乘上 \(x_i\) 即可，不過 \(x_i\neq y_i\)。直接單調棧就行了吧？不對，還有一些很大的問題。因為要前綴最大值相同，但如果在 \(y_i>\max(x_1,x_2,\cdots, x_i)\) 情況下，這是非法的。所以再直接 \(\operatorname{ST}\) 二分找一下第一個滿足 \(x_j>y_i\) 的 \(j\) 即可。\(j\) 的范圍是 \(1\sim 單調棧所找到的位置\)（就當是 ds 題了）。

沒想到的：無。

圖論

CF1915G *1800

最短路跳到的題目。

想到的：貪心的考慮，每次一定會用現有的最快的自行車。同時，注意到 \(n\le 1000\) 這啟發我們用 \(n^2\) 的狀態。 設 \(dis_{i, j}\) 表示走到點 \(i\) 且此時最快的單車的速度為 \(j\) 的最小時長。

沒想到的：無。

CF1383A *1700

想到的：注意到每次只能把字母往大的改，所以無解很好判。然后考慮統計極長連續子串的個數，即為答案。怎么假了？c，原來是選擇子序列……難不成是圖論建模？

沒想到的：注意到可以把每個字母與其要變成的字母之間連一條邊，那么原圖必為 DAG，所以任意一顆生成樹便能滿足條件。并差集即可。

CF2135C *2000

這題在賽時聽到了一點思路？不過并不影響……

想到的：注意到樣例給的都有環，所以考慮在環上的點的性質。注意到環上的點必須相等，且奇環上的點一定要為 \(0\)。此時考慮算出邊雙，然后對于每個邊雙進行 dfs 統計答案。代碼實現好復雜啊！

CF2137G *2200

想到的：\(\operatorname{DAG}\) 上的博弈論，為什么都說比 F 簡單？

沒想到的：第一次做類似的題，需要考慮在先手取和后手取的先手必敗或先手必勝狀態。即 \(f_{i,0}\) 表示先手取的狀態，\(f_{i,1}\) 表示后手取的狀態，轉移如下：

• \(f_{u,0}=\operatorname{OR}_{v\in G_u}\{f_{v, 1}\}\)
• \(f_{u,1}=\operatorname{AND}_{v\in G_u}\{f_{v, 0}\}\)

然后，每次把節點染成紅色就相當于把 \(f_{u,0}\) 和 \(f_{u,1}\) 都賦值成 \(0\)。最后注意到每個點只會被染色一次，沒了。

dp

CF2143D1 *1800

想到的：注意到一個性質，只有在選出來的序列中的最長下降子序列的長度 \(\le 2\) 時才合法。考慮枚舉開頭的點，然后進行 dp 轉移。狀態可以這樣設計：\(f_{i,j}\) 表示以 \(i\) 結尾，且最長下降子序列為 \(j\) 的序列個數。

不一定是 dp 啊。似乎可以直接暴力枚舉下降的子序列中的數，然后找到所有比子序列中最大的數大的數的數量，設其為 \(x\)，則貢獻加上 \(2^x\)。仍有一些問題，考慮枚舉兩個位置 \(i\) 和 \(j\)，并且有 \(a_i>a_j\)。然后找到 \(i\) 之前的數中有多少個比 \(a_i\) 小的，找到在 \((i, j)\) 之中有多少個比 \(a_i\) 大的，找到在 \(j\) 之后中有多少個比 \(a_j\) 大的。設其總和為 \(x\)，\(ans\leftarrow ans + 2^x\)。不對，這樣有可能會不合法，枚舉完 \(i\)，\(j\) 后直接對于三個段暴力 dp，但這樣是 \(n^4\) 的，跑不過去啊啊啊啊啊啊啊啊！ 還要去個重……

沒想到的：什么？三維 dp？\(f_{i,j,k}\) 表示在 \(1\sim i\) 中有全局最大值為 \(j\) 且此時二元組第二個最大為 \(k\)。（真的要全局最大值啊）……

CF1225E *2200

模擬賽賽題，寫的比較糖……

想到的：亂 dp，直接前綴和+二分優化。

沒想到的：注意到一條路徑一定有很多個拐點，所以考慮從每個拐點向該行或列最后一個可以走到的點進行轉移（這東西賽時想到了的），這可以差分優化一下。然后判斷最后一個點直接前綴和即可。因為每個點都可以從上面或右邊走過來，所以狀態定義為：\(f_{i,j,0/1}\)。

CF1935C *1800

想到的：感覺可以 dp，但要優化。設 \(f_{i,j}\) 表示 dp 到第 \(i\) 個數且第 \(i\) 個數是現在集合里的第 \(j\) 個數的最小花費。發現不好轉移。難不成只能貪心了？看了一下 tag，還真是前綴和優化 dp……等會，是不是可以先排序，然后就不用考慮需要在中間轉移的情況了。可以以 \(b_i\) 為關鍵字從小到大排序，然后轉移方程就變成了：

把和 \(k\) 有關的東西提出來，得到：

所以每次轉移只需要維護一下長度為 \(j-1\) 的集合的最小值即可。按順序轉移，還是很妙的。

沒想到的：就排序那一步是看了一下 hint……

數學

CF2137E *1500

想到的：沒什么好說的，純純無聊分討題，corner cases！！！

CF2140C *1500

想到的：類似這樣操作的題目一般都有一個 trick 就是在同一種狀態最優狀態下不斷重復拉扯。但這題有一個問題就是如果不斷拉扯那么 \(f(a)\) 與 \(cost\) 有關，所以要盡量早的結束。于是問題轉換為在 Alice 進行第一次操作后的 \(f(a)_{max}\)。 考慮 Alice 的操作方式。如果 Alive 目前的序列是最優解，那么選擇兩個最遠的且下標奇偶性相同的數交換。有兩個式子：

• \(a_r-a_l+r-l=(a_r+r)-(a_l+l)\)
• \(a_l-a_r+r-l = (a_l-l)-(a_r-r)\)

所以只要分前后兩邊掃，然后分別算出這兩個式子的最大值即可。為什么 WA on test 3？改一下式子：

• \(2\times a_r-2\times a_l+r-l\)
• \(2\times a_l-2\times a_r+r-l\)

求這個最值就行了。

板刷 luogu

P12684 \(\color{green}綠\)

想到的：第一眼注意到這東西好像是有單調性的？然后可以 bfs 一次求出最少的使用步數。并不具備單調性，而且 \(5000\times 5000\) 很大啊。

沒想到的：第一次直接 01bfs 優化即可，然后第二次的轉移條件相當于加了一個一定要是最短路上的邊進行轉移，然后再跑一邊 01bfs 就行了……

P6005 \(\color{green}綠\)

想到的：類似 dp 之類東西？設 \(f_{i, j}\) 表示第 \(i\) 天走到 \(j\) 能獲得的最大價值。有轉移如下：

沒想到的：狀態設計看了一眼題解。

模擬賽

26

a

思路：對于開頭的長度為 \(k\) 的序列，我們發現可以用它把后面的 \(n-k\) 位都改變，同理，我們如果使用后 \(k\) 那么我們可以把所有的前面的 \(n-k\) 位都改變。所以如果前 \(k\) 和后 \(k\) 都沒有交集，那么必然每一個位置都可以被改變，如果有交集呢？那么交集中的部分不管怎么改，兩兩之間的相對情況都不會改變，所以交集必須全部相同。此時，問題便轉換成了求中間的最長的相同的子串。

b

思路：注意到 \(k\le 1000\)，所以可以對于左下角的點枚舉其所在 \(k\times k\) 的方格中的位置，然后判斷其它點的位置。但這樣的復雜度是 \(O(n\times k^2)\) 的，顯然會 TLE，怎么優化呢？考慮一個轉化，那就是可以對于每個 \(x\) 和 \(y\) 都對 \(2\times k\) 取模，然后把白色的點的坐標改成 \((x+k, y)\)，這樣就變成了黑點。此時，我們枚舉左下角的點可能在的 \(2k\times 2k\) 中位置，然后用二維前綴和取統計一下就行了。細節稍多。

c

思路：貪心的考慮，讓最外端的字符進行匹配，這樣一定不劣，然后每次匹配完一對字符后邊可將其刪除，即不用再考慮它們了。然后就是怎樣維護每次操作后剩下的字符的位置，發現每次將 \(s_i\) 移動到末尾 \(n\)，那么只需要知道 \(i\sim n\) 中有多少個字符即可，這可以使用線段樹維護，每次匹配完一對字符后就把它們賦值成 \(0\)。唯一要注意的是單獨一個字母在回文串中間的情況，這樣后面的所有步驟都需要加一。

d

思路：沒什么好講的，狀壓板子。