C 白晝夢(mèng) / Daydream
題解:
貪心 從后向前比較方便 每次看最后3位 四個(gè)串的最后3位都不同 所以可以直接確定應(yīng)該是那個(gè)串
時(shí)間復(fù)雜度: O(n)
D 連結(jié) / Connectivity
題解:
就是給定兩個(gè)圖, 點(diǎn)集相同, 邊集不相同, 問(wèn)對(duì)于每一個(gè)點(diǎn), 有多少個(gè)點(diǎn)在兩個(gè)圖中同時(shí)與它屬于一個(gè)連通塊
對(duì)于每一個(gè)圖, 我們可以通過(guò)dfs或者并查集處理出來(lái)每個(gè)點(diǎn)屬于哪一個(gè)連通塊
這時(shí)候我們把兩個(gè)合起來(lái), 用hash或者map記錄下來(lái)每一種情況(指的是類(lèi)似于一個(gè)pair的狀態(tài))對(duì)應(yīng)著有多少個(gè)點(diǎn) 就得到了答案
時(shí)間復(fù)雜度: O(n)
F シャッフル / Shuffling
題解:
關(guān)鍵在于題目中的一個(gè)性質(zhì) l_i \leq l_i+1
這有什么用處呢 其實(shí)即使輸入不限制這個(gè)條件也是一樣的 大不了讀入之后排序就好了
那么這個(gè)條件的作用在于 當(dāng)前做到第i個(gè)命令的時(shí)候, l_i-1之前的都已經(jīng)確定, 所以我們可以dp
令dp[L][R][num]表示當(dāng)前做到左端點(diǎn)為L(zhǎng),右端點(diǎn)為R的區(qū)間, L到R中間的1的個(gè)數(shù)為num的方案數(shù)
但是我們必須保證 r_i+1之后的元素確定 不然的話num這一維狀態(tài)不好變化
然后發(fā)現(xiàn) 事實(shí)上 l_i,r_i都是單調(diào)遞增的
因?yàn)閷?duì)于當(dāng)前的l, 我們可以找到以他為左端點(diǎn)的所有區(qū)間中r最大的那一個(gè), 其他的區(qū)間對(duì)結(jié)果沒(méi)有影響, 反正都是將這一段大區(qū)間里面的元素shuffle一下
所以對(duì)于每一個(gè)l,只有最大的r是有用的 我們把這個(gè)r處理出來(lái), 記作a_l
記錄ok_l表示所有區(qū)間中出現(xiàn)的所有的左端點(diǎn)坐標(biāo)l是否出現(xiàn)
記錄sum_l表示從L對(duì)應(yīng)的R到下一個(gè)L對(duì)應(yīng)的R之間(左開(kāi)有閉)中1的數(shù)量
然后把dp狀態(tài)中第二維去掉
下面我們就可以進(jìn)行轉(zhuǎn)移:
dp[L][num]=\left\{\begin{array}{cc} 1 & L=n\\ dp[L+1][num-1] & ok_L=0 \& S_i=1\\ dp[L+1][num] & ok_L=0 \& S_i=0\\ dp[L+1][num+sum_L] & ok_L=1 \& num=0\\ dp[L+1][num+sum_L]+dp[L+1][num+sum_L-1] & ok_L=1 \& num>0 \end{array}\right.
用記憶化搜索去做
時(shí)間復(fù)雜度:O(n)
