A A A
- 從父親繼承線性基，每一位保留深度最大的點， C o d e Code Code
B B B
- 考慮二分這個 k k k，我們暴力建出圖，用 h a s h hash hash 來判重和連邊，合法當且僅當沒有環，考慮怎麼輸出方案，首先可以在 d a g dag dag 貪心出每個點向後的最長鍊，隻需要考慮起點，發現需要支援比較兩個串的字典序，選好起點之後在 d a g dag dag 上貪心選最小的後繼即可， C o d e Code Code
C C C
- 首先考慮在上方 d d d 走了不超過半圈的情況，簡單推導可以得到就是積這麼一個東西
∫ a b d ∗ ( cos ( x R ) cos ( x R + α ) − 1 ) d x = ∫ a + d b + d d ∗ ( cos ( y R − α ) cos y − 1 ) d y ∫ a + d b + d d ∗ ( cos α + tan y R sin α − 1 ) d y \int_{a}^{b} d*(\frac{\cos(\frac{x}{R})}{\cos(\frac{x}{R}+\alpha)}-1)\text{d}x\\=\int_{a+d}^{b+d} d*(\frac{\cos(\frac{y}{R}-\alpha)}{\cos y}-1)\text{d}y\\ \int_{a+d}^{b+d} d*(\cos \alpha+\tan \frac{y}{R}\sin \alpha-1)\text{d}y ∫abd∗(cos(Rx+α)cos(Rx)−1)dx=∫a+db+dd∗(cosycos(Ry−α)−1)dy∫a+db+dd∗(cosα+tanRysinα−1)dy ∫ d ∗ ( cos α + tan y R sin α − 1 ) d y = d ( cos α y R − R sin α ln ( cos y R ) − y R ) = d ( ( cos α − 1 ) x R − R sin α ln ( cos ( x + d R ) ) \int d*(\cos \alpha+\tan \frac{y}{R}\sin \alpha-1)\text{d}y\\=d(\cos\alpha \frac{y}{R}-R\sin\alpha \ln(\cos \frac{y}{R})-\frac{y}{R})\\=d((\cos\alpha-1)\frac{x}{R}-R\sin\alpha\ln(\cos (\frac{x+d}{R})) ∫d∗(cosα+tanRysinα−1)dy=d(cosαRy−Rsinαln(cosRy)−Ry)=d((cosα−1)Rx−Rsinαln(cos(Rx+d))
-
下面考慮轉了多圈的情況（準确的說是多個半圈，因為在圓的兩半計算方式是不同的）
如果積分的兩個點滿足走 d d d 步後在同一個半圓，那麼它們的貢獻可以一起算，我們隻需要根據半圓的奇偶性來減掉圈數乘上周長的積分
∫ a b cos ( x R ) C d x \int _{a}^b\cos(\frac{x}{R})C\text{d}x ∫abcos(Rx)Cdx
若積分區間在同一個圓但不是一個半圓，我們需要二分出半圓的分界點， C o d e Code Code