2021百度之星複賽部分題解

2021百度之星複賽部分題解

\(n,m\leq 2\)的情況需要特殊讨論

其餘的，\(m\)為奇數時是二分圖，一定成立

\(m\)為偶數時，隻有\(n=m\)​成立

有點難度的計數題，将序列剖分成相同符号的連續段，每段個數為\(a_i\)

則按照+号和*誰開頭誰末尾分成4類讨論，再枚舉分段數

即可把問題轉化為若幹個這樣的子問題： 把+号分成\(x\)段，把*号分成\(y\)段

容易發現這就是盒子有序的第二類斯特林數，可以\(O(n^2)\)預處理，\(O(n)\)​完成一組詢問的查詢

貪心題真的搞心态，開始寫了一個堆貪心又T又wa

首先考慮\(b_i=1\)的簡單版本，此時容易發現就是最大化連邊的數量

每個點優先向兒子連，有多再丢給父親即可，可以用一個dfs貪心處理

一般的情況，可以做一個轉化得到一個類似的問題：

每個點有\(b_i\)個，最多連\(p_i\)次 \(\Longrightarrow\) 每個點最多連\(b_i\cdot p_i\)條邊

一條邊\((u,v)\)可以連\(\min\{b_u,b_v\}\)次

将容易發現轉化後一種連邊方案最終總可以構造得到一組合法的連邊方案

如上，同樣可以通過dfs來得到答案，為總點數-連邊數

是一個經典的dp優化題，可以預處理樹上兩點距離

先考慮對于一個給定序列的求解，容易發現是一個經典的區間dp的問題

這類問題想要優化複雜度，最常見的辦法是決策單調性

感性了解可以直接套用四邊形不等式進行決策優化，在\(O(n^2)\)時間内求解

回到原題，發現這些dp會出現共用一部分dp答案的情況

我們給每一個元素定一個編号，原先\(dp_{l,r}\)用\(l,r\)的編号替換為\(dp_{i,j}\)

這樣每次插入一個元素，計算以這個元素\(j\)為結尾，序列前面每一個\(i\)所對應的\(dp_{i,j}\)

同時維護區間總和，區間決策點（用于決策單調性）

通路前面每一個位置可以通過記錄一個前驅來實作，這樣就能完成共用dp答案

複雜度為\(O(m^2+(n+r)^2)\)​，由于數組通路比較不連續，常數較大

由帶入T2代碼可以得到，最劣情況下，本質不同的方案數達到\(3\cdot 10^5\)

即便資料随機也有大量極限情況，而且枚舉有常數，故不可以通過

實際上可以直接meet in the middle

枚舉前5個數，後五個數，方案數為\(\binom{10}{5}=252\)

再搜尋兩部分的答案，第一部分帶入\(x\)，第二部分初始帶入0，最壞情況下兩邊各有46種

最終的答案就是 ： 第一部分答案 \(\cdot\) 第二部分乘積+第二部分答案

枚舉之後已經确定了乘積，故兩部分是分離的，隻需要相加即可

相加求最小值可以尺取進行，枚舉的情況上界很松，實際極限複雜度達不到\(252\cdot 46\cdot \log\)

是以較大常數的實作也可以在1s左右出解