競賽程式相關

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

題目敘述 給定一質數$p$和$a_0$, $a_1$，定義數列$\{a\}$滿足遞迴式 $$a_n=a_{n-1}+a_{n-2}+1,\, \forall n \ge 2$$ 現在我們知道$x$, $a_x$, $y$, $a_y$, $k$，求$a_k$。若無解輸出$-1$，若有超過一解輸出$-2$ $x$, $y$, $k$都在long long範圍內，$p$在int範圍內 作法 首先根據簡單的運算我們有 $$a_n=F_{n-2}a_0+F_{n-1}a_1+F_{n}-1$$ 其中$\{F\}$為費波那契數列（$F_0=F_1=1$），且$F_{-1}=0$, $F_{-2}=1$ 令$a=F_{x-2}\%p$, $b=F_{x-1}\%p$, $c=F_{y-2}\%p$, $d=F_{y-1}\%p$, $e=F_{k-2}\%p$, $f=F_{k-1}\%p$ （用矩陣快速冪等方法求得） 我們有 $$ag_0+bg_1 \equiv a_x -(F_{x}-1) \pmod p$$ $$cg_0+dg_1 \equiv a_y -(F_{y}-1) \pmod p$$ 然後想要知道 $$eg_0+fg_1$$ 是多少 二元一次聯立方程式式國中課程內容，但如果套用到模運算下會很麻煩，尤其我們並不是真的要求$g_0$, $g_1$，而只要$eg_0+fg_1$。以下提供一個暴力分case的方法，雖然應該存在簡短的方式，但這種直覺的作法應該不容易漏case。 首先有個簡單的Lemma説對於所有質數$p$，不存在$i$使得$F_i$, $F_{i+1}$都是$p$的倍數，證明會在後面補。所以不會發生$a=0$且$b=0$，也不會發生$c=0$且$d=0$的情況。接下來就是分類了： $\mathbf{a=0}$       首先我們可以用$bg_1 \equiv a_x -(F_{x}-1)$求出$g_1$，然後代入第二條式子得到 $$cg_0 \equiv a_y -(F_{y}-1)-dg_1 \pmod p$$ 若$c=0$ $a_y -(F_{y}-1)-dg_1 \equiv 0$，則無限多組解 否則無解 若$c\neq 0$，直接計算出$g_0$

題目敘述 題目連結： https://tioj.ck.tp.edu.tw/problems/2077 Output only題。 給定正整數$n$, $k$, $d$, $T$，找出$T$個集合$S_1,S_2,...,S_T$滿足  $S_i \subset \{0,1,2,...,n-1\}$  $|S_i | = k$  $\forall i \neq j,\, | S_i \cap S_j | \le d$ Subtask $n=5$, $k=3$, $d=2$, $T=10$ $n=8$, $k=5$, $d=3$, $T=8$ $n=20$, $k=12$, $d=7$, $T=16$ $n=64$, $k=32$, $d=16$, $T=125$ $n=65$, $k=32$, $d=17$, $T=125$ $n=49$, $k=7$, $d=3$, $T=2401$ $n=121$, $k=11$, $d=4$, $T=161051$ $n=1369$, $k=37$, $d=2$, $T=50653$ $n=49$, $k=7$, $d=5$, $T=117649$ 作法 大致上可以把這些subtask分成三類：  Subtask 1~3是小測資。  Subtask 4~5是$n$為二的冪次的測資，我們可以注意到把Subtask 4的全部集合補上一個65就是Subtask 5的答案了。 Subtask 6~9都滿足特定的規律：$n=k^2$, $T=k^{d+1}$ 接著一個一個說明每一類的作法： Subtask 1~3 $n=5$直接枚舉所有5取3就可以了，$n=8$也可以自己手構一下 而$n=20$就得跑程式爆搜了，一個作法是從$S_1$慢慢選擇到$S_T$，要選擇$S_t$時，random產生1000個候選集合$s_1,s_2,...,s_{1000}$，把那些不符合條件（aka $\exists j<t,\, |S_j \cap s | > d$）的篩掉，然後找 $$\sum _{i=0}^{t-1} |S_i \cap s |$$ 最大的$s$，然後讓$S_t=s$。 這個作法跑十秒鐘大概10輪內就有結果了(?