【TOI2019 三模 pC】 網路佈線問題

題目敘述

給一張有邊權的無向圖和一個常數$K$，我們要找出一顆生成樹滿足
  • 這顆生成樹的全中總和不超過$(1+\frac{2}{K})MST$
  • 對於所有$i$都有$dist(i)\le (1+K)dist'(i)$
其中，$MST$表示最小升生成樹權重和，$dist(i)$表示生成樹上$1$和$i$的距離，$dist'(i)$表示原圖上$1$和$i$的距離。

作法

大致上來說，先把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開始看即可)。

留言

張貼留言

這個網誌中的熱門文章

【TOI2019 三模 pD】自助餐

圖片
題目敘述 題目連結： 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輪內就有結果了(?
閱讀完整內容

【TOI2019 二模 pA】吠市數列

題目敘述 給定一質數$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$
閱讀完整內容

【TOI2019 三模 pA】圓的最佳覆蓋

圖片
題目敘述 平面上有$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)$）。 附上程式碼
閱讀完整內容