Bubble Cup 11 - Finals [Online Mirror, Div. 1]
一場很好玩的題啊！
I. Palindrome Pairs
- 枚舉哪種字元出現奇數次。
G. AI robots
- 對\(r\)從大到小排序，然後cdq分治。
- 注意要對\(q-k,q+k,q\)進行離散化
B. Space Isaac
- 對原序列做差分,
b[i]=a[i]-a[i-1]
- 如果我們要湊出\(x\),那麼集合A中小于\(x\)的數字，要關于\(x/2\)對稱，大于\(x\)的數字要關于\((x+m)/2\)對稱。
- 枚舉分界點x的位置，\(x\)左邊，\(x\)右邊的差分序列，都應該式回文的，才能合法。
- 怎麼判斷回文串呢？hash一下就好了。
C.Hyperspace Highways
- 先求出所有的點雙聯通分量。加上那些邊後，每個點雙都會變成一個完全圖。
- 我們給每個點雙建立一個虛拟節點，從這個虛拟節點像點雙中每一個點連長度為
1/2
- 剩下的圖一定是一棵樹，如果有環的話，那麼又出現了新的點雙。
- 樹上路徑長度查詢，拿LCA做就好了。
一開始想的假算法：留下所有割點，建樹。，然後建的樹裡竟然有環！于是就GG了。
從連通分量的角度，去重建一個圖，也是比較常見的操作了。
- SCC縮點後，有向圖會變成一個DAG。要連招的話，可以追加一個DAG上的DP什麼的。
- BCC邊雙縮點後，把所有橋保留。每隻邊雙連通分量變成一個點。那麼我們會得到一棵樹。樹能幹的事就多着了！好多好多操作都可以施展了。
- BCC點雙！不能随便縮點啊！會得到很辣雞的東西。
D.Interstellar battle
- 一開始想樹形DP搞，然後很GG。
- 連通塊個數 = \(V - E\)，也就是點數-邊數。
- 我們分别求出V的期望，和E的期望就好了。V的期望很好求。
- E的期望 = \(\sum_{edge} p(edge苟住了)\)，期望可加性，把條邊對答案的貢獻加起來即可。
像這種期望問題，一般是兩種政策了。
- 政策1：最終的答案可能要我們算一個宏偉的東西，根據期望的可加性什麼的，把最終答案分成很多個小事件。然後加起來。這個問題就是這樣的！
- 政策2：拿頭去DP。如果事件之間不具備獨立性，然後我們又要算\(E(AB)\)這種東西。那就考慮下DP吧！如果拿DP搞那種政策1的那種東西，就會又掉血，又掉藍，這就非常不理智了。
轉載于:https://www.cnblogs.com/RUSH-D-CAT/p/9752182.html