各位电神安安 o'_'o Sum of Three Values 应该算是很经典的题目，其简化版本 Sum of Two Values 常见的解 法有两种，分别是用杂凑表及 two pointer 有趣的是在 CSES 上使用 std::unordered_map 及 GNU PBDS 的 gp_hash_table 分别各有 一笔测资 TLE, 反而改用 BST 才 AC, 证实 log 只是常数 XD 回过头来看 Sum of Three Values, 我想同样有杂凑表与 three pointer 两种解法。 CSES 上 N <= 5000, 显然需要至少 O(N^2) 的解。 https://cses.fi/problemset/task/1641 这次试过 gp_hash_table, cc_hash_table, unordered_map 但测资 #21 始终过不了。 我也上网搜寻比较好的 hash function, 还是 TLE. https://reurl.cc/4a05rY 把测资载下来研究，cc_hash_table 约十秒多，cc_hash_table + custom hash function 约七秒，cout IMPOSSIBLE 完直接 exit(0) 不管记忆体压到四秒多，BST 则是惨烈的三十 几秒 https://cses.fi/paste/25d625b68bc3c2b828e863/ 但我的很好奇为何会这样？？ 明明 N 不过才 5000, 只做 12497500 次查询竟然要花上 4.3 秒！？ 这笔测资到底有何神秘之处？？其他同样 N = 5000 且无解的测资顶多跑个 0.1 秒而已。 实在找不到程式的瓶颈在哪，优化读 5000 个整数也只快零点零几秒。 想请教各位板友，这题是非用 three pointer 不可吗？？可是我看 Sum of Four Values 好像还是用杂凑表耶。 还是 hash function 有甚麽改进之处？？ 感谢 -- 看到国外 IP, 尤其是来自奇怪地区，请多加留意是否为跳板。 https://ptt.nevikw39.cf/ 输入 ptt 上的 id, 即列出其最近上站的 10 个 IP 地址、日期、国家与是否为跳板。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.240.165.72 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1628963639.A.030.html