作者Ori185 (JstMonika)
看板C_and_CPP
標題[問題] zerojudge e288 時間複雜度問題
時間Wed Jul 15 15:03:28 2020
問題(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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1594796611.A.F05.html
1F：推 FanFlyAway: 改用 unordered_map 應該就可以了 07/15 16:12
2F：→ FanFlyAway: 可以把查詢的複雜度從 O(log n) 壓到 O(1) (expected) 07/15 16:13
3F：→ Ori185: 回F大，我有試過這個方法，一樣是TLE 07/15 19:37
5F：→ Ori185: 附一下我同學的code好了，他用的也是map，但是我就找不到 07/15 19:39
6F：→ Ori185: 我的code哪裡有問題QQ 07/15 19:39
7F：→ firejox: 輸入呢？一次讀一整行？ 07/15 20:38
8F：→ Ori185: 我也試過這個，改成string用cin >> 一樣TLE.... 07/16 09:29
9F：→ Ori185: 不知道cin.get()跟用string一次讀整行的效率有沒有差很多 07/16 09:30
10F：→ Ori185: ，但我的code這兩個版本都不過就是了 07/16 09:30
11F：推 aa0917954358: cin.get()改成cin >>就過了 07/16 10:03
12F：→ Ori185: 謝謝各位，我修改後發現是自己用map的方式出了問題，改完 07/16 23:31
13F：→ Ori185: 後AC了！謝謝！ 07/16 23:31