[考試總結]noip模拟48

今天題目比較簡單，是以有時間來寫部落格。。。

然後先從模拟48開始

啊這。。。。

記不太清自己的考場行為了，就簡單說說題解吧。。。

lighthouse

這個就是一個挺簡單的容斥，然後一個環排列就有了。

系數為 \((-1)\)

Minner

歐拉回路

假設圖中有 \(k\)個聯通塊，然後第 \(i\) 個點的度為 \(c_i\)，那麼

\[Ans = \sum_{i=1}^{k}max(1,\frac {c_i}{2})-1\]

第二問就是将度數為奇數的點任意配對連額外的邊。

然後每個連通塊跑歐拉回路,額外連的邊會将回路割成若幹段路徑,這些路徑之間以及連通塊之間用1操作跳。

然後就是 \(\mathcal O(n + m)\)

Lyk Love painting

似乎就是一個結論 \(dp\)，忘了思路了。。。