競賽程式相關

題目敘述 給一張有邊權的無向圖和一個常數$K$，我們要找出一顆生成樹滿足 這顆生成樹的全中總和不超過$(1+\frac{2}{K})MST$ 對於所有$i$都有$dist(i)\le (1+K)dist'(i)$ 其中，$MST$表示最小升生成樹權重和，$dist(i)$表示生成樹上$1$和$i$的距離，$dist'(i)$表示原圖上$1$和$i$的距離。 作法 論文題。連結： https://link.springer.com/content/pdf/10.1007%2FBF01294129.pdf 大致上來說，先把MST和Shortest-Path Tree建好。我們用$p[]$和$d[]$分別來紀錄“當前的樹”中每個人的爸爸和到root（原題的1，程式碼中的0）的距離，然後在等等的dfs過程中不斷用$relax$函數來建出這顆樹。注意到一次成功的$relax(u,v)$做的事就是把當前的樹中$v$的爸爸改前$u$。 接著dfs MST，每次發現有節點的距離太大時（也就是$dist(i)>(1+K)dist'(i)$），就直接用shortest-path tree的邊換掉。最後複雜度是$O(n)$，至於詳細作法和證明可以參考論文，裡面還有一個簡單的範例幫助暸解(直接從P308. Section 3開始看即可)。

題目敘述 同  https://codeforces.com/contest/1114/problem/F 作法 請看Codeforces提供的Editorial 程式碼如下

題目敘述 平面上有$n$個點，請問一個半徑為$r$的圓內部最多可以有幾個點？（圓周視為內部） $n\le 1000$, 值域和$r$都在$10^4$內 作法 一個很直覺的想法是如果有一個最佳狀況的圓，我們總是能稍微調整讓這個圓貼住其中至少兩個點，也就是說圓周上至少會有兩個點。這樣枚舉所有$\binom{n}{2}$個點對，畫一個半徑$r$且經過這兩點的圓，然後檢查每個點是不是在這個圓的內部，複雜度為$O(n^3)$，賽中只能拿到60分。 只要枚舉點對複雜度就已經$O(n^2)$了，後面檢查應該沒什麼機會更快，這代表枚舉點對行不通。所以我們試試看只枚舉一個點，然後看所有經過這個點的圓內部有幾個點。 假設現在固定圓要經過一個點$A$，那這個圓的圓心$O$必須在$A$為圓心，$r$為半徑的圓上。 一個重要的觀察是：對於其他的點$P$，當圓心在某個夾角內的時候，這個點才會在圓的內部裡面，如下圖所示。 有了這個觀察，題目就變成環狀區間加值，最後問最大值的問題，簡單做個差分就解決了。 那要怎麼計算一個點貢獻什麼區間呢？這可以用簡單的三角函數計算，如圖 如果$P$剛好在圓$O$上時，$OP=OA=r$，所以$\alpha=cos^{-1}(\frac{d}{2r})$，所以假設向量$AP$的幅角是$\theta$，那區間就是$[\theta-\alpha,\theta+\alpha]$。 實作上，因為是環狀的，所以先計算圓心角度為$0$的答案，然後繞一圈去更新答案即可。複雜度為$O(n^2logn)$（枚舉固定點$O(n)$，排序和差分$O(nlogn)$）。 附上程式碼

題目敘述 有$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$。