PTT數位生活區 / C_and_CPP (C/C++)

[問題] zerojudge e288 時間複雜度問題

看板C_and_CPP (C/C++)作者 (JstMonika)時間5年前 (2020/07/15 15:03), 編輯推噓2(2推 0噓 11→)
留言13則, 4人參與, 5年前最新討論串1/1
問題(Question)： https://zerojudge.tw/ShowProblem?problemid=e288 目前正在解這題 解法與網路上的類似 都是利用long long與mask求出互補集合 不過現在卡在速度太慢，後25%沒有辦法AC 不太懂TLE的部份出在哪裡 我自己算的方法是 while(n--) 的 O(n) 配上map搜尋的時間O(log n) 在50萬筆的情況下應該是夠用.... 是有哪個地方我用了不該用的東西或錯誤的方法，讓複雜度往上飆嗎 (像是位元運算，我同學寫了一陣子就順利AC了QQ) 謝謝各位 程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔) https://www.codepile.net/pile/RV7Z7WKr -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.172.146.137 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1594796611.A.F05.html
推
07/15 16:12, 5年前 , 1F
改用 unordered_map 應該就可以了
07/15 16:12, 1F
→
07/15 16:13, 5年前 , 2F
可以把查詢的複雜度從 O(log n) 壓到 O(1) (expected)
07/15 16:13, 2F
→
07/15 19:37, 5年前 , 3F
回F大，我有試過這個方法，一樣是TLE
07/15 19:37, 3F
→
07/15 19:39, 5年前 , 4F
07/15 19:39, 4F
→
07/15 19:39, 5年前 , 5F
附一下我同學的code好了，他用的也是map，但是我就找不到
07/15 19:39, 5F
→
07/15 19:39, 5年前 , 6F
我的code哪裡有問題QQ
07/15 19:39, 6F
→
07/15 20:38, 5年前 , 7F
輸入呢？一次讀一整行？
07/15 20:38, 7F
→
07/16 09:29, 5年前 , 8F
我也試過這個，改成string用cin >> 一樣TLE....
07/16 09:29, 8F
→
07/16 09:30, 5年前 , 9F
不知道cin.get()跟用string一次讀整行的效率有沒有差很多
07/16 09:30, 9F
→
07/16 09:30, 5年前 , 10F
，但我的code這兩個版本都不過就是了
07/16 09:30, 10F
推
07/16 10:03, 5年前 , 11F
cin.get()改成cin >>就過了
07/16 10:03, 11F
→
07/16 23:31, 5年前 , 12F
謝謝各位，我修改後發現是自己用map的方式出了問題，改完
07/16 23:31, 12F
→
07/16 23:31, 5年前 , 13F
後AC了！謝謝！
07/16 23:31, 13F
‣ 更多 Ori185 的文章
文章代碼(AID): #1V3gf3y5 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Ori185 的文章
文章代碼(AID): #1V3gf3y5 (C_and_CPP)