zhangxyhp

摘要： 首先計(jì)算在紅綠燈 \((a,b)\) 處期望的等待時(shí)間。記 \(a+b\) 為一個(gè)周期（即先有時(shí)長(zhǎng)為 \(a\) 的紅燈，再有時(shí)長(zhǎng)為 \(b\) 的綠燈），設(shè)我們?cè)?\(x\) 時(shí)刻到達(dá)了這個(gè)紅綠燈，那么我們需要等待的時(shí)間顯然為 \(\max(a-x,0)\)。 要求出期望，就要用上面那個(gè)函數(shù)的和再 閱讀全文

摘要： 看到 \(n\le 18\)，基本上是要做狀壓的。考慮進(jìn)行預(yù)處理，然后在較小的復(fù)雜度內(nèi)回答詢問(wèn)。設(shè) \(f_{S,u}\) 表示當(dāng)前走完了 \(S\) 中的點(diǎn)，現(xiàn)在在 \(u\) 點(diǎn)（\(u\in S\)），走完剩下的點(diǎn)的期望步數(shù)。于是有方程： \[f_{S,u}=1+\frac{1}{d_u}\s 閱讀全文