WC2021 菊蒻yxy的題解

[WC2021] 括號路徑

顯然 如果 a a a 可以到達 b b b ，則有 b b b 可以到 a a a

我們考慮從小的括號序列開始找 當存在邊 ( a , b , w ) (a,b,w) (a,b,w) 和 ( c , b , w ) (c,b,w) (c,b,w) 都為左括號

那么就有 a ? > b ? > c a->b->c a?>b?>c 構成一個合法序列 ?所以 a , c a,c a,c 互相可以到達

此時就可以把 a , c a,c a,c 縮成一個點 用并查集實作，并維護每一個集合指向它且為左括號的邊和當前 s i z e size size

再用新的并查集來當中介去合并新的點

具體實作時 按置合并邊（同型別邊放一起 用 m a p map map ），當一個并查集當中介時 它的同型別的邊對應的點可以合并 所以一個合并可能會引起另一個合并，把它們放入佇列處理，佇列中存合并操作，

時間復雜度 O ( m log ? m ) O(m\log m) O(mlogm) 期望得分100

[WC2021] 運算式求值

考慮一列一列處理 把矩陣每一列分別計算 相當于求解

• 給定陣列 A 0 , . . . , A m ? 1 A_0,...,A_{m-1} A0?,...,Am?1?，那么對應的 2 t 2^t 2t 個運算式的和是多少？

首先建出運算式樹 子節點為值 A i A_i Ai? 非子節點為 < , > , ? <,>,? <,>,?

然后在樹上 d p dp dp

S S S 是存陣列下標的集合， x x x 是樹上的一個節點， s u m x sum_x sumx? 為 x x x 子樹所有的方案數， l l l 為 x x x 左子樹， r r r 為 x x x 右子樹

狀態 d p ( S , x ) dp(S,x) dp(S,x) 表示：在任意 i ∈ S i\in S i∈S 且 j ? S j\notin S j∈/?S 有 A i > A j A_i>A_j Ai?>Aj? 的情況下， x x x 出算出來的結果是 A i A_i Ai?（ i ∈ S i\in S i∈S ）的方案數

那么很容易得到轉移方程

• x = ′ > ′ x=\ '>' x= ′>′ 時

  d p ( S , x ) = d p ( S , l ) × s u m r + ( s u m x ? d p ( S , l ) ) × d p ( S , r ) dp(S,x)=dp(S,l)\times sum_r+(sum_x-dp(S,l))\times dp(S,r) dp(S,x)=dp(S,l)×sumr?+(sumx??dp(S,l))×dp(S,r)

• x = ′ < ′ x=\ '<' x= ′<′ 時

  d p ( S , x ) = d p ( S , l ) × d p ( S , r ) dp(S,x)=dp(S,l)\times dp(S,r) dp(S,x)=dp(S,l)×dp(S,r)

• x = ′ ? ′ x=\ '?' x= ′?′ 時

  d p ( S , x ) = d p ( S , l ) × s u m r + ( s u m x ? d p ( S , l ) ) × d p ( S , r ) + d p ( S , l ) × d p ( S , r ) dp(S,x)=dp(S,l)\times sum_r+(sum_x-dp(S,l))\times dp(S,r)+dp(S,l)\times dp(S,r) dp(S,x)=dp(S,l)×sumr?+(sumx??dp(S,l))×dp(S,r)+dp(S,l)×dp(S,r)

求得所有的 d p ( S , x ) dp(S,x) dp(S,x) 后 我們開始計算最后的 a n s ans ans

對 A 0 , A 1 , A 2 . . . A m ? 1 A_0,A_1,A_2...A_{m-1} A0?,A1?,A2?...Am?1? 排完序后得到 A p 0 , A p 1 , . . . A p m ? 1 A{p_0},A{p_1},...A_{p_{m-1}} Ap0?,Ap1?,...Apm?1??

答案就是

a n s = ∑ i = 0 m ? 1 A p i × ( d p ( { p 0 , p 1 , . . . , p i } , r o o t ) ? d p ( { p 0 , p 1 , . . . , p i ? 1 } , r o o t ) ) ans=\sum_{i=0}^{m-1}A{p_i}\times(\ dp(\{p_0,p_1,...,p_{i}\},root)-dp(\{p_0,p_1,...,p_{i-1}\},root) \ ) ans=i=0∑m?1?Api?×( dp({p0?,p1?,...,pi?},root)?dp({p0?,p1?,...,pi?1?},root) )

時間復雜度 O ( 2 m ∣ E ∣ + n p o l y ( m ) ) O(2^m∣E∣+npoly(m)) O(2m∣E∣+npoly(m)) 期望得分100

[WC2021] 斐波那契

嗚嗚嗚嗚嗚我對這類題過敏啊嗚嗚嗚

您們好好學數學了嗎 嗚嗚我沒有我只會看題解

題解 P7325 【[WC2021] 斐波那契 大佬的題解

orz orz 撲通撲通跪下來