題目梗概

給的都是 VJ 的鏈接，帶翻譯。

賽時情況

習慣了，先把所有題目讀一遍。

A 題看起來是模擬，\(n\) 又那么?。籅 是構造，哇我完蛋了我構造特弱；然后看了 C，看著像是 DP 什么的，不過樣例好奇妙，答案都那么小（伏筆?。?；D 是什么鬼，還整上交互了；E 是博弈，好難好難好難的樣子；至于 F，我什么都不知道呢。

做 A。寫完代碼以后測了一下 \(n=500\)，是 \(998\)。啊那沒事了就算全部模擬一遍也過得去。

不想管了，開 B！噼里啪啦瞎搖了一通，似乎想到了一種神秘的構造方法，隨便試了幾個，都能過去。然后分析了一會兒無解情況，于是開寫。樣例沒毛病，目光掃視代碼幾遍以后直接跳了。

C 啟動，想了一陣子 DP，發(fā)現(xiàn)自己死挺慘的，什么也玩不出來。然后開始觀察樣例，發(fā)現(xiàn)一些神秘的性質(zhì)！然后發(fā)現(xiàn)答案最大 \(2\)（呼應伏筆 qwq）。死鬼 CF，還說要對什么 \(676767677\) 取模呢，真好笑。然后開始寫，結果樣例全輸出 \(0\)，不解的我把差分數(shù)組打出來一看——怎么都少 \(1\)？看了一遍題，哦我忘了算上 \(i\) 自己。弄完以后，過樣例，不想管了開 D。

交互交互交互交互。好難好難好難好難。瞎整了一些東西，發(fā)現(xiàn)疑似可以分塊（？什么破思路），于是決定把這 \(n\) 個電池分成 \(n\) 組，然后每次不斷合并，然后查一個組內(nèi)的情況。雖然很獵奇，但是淺淺算了一下，好像次數(shù)夠，于是就開寫了。代碼比思路更獵奇，中途還寫錯了一些，不過還好在寫的同時給找出來了。

開測樣例，次數(shù)啥的都沒問題，只是覺得自己的代碼好傻，反復問兩個同樣的電池。思考如何解決這個問題。突然想到 \(n\) 只有 \(40\) 來著！噢，那隨便弄都行，開了個二維 bool 數(shù)組 \(vis\)，\(vis_{x,y}\) 存 \((x,y)\) 這對組合問沒問過。然后又試了一下，嗯，現(xiàn)在聰明多了。

覺得這個 D 好不保險的樣子啊，隨便編了幾組東西測了測，次數(shù)都少好多，不想測了。

然后開了 E，想了好一會，不知道怎么處理這個什么最優(yōu)策略。好難啊，好難啊，根本沒有一點思路。瞎搖了一些東西，但是始終不知道怎么弄。話說這個矩陣還變來變?nèi)サ奶y整了！更何況 \(n\) 和 \(m\) 的總和還沒有限制，好難！研究了一下，想用平常的博弈 DP 的思路去解決，問題在于這個狀態(tài)吧……根本不知道怎么設啊喂！神秘死了，被氣死了，不想 E 了。

意料之中，意料之中，我怎么可能做得出來 Div.2 的 E 呢（喂喂喂你不能這么說）？F 就更不可能了，但是無聊的我還是想去看一下。想了想，毫無思路，只是覺得百分百要上 LCA，但其他就什么都不知道了。搖了搖樣例，沒有任何頭緒。

看了看時間，四點四十了，那最后留點時間檢查下前面的代碼吧。五點交卷，后面還有點時間看下沒 A 的題是怎么回事，以及看一下后兩題咋做。題今天下午肯定沒時間補的，之后抽時間嘛，周末有一大把的時間??！我又考不了今年的 CSP。

誒誒，怎么扯了這么多廢話，于是開始檢查前面的題，測了下樣例，然后大眼瞪法檢查代碼，沒查出什么毛病。又玩了一下 D 的代碼，真好玩呀真好玩。（D 題代碼：不是我好端端一個代碼怎么被你玩得跟個游戲似的？我有那么好玩嗎？）

又看了下時間，四點五十二了，準備交卷。打開 CF，登上號，提交！提交！提交！提交！

分數(shù)分布

A B C D 全過，很開心。

賽后題解

A

話不多說，直接模擬即可，用 \(x\) 和 \(y\) 存一下當前勝者組和敗者組的隊伍數(shù)，按著它的套路算就行。注意計算順序，不行就多開點臨時變量。然后記得最后答案要 \(+1\) 因為還有最后一個總決賽。

B

簡單構造題。

首先考慮從上到下從左往右造 \(k\) 個向上 U 的格子，這樣這 \(k\) 個肯定出不去。

然后考慮如何讓剩下 \(n^2 - k\) 個被困在迷宮里打圈圈。

先讓所有沒被打上向上 U 的非最后一行的格子全都打上 D，讓它們?nèi)M到最后一行，然后再想如何困住。

很簡單，最后一行的前 \(n-1\) 個全給往右 L，最后一個給往左 R 就行了。這樣就會被控制在 \((n,n-1)\) 和 \((n,n)\) 兩個格子里走來走去走來走去了。

無解情況？當且僅當 \(k = n^2 - 1\) 的時候才會無解，因為這個時候只有一個格子是走不出去的，但是它要么直接走出去了，要么會走到一個走得出去的格子里，所以是沒有辦法構造出來的。

C

CF 是懂迷惑人的。

題目給了個什么對 \(676767677\) 取模，實際上毫無必要因為答案最大 \(2\)。

為什么呢？因為考慮兩個相鄰的 \(a_{i-1}\) 和 \(a_i\)，發(fā)現(xiàn)它們的差值頂多 \(2\)。因為它們的差距只在相互能否看到對方而已。

那么只要固定了第一個人的披斗篷方式，后面的人就全能算出來了，當然嘛有無解情況，也就是后面的人算出來不存在什么的。

定義 \(c_i\) 表示第 \(i\) 個人的披斗篷方式，其中 \(c_i = 0\) 表示第 \(i\) 個人的斗篷往左披，\(c_i = 1\) 則表示第 \(i\) 個人的斗篷往右披。

于是我們枚舉 \(c_1 \in \{0,1\}\)，然后可以推出式子：對于每個 \(i>1\)，都有 \(c_i = a_{i-1}-a_i+1-a_{i-1}\)。當然了如果 $c_i < 0 $ 或者 \(c_i > 1\) 那么顯然這種情況不存在。

求出來以后就可以了嗎？為了保險我驗證了一下。簡單寫個差分就可以啦，記得算上自己可以看到自己的情況。

D

肯定不能一個一個試那絕對會掛完。

我的方法很奇怪。但是能過就對了。

大概就是，先把這 \(n\) 個電池分成 \(n\) 組，每組一個電池。只要還沒找到一組，我就一直 while 下去，直到找到！

while 里頭干啥嘞？首先合并這些電池組。咋個合并法？很簡單，就是選相鄰兩個并起來，并成新的電池組，于是個數(shù)就會是上次的一半。由于 \(n\) 特小，所以咋搞都行。

接著咱枚舉每個電池組中的兩個不相同的元素 \(x,y\)，然后詢問 \(x,y\) 可不可以通電。如果回答了 \(1\)，OK 那咱直接把程序結束，因為找到了嘛！回答了 \(0\)，那咱不管，就讓它繼續(xù)回答著。

如果這一次所有的電池組中都沒能找到兩個都可以通電的電池，那么我們可以決定一件事，那就是 \(a \le cnt\)，其中 \(cnt\) 是當前電池組的數(shù)量。抽屜原理嘛。因此一直這樣走下去，越往后走，你所知的剩余次數(shù)其實就越多，因為 \(a\) 的數(shù)據(jù)范圍在不斷縮小。

那么最后的詢問次數(shù)大概是什么樣的呢？我粗略地算了一下，莫約是 \(\left \lfloor \dfrac{n^2}{2\lceil \frac{a}{2} \rceil} \right \rfloor\) 的，嗯，和題目給的范圍 \(\left \lfloor \dfrac{n^2}{a} \right \rfloor\) 差不多，還稍微少一些些，肯定能過啦！

E

分類討論。

• \(n=1\)：
  • 這個時候總步數(shù)是固定的，只需要考慮奇偶性，奇數(shù)則先手贏，否則后手贏。
  • 設 \(f_i\) 表示在第 \(i\) 列的一個 token 貢獻的總步數(shù)。
  • 易得出 \(f_1 = 0\)，\(f_i = 1 + \sum_{j=1}^{i-1} f_i (i>1)\)。
  • 然后可以發(fā)現(xiàn) \(f_i = 2^{i-2}(i>1)\)，結合 \(2\) 的次冪的性質(zhì)，所有 \(i \ge 3\) 的列對奇偶性都毫無貢獻。
  • 于是只需要看第 \(2\) 列的 token 個數(shù)，為奇數(shù)則先手贏，否則后手贏。
• \(n>1\)：
  • 觀察發(fā)現(xiàn)，將 token 上下移動就能將對應列的 token 個數(shù) \(+1\)，相當于改變這一列的 token 個數(shù)的奇偶性。
  • 假如每列的 token 個數(shù)都是偶數(shù)，后手就可以根據(jù)先手的操作情況決定自己的操作情況——就像取石子那樣，所以后手必勝。
  • 但是當存在部分列的 token 個數(shù)是奇數(shù)的時候，先手可以選擇最靠右一列然后將所有這些是奇數(shù)的全改成偶數(shù)，然后用和上面后手一樣的套路，于是先手就可以贏了。

簡單判斷一下即可。

F

對于每個顏色 \(x\)，我們求出含有顏色 \(x\) 的點的森林，對于其中的每個連通塊 \(S\)，我們發(fā)現(xiàn)，如果要顏色 \(x\) 對 \((u,v)\) 這對點組造成貢獻，只需要滿足 \(u,v \in S\) 即可。

那么問題就完全轉化了，和樹壓根無關。這里把 \(n,s,q\) 均當做 \(n\) 來看待。于是題目就等同于是給定 \(n\) 個集合（并且保證這些集合的大小之和不會超過 \(n\)），對于每個點組 \((u,v)\) 求有多少個集合包含 \(u,v\) 兩個數(shù)。

考慮根號算法。設 \(B = \sqrt{q}\)，實際可取 \(400\)。

把所有的點按照 \(B\) 對半切割，分成兩部分，一部分是度 \(\le B\) 的，還有一部分是度 \(> B\) 的。

先預處理集合 \(T_u\)，對于每組詢問都把 \(v\) 加入 \(T_u\) 集合。

如果一個詢問是由兩個度 \(\le B\) 的點構成的，顯然這些點的集合 \(T\) 的大小不會超過 \(B\)（可能有常樹，但總之數(shù)量級是 \(O(B)\) 的）。然后我們遍歷所有集合，走到 \(u\) 就給它打上標記。然后后面再跑 \(v\)，這樣就能對應上算出答案了。

然后再考慮一個詢問出現(xiàn)了度 \(> B\) 的點的情況。直接對于每個度 \(>B\) 的 \(u\)，暴力遍歷所有集合，如果在某個集合里它出現(xiàn)了，就把這個集合內(nèi)所有在 \(T_u\) 內(nèi)的數(shù)全都算進它的貢獻里。

然后看一下兩邊的時間復雜度，都是 \(O(n \sqrt{q})\) 的，沒什么問題。

簡單總結

總而言之，言而總之——還算滿意吧。

如果能推出 E 來那就更好了。

F 我倒是不指望考場上能推出來什么，不過一定能寫暴力就對了。

再接再厲。

小彩蛋：

……F 就更不可能了，但是無聊的我還是想去看一下。想了想，毫無思路，只是覺得百分百要上 LCA，但其他就……

——節(jié)選自【賽時情況】部分。

然鵝后面的題解沒有提到任何和 LCA 相關的東西，因為樹的性質(zhì)被搞沒用了。簡單地說就是題意轉化了嘛。

所以百分之百是不準確的。準確的應該是百分之一百二十，甚至百分之一萬。