liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [49.218.98.111]
最後登入時間 ：
2024-10-21 21:40:50
感覺不是窮舉組合，因為每隊人數要相同，也許 greedy 就行了。
用什麼條件 $\text{Greedy}$ ?
我自己是寫窮舉，可是需要做一些剪枝操作，複雜度 $O(\frac{N!}{K!P!})$，$P$ 是每隊人數。
$N!$ 窮舉
$\div K!$ 不窮舉組的排列
$\div P!$ 不窮舉人的排列
目前他人上傳的代碼看起來都是少了 $\div K!$ 導致超時。
我猜官解應該差不多就是這樣啦，這樣 $N=15$ 複雜度是合理的，可是 $N=16$ 就會超時（多了約 $20$ 倍）
挺好奇你的 $\text{Greedy}$ 是怎麼寫的，等你上傳我再來 hack 看看🤪🤪🤪
liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [49.218.98.111]
最後登入時間 ：
2024-10-21 21:40:50
我自己是寫窮舉，可是需要做一些剪枝操作，複雜度 $O(\frac{N!}{K!P!})$，$P$ 是每隊人數。
$N!$ 窮舉
$\div K!$ 不窮舉組的排列
$\div P!$ 不窮舉人的排列目前他人上傳的代碼看起來都是少了 $\div K!$ 導致超時。
我猜官解應該差不多就是這樣啦，這樣 $N=15$ 複雜度是合理的，可是 $N=16$ 就會超時（多了約 $20$ 倍）
更正
複雜度是
$O(\frac{N!}{P!^KK!})$
這樣應該要到 $N=18$ 才會爆
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-10-16 22:34:33
我自己是寫窮舉，可是需要做一些剪枝操作，複雜度 $O(\frac{N!}{K!P!})$，$P$ 是每隊人數。
$N!$ 窮舉
$\div K!$ 不窮舉組的排列
$\div P!$ 不窮舉人的排列目前他人上傳的代碼看起來都是少了 $\div K!$ 導致超時。
我猜官解應該差不多就是這樣啦，這樣 $N=15$ 複雜度是合理的，可是 $N=16$ 就會超時（多了約 $20$ 倍）
更正
複雜度是
$O(\frac{N!}{P!^KK!})$這樣應該要到 $N=18$ 才會爆
我想錯了。