10.14 正睿做題筆記

10.14 正睿做題筆記

連續兩場掉分，心情非常不爽。

水題，直接拿 bitset 優化轉移就可以過掉這道題。

代碼：

有一定技巧性，屬于那種沒見過做不出來的題。真的非常巧妙。

首先是一個莫比烏斯反演轉化，利用莫比烏斯反演，每個詢問可以做成這樣：\(\sum_{d|x}\mu(d)\sum_{i=l}^r[d|a_i]\)。

我們考慮維護後面這個東西，不難發現可以把詢問分成兩塊，這樣我們所有的詢問都變成了這樣：\(\sum_{d|x}\mu(d)\sum_{i=1}^r[d|a_i]\)。

然後我們考慮做上面這個東西。首先我們可以把詢問離線下來，然後按照 \(r\) 排序。

然後我們用雙指針去做這個東西，當可以回答詢問的時候，我們就回答詢問。然後沒遇到一個 \(a\) 或者是查詢一個 \(x\)，我們用 \(\sqrt n\) 的時間複雜度去枚舉其因數。這樣總複雜度可以做到 \(O(n \sqrt n)\)。

這個題已經把暴力想出來了，但是放棄了進一步優化，這是我的問題，當時在 BC 之間抉擇的時候，應該優先選擇優化 dp 的。這樣起碼還有些盼頭。

暴力 dp 很好想，設 \(f_{l,r,k}\) 表示區間 \(l,r\) 内 \(k\) 是否有可能赢。那麼我們在左邊枚舉一個能夠被 \(k\) 打敗的數 \(a\)，右邊枚舉一個能被 \(k\) 打敗的數 \(b\)，然後轉移就可以。

稍微想一下可以枚舉到 \(n^4\)，就是我們關注的是左邊有沒有，右邊有沒有，是以不用枚舉數對。

然後我們考慮如何優化到 \(n^3\)，考慮第 \(3\) 維實際上并沒有什麼用處，這是因為：\(f_{l,r,k}=f_{l,k,k}\and f_{k,r,k}\)。然後我們直接可以省掉第 \(3\) 維，把 dp 變成 \(f_{l,r,0/1}\) 其中 \(0\) 表示原來的 \(f_{l,r,l}\) ，\(1\) 表示原來的 \(f_{l,r,r}\)。

因為 dp 值為 bool，是以我們考慮用 bitset 優化，具體來說，就是用 <code>bit1[l]</code> 來存 \(f_{l,k,0}\)，用 <code>bit2[r]</code> 來存 \(f_{k,r,1}\)，然後因為需要保證能夠打敗，是以我們轉移的時候在 and 上一個 <code>beat[k]</code> 表示能被 \(k\) 打敗的集合即可。

注意我們最好做完一階段 dp，在去更新兩個幫助轉移的 bitset。

非常巧妙的一個轉化。首先我們考慮這個題并不是簡單的，邊不在樹邊上，我們就可以随便走的題目，這是因為我們題目中的主人公不具有預見性，這個題目實際上是一個博弈模型，想像和你做博弈的人，每當你走到一個點時，就會考慮是否删掉相鄰的一個邊，且其删邊的機會隻有一次，他的目标是把你的路徑權值和最大化，你的目标是最小化權值和。

以下設 \(s\) 為最短路樹根節點。

我們考慮設 \(val_i\) 表示在最短路樹上去掉 \(i\) 與其父親的邊之後走到根的最短路。\(f_i\) 表示節點 \(i\) 的答案，那麼我們考慮如何計算。

顯然，如果對手打算在我們走到這個節點的時候删邊，那麼其一定删最短路上與 \(i\) 相連的父邊，這樣答案就是 \(val_i\)，否則，我們可以走到某個節點 \(j\)，然後這個時候狀态變成了 \(f_j\)，是以我們有轉移 \(f_i=\max(val_i,\min\limits_{(j,i)\in E}(f_j+w(i,j))\)。

現在我們有兩個問題需要解決：

如何計算 \(val\)。

以什麼順序轉移 \(f\)。

我們首先考慮第二個問題。

首先 \(f_s=0\)，其次，不難發現，如果 \(f_i\) 最終選擇從 \(f_j\) 轉移過來，那麼一定有 \(f_i&gt;f_j\)，如果從 \(val_i\) 轉移過來，那麼一定要麼節點 \(i\) 沒有任何出邊，要麼 \(val_i\) 最大。

上述性質标明，這個轉移一定沒有環，換句話說，我們一定能夠找到一個轉移方式。

不難發現，如果我們每次找目前 \(f\) 值最小的還沒有被擴充的節點，那麼一定不存在其餘節點能夠更新它。

是以我們可以通過迪傑斯特拉的方式來更新，因為滿足貪心性質，是以正确性顯然。

然後我們考慮如何計算 \(val_x\)。

首先一個性質是它一定隻走了一條非樹邊，如果走了兩條的話，不滿足最短路樹的性質，這個容易證明。且這個非樹邊的兩個節點在樹上之間的路徑一定經過這個節點 \(x\)，這個畫圖不難證明，否則的話不滿足是一棵樹。當然前提得是走這個邊是最優邊。

我們發現這個最優邊一定是從 \(x\) 往深走，走到某個節點，然後通過一條非樹邊，走到另一顆子樹，然後走到根節點。

我們考慮設 \((a,b,w)\) 為這個非樹邊。那麼 \(val_x=dis_a+dis_b+w+dis_x\)，其中 \(dis\) 為最短路樹上節點到根的距離。

暴力的想法是枚舉這個最右邊，不過這樣複雜度爆炸。

我們不如把所有的非樹邊拿出來，按照 \(dis_a+dis_b+w\) 進行排序，然後對于一個非樹邊 \((a,b,w)\)，覆寫這兩個點到 \(lca(a,b)\) 的所有點的 \(val\)，當然不覆寫 \(lca\)，我們用并查集維護覆寫的點，具體來說，當一個點被覆寫，我們就把它和它的父親合并，這樣我們查詢的時候會直接跳到其父親。

update 2021.10.15 我被 hack 了，注意到我們上面的代碼在标記樹邊時周遊樹邊的方案是隻要滿足最短路性質即可，但比如說 \(k\) 到 \(u\) 一共有兩條路徑，且權值和相等，那麼這兩條路徑都會被錯誤的标記為樹邊。 解決方案是在記一個 visit 數組，保證每個點不被周遊兩次。