0w1

Expectation

Yuki 162 8020運動 ( DP )

No.162 8020運動 - yukicoder題意: 你上下各有一排 14 個連續的牙齒。 你現在 A 歲,你想知道你在 80 歲時,期望會有多少顆牙齒剩下。 牙齒掉落的機率是 P[ 左邊的牙齒是否剩下 + 右邊的牙齒是否剩下 ]。解法: 考慮動態規劃: dp[ i ][ j ][ k ] : 經過 i …

HR Colliding Circles ( Math, Expectation )

Programming Problems and Competitions :: HackerRank題意: 有 N 個線段,用長度描述。每一秒以均等機率有兩個線段合併 ( 長度變為總和 )。問期望上 K 秒後,每個線斷所成的圓面積總和為何。制約: 1 ≤ N ≤ 1e5 0 ≤ K ≤ N - 1 0 ≤ R[ i ] ≤ 1e4解法: 首先…

CFR 351 B. Jeff and Furik ( DP, Expectation )

Problem - 351B - Codeforces題意: 給你一個 1 ~ N 的排列。現在兩個人輪流操作,第一個人會選擇兩個數字,且一定選左數比右數大的兩個數字,並進行交換。第二個人會以 0.5 的機率選左數比右數大的兩個數字。求達到第一次排好期望需要幾次操作。資料規模: …

Yuki 242 ビンゴゲーム ( Expectation, Math )

No.242 ビンゴゲーム - yukicoder題意: 在 5 * 5 的矩陣玩賓果 ( 縱橫斜連線 ),每個格子都不重複存在一個介於 1 ~ 99 之間的一個整數。求矩陣裡的格子裡的數字都完全隨機,叫出的號碼也都完全隨機的情況下,喊到第 N 個數時,期望有多少連線。資料規模: 1…

Yuki 210 探し物はどこですか? ( Expectation, Priority Queue )

No.210 探し物はどこですか? - yukicoder題意: 有若干個房間,我們想找到一個藏在某處的寶物,而每個房間有寶物的機率為 P / 1000,如果該房間確實有寶物,則每次檢查這個房間會找到寶物的機率為 Q / 100。求最佳檢查順序下,能找到寶物的最小期望檢查次數…

CFR 518 D. Ilya and Escalator ( Expectation DP )

Problem - D - Codeforces 題意: N 個人排成一排,每秒隊首有 P 的機率進電梯,1 - P 的機率停留原地。求 T 秒後,期望有多少人在電梯裡。 解法: dp[ i ][ j ] : 已經過 i 秒,電梯裡有 j 個人的機率。 dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] * P + dp[ i -…