【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輪內就有結果了(?
留言
張貼留言