作者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