寒假練題計畫11 小小題解

今天練題計畫的題目好棒，打個小題解
阿我懶所以就不翻譯題目ㄌ> <
然後A-C太水不講

pD

觀察一下發現答案同於：給一個陣列，問有幾對 $(a,b,c)$ 滿足 $a + b > c$
因為值域很小，可以直接 $\mathcal{O}(C^2)$ 枚舉 $a, b$ ，再用後綴和算出 $c$ 的數量

pE

先定義重要邊是可能出現在最短路徑樹上的邊
在做dijkstra的時候直接存所有重要邊中，邊權最小的一個即可
這樣做一定會是最小的，是樹的原因是若將所有重要邊畫成一張有向圖
這張圖是沒有環的，也因此最後的圖當然不會有環
又除了起始點都有一條邊連出去，所以圖是樹

submission

pF

題目連結

我蠻意外他有2100(?) 根本水題
只是實作好煩= =
做法就是先用bfs找出該走的路
然後因為他從 $(1, 1)$ 開始，所以一定可以找到一個安全點判斷swapUD和swapRL

submission

pG

題目連結

這題好棒超喜歡
$dp[i][j]$ 代表有 $i$ 個 $a$ ，現在有 $j$ 個 $ab$ 的機率
轉移式長這樣

1 2	dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * pa) % mod; dp[i][i + j] = (dp[i][i + j] + dp[i][j] * pb) % mod;

然後接下來是計算答案的部分，答案會等於：
$\sum_{j >= k}{dp[i][j] * j} + \sum_{i == k, j < n}{dp[i][j] * (i + j + E)}$
其中 $E$ 是抽到 $b$ 之前期望抽到 $a$ 的次數，由恆等式 $E = (E + 1) * pa$ 可以算出
後面那條式子是當 $j$ 還沒到達上限，但已經確保再抽到一次 $b$ 就可以結束對答案的貢獻
至於 $i < k$ 不須考慮是因為那些再考慮進去會算到重覆

submission