#37635: 解題思路（含一些小技巧）- 三種解題方式
edoctopus322@gmail.com
(Moon Jam)
學校
:
臺北市立成功高級中學
編號 : 167591
來源 : [36.225.19.60]
最後登入時間 ：
2023-12-23 13:47:18
解題思路：
1. 直接模擬O(N^2)（有機會AC）
雖然依照這題的限制應該是絕對TLE，但實際試過之後還是有機會過的，可能是測資還不夠極限，總之這個方法就是假解。
實際來講，我的方法是找到最後剩下的個數，以及最後一圈走的步數，最後就可以知道誰是幸運者了，但因為我模擬時出局的人要花O(N)的時間erase，所以就會花上O(KN)的時間(K<N所以就寫成O(N^2))，實際可以看底下的程式。
2. 線段樹做O(N log N)（一定AC）
一樣直接模擬，但erase時間可以縮短至O(log N)
3. 使用約瑟夫問題演算法O(N)（一定AC）
約瑟夫問題就等價這題k=N-1，這個方法的邏輯是「倒推」，假設當你已經知道有N-1人時，留下來的那個人會是哪一號，那應該怎麼推得N人時，留下來的人是誰呢？可以看一下底下這張圖（以下會用0-base為說明，但實際是1-base，所以記得最後要+1）
我們不知道N個人誰會是幸運者，但是我們可以知道m-1人會在第一輪出局，那想想看，那個人出局後就變成N-1人了！那出局後的狀況跟上一張圖之間有什麼差別，有什麼辦法可以將出局後的狀況轉換到N-1人的狀況？另外當k不等於N-1時應該怎麼改變呢？
🌟 如果有時間的話可以用線段樹解法寫寫看，不然直接用約瑟夫問題的方法一下就解決了，這樣不夠有趣🫠
ZeroJudge Forum