作者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/cn.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