【TOI2019 二模 pC】馬力的比賽
題目敘述
有$n$場比賽，每場比賽的時間是一個區間$[l_i,r_i)$，馬力想要比盡量多場時間不重疊的比賽，請問：
1. 為了比最多場比賽，有幾場比賽是馬力一定得參加的？
2. 在參加最多場比賽的前提下，馬力有幾種參加比賽的組合？ （答案模$10^9+7$）
3. 有多長的時間馬力一定在參加比賽，不論他選擇什麼比賽組合？
例如說：如果現在有6場比賽時間分別是$T(1)=[0,3)$, $T(2)=[4,6)$, $T(3)=[3,5)$, $T(4)=[7,9)$, $T(5)=[7,9)$, $T(6)=[2,5)$，那馬力可以參加3場比賽，組合有$\{1,2,4\}$, $\{1,2,5\}$, $\{1,3,4\}$, $\{1,3,5\}$。第一場比賽馬力一定要參加，且$[0,3)$, $[4,5)$, $[7,9)$這幾個時間馬力一定正在比賽。故答案為$1$, $4$, $6$。
作法
令$S=\{[l_i,r_i) \mid 1\le i \le n\}$
首先，如果只問最多參加多少場比賽，這是一個很經典的dp題：
- 令$dp(t)$為時間$t$內最多能參加幾場比賽
- $\displaystyle dp(t)=\max(dp(t-1), \max _{[l,t)\in S} (dp(l)+1)) $
最後答案就是$dp(t_{max})$，如果離散化後$t_{max}$最多是$2n$，複雜度$O(nlogn)$（離散化）。
現在問題多了一些變化，先從最簡單的方法數開始，我們只要在dp轉移的過程中順便計算方法數即可，計算$dp(t)$時，如果一個轉移的方法的確達到最大比賽數量，就把方法數加上去。
- 令$g(t)$為時間$t$內參加最多比賽的方法數
- $\displaystyle g(t)=[dp(t-1)=dp(t)]\cdot g(t-1) + \sum_{[l,t)\in S} ([dp(l)+1=dp(t)]\cdot g(l))$
- $g(t_{max})$為所求之方法數
其中$[statement]$在$statement$是真時為$1$，否則為$0$。
如果每個區間的長度都是1，那問題變成LIS，所以以下我們稱呼一個最多比賽組合為一個LIS，並且令LIS的長度為$d$。
現在假設有兩個不同的LIS，分別為$\{a_1,a_2,...,a_d\}$和$\{b_1,b_2,...,b_d\}$，如果$a_i=b_j$且$i<j$，那考慮這個比賽順序
$$\{b_1,b_2,...,b_j,a_{i+1},a_{i+2},...,a_d\}$$
易知這種比賽方式不會有時間重疊的問題，而且長度為$d+j-i$，但LIS參加了$d$場比賽，我們卻構造出一個更多比賽的方法，矛盾。故$i=j$，這告訴我們說如果有一場比賽$u$出現在某個LIS裡面的第$\alpha$項，那在其他所有LIS中，他一定也是出現在第$\alpha$項或者是不出現。定義$level(u)$代表比賽$u$可能出現在LIS的第幾項（即上述的$\alpha$），其實由前面的dp我們可以知道
$$level(u)=dp(l_u)+1$$
因為我們一定要在時間$l_u$前參加盡量多的比賽，然後接著參加比賽$u$。
但如果一個比賽的時間太長，或者時機不對，他可能沒辦法出現在任何一個LIS中，那我們要怎麼判斷一個比賽會不會出現在某個LIS裡面呢？
令$rdp(t)$為時間$t$以後最多能參加幾場比賽，很直觀的，比賽$u$要出現在LIS裡面若且唯若
$$dp(l_u)+1+rdp(r_u)=d$$
而$rdp(r_u)$怎麼求？如果今天把時間倒序，那$rdp$和原來的$dp$其實一模一樣，所以$$\displaystyle rdp(t)=\max(rdp(t+1), \max _{[t,r)\in S} (dp(r)+1)) $$
把不滿足$dp(l_u)+1+rdp(r_u)=d$的比賽刪除掉並不會對題目有任何影響，所以以下直接不考慮這些比賽。
回到第一個問題，一場比賽$u$一定要參加若且唯若不存在$x\neq u$滿足$level(x)=level(u)$，這樣每個LIS的第$level(u)$項只能選擇比賽$u$，所以他就是一定得參加的比賽。
至於最後一個問題，我們可以思考什麼樣的狀況下$[t,t+1)$這個時間馬力一定在比賽。一個看起來很正確的猜想是一個時間$[t,t+1)$馬力一定在比賽的話，此時馬力一定在參加第$c$場比賽，$c$是某個常數。為了證明或否證，考慮以下情況：
在某個LIS$\{a_1,a_2,...,a_d\}$中，$[t,t+1)$時馬力正在參加第$c$場比賽 ；在另一個LIS$\{b_1,b_2,...,b_d\}$中，$[t,t+1)$時馬力正在參加第$c+1$場比賽。
現在如果馬力比賽順序是這樣
$$\{b_1,b_2,...,b_c,a_{c+1},a_{c+2},...,a_{d}\}$$
他會參加$d$場比賽而且$[t,t+1)$時沒在比賽，所以剛剛的猜想是正確的。
所以馬力一定在比賽的時間是所有$level(u)=1$的比賽交集，所有$level(u)=2$的比賽交集，...，所有$level(u)=d$的比賽交集。
最後總結一下複雜度。
現在假設有兩個不同的LIS，分別為$\{a_1,a_2,...,a_d\}$和$\{b_1,b_2,...,b_d\}$，如果$a_i=b_j$且$i<j$，那考慮這個比賽順序
$$\{b_1,b_2,...,b_j,a_{i+1},a_{i+2},...,a_d\}$$
易知這種比賽方式不會有時間重疊的問題，而且長度為$d+j-i$，但LIS參加了$d$場比賽，我們卻構造出一個更多比賽的方法，矛盾。故$i=j$，這告訴我們說如果有一場比賽$u$出現在某個LIS裡面的第$\alpha$項，那在其他所有LIS中，他一定也是出現在第$\alpha$項或者是不出現。定義$level(u)$代表比賽$u$可能出現在LIS的第幾項（即上述的$\alpha$），其實由前面的dp我們可以知道
$$level(u)=dp(l_u)+1$$
因為我們一定要在時間$l_u$前參加盡量多的比賽，然後接著參加比賽$u$。
但如果一個比賽的時間太長，或者時機不對，他可能沒辦法出現在任何一個LIS中，那我們要怎麼判斷一個比賽會不會出現在某個LIS裡面呢？
令$rdp(t)$為時間$t$以後最多能參加幾場比賽，很直觀的，比賽$u$要出現在LIS裡面若且唯若
$$dp(l_u)+1+rdp(r_u)=d$$
而$rdp(r_u)$怎麼求？如果今天把時間倒序，那$rdp$和原來的$dp$其實一模一樣，所以$$\displaystyle rdp(t)=\max(rdp(t+1), \max _{[t,r)\in S} (dp(r)+1)) $$
把不滿足$dp(l_u)+1+rdp(r_u)=d$的比賽刪除掉並不會對題目有任何影響，所以以下直接不考慮這些比賽。
回到第一個問題，一場比賽$u$一定要參加若且唯若不存在$x\neq u$滿足$level(x)=level(u)$，這樣每個LIS的第$level(u)$項只能選擇比賽$u$，所以他就是一定得參加的比賽。
至於最後一個問題，我們可以思考什麼樣的狀況下$[t,t+1)$這個時間馬力一定在比賽。一個看起來很正確的猜想是一個時間$[t,t+1)$馬力一定在比賽的話，此時馬力一定在參加第$c$場比賽，$c$是某個常數。為了證明或否證，考慮以下情況：
在某個LIS$\{a_1,a_2,...,a_d\}$中，$[t,t+1)$時馬力正在參加第$c$場比賽 ；在另一個LIS$\{b_1,b_2,...,b_d\}$中，$[t,t+1)$時馬力正在參加第$c+1$場比賽。
現在如果馬力比賽順序是這樣
$$\{b_1,b_2,...,b_c,a_{c+1},a_{c+2},...,a_{d}\}$$
他會參加$d$場比賽而且$[t,t+1)$時沒在比賽，所以剛剛的猜想是正確的。
所以馬力一定在比賽的時間是所有$level(u)=1$的比賽交集，所有$level(u)=2$的比賽交集，...，所有$level(u)=d$的比賽交集。
最後總結一下複雜度。
- 離散化 $O(nlogn)$
- 計算$dp$和$rdp$ $O(n)$
- 計算方法數和計算$dp$一模一樣 $O(n)$
- 計算一個比賽的$level$ $O(1)$
- 將比賽依照$level$分類後各個取交集 $O(n)$
附上賽後改寫的程式碼，因為還沒有judge，所以可能會有錯誤，請見諒。
留言
張貼留言