2019.07.10【NOIP提高組】模拟 B 組總結

今天考的不是很理想

估分：100+100+50+0=250

實際：100+30+60+0=190

第一題：

Fibonacci sequence

矩陣乘法

f[0..3]表示第n個斐波那契的數，第n+1個數，前n個數的和，轉移顯然。

第二題：

Number

二分

二分mid，在1~mid中容斥原理即可。然而考場因細節打挂了，而且沒開long long。

第三題：

PermRLE

狀壓dp。

設f[ S ][ i ][ j ]表示選數狀态為S，每個塊中開頭選了第i個，結尾選第j個的最大能删的數的個數。

預處理出inside[ i ][ j ]，表示每個塊中第i個數與第j個數不相等的個數。

between[ i ][ j ]表示相鄰兩個塊中前一個塊的第i個與後一個塊中第j個不相等的個數。

f[ S ][ i ][ j ]=max{ f[ S-(1<<j-1) ][ i ][ k ] +inside[ j ][ k ] }。

發現空間不夠，我們可以将i那維壓掉。

第四題：

TreeCount

我們發現1到所有點的最短路徑是構不成環的，如果一個連通圖不能構成環，那麼它一定是一棵樹。是以題意可以轉化為求1到任意點的最短路構成的樹的種數，是以根據乘法原理，我們直接将1到每個點的最短路個數乘起來即可。

 有待提高