作者vincent97198 (萌新冒险者)
看板C_and_CPP
标题Fw: [问题] 请教 zerojudge c260 的想法
时间Thu Jan 31 00:06:27 2019
※ [本文转录自 Prob_Solve 看板 #1SKMSVJI ]
作者: vincent97198 (萌新冒险者) 看板: Prob_Solve
标题: [问题] 请教 zerojudge c260 的想法
时间: Wed Jan 30 16:58:05 2019
问题
https://zerojudge.tw/ShowProblem?problemid=c260
我的想法:
单调伫列找解
我的程式码
https://ideone.com/A8PxXy
我的问题:
要用什麽方法才能找到全部的解呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.33.208.245
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1548838687.A.4D2.html
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: vincent97198 (1.175.218.216), 01/31/2019 00:06:27
1F：→ vincent97198: 补了程式码应该不会被当成伸手文了吧 01/31 00:09
2F：推 sifmelcara: (a) 先把问题 reduce 到 「求平均值 > x 的 段数」 01/31 00:48
3F：→ sifmelcara: (b) 要求解 (a) ，我们可以把每个值都减掉 x，问题 01/31 00:49
4F：→ sifmelcara: 就被 reduce 到「求平均值为正的段数」 01/31 00:49
5F：→ sifmelcara: 接着由左到右枚举蛋糕尾端，过程中用 set 维护 01/31 00:49
6F：→ sifmelcara: sums ，就能快速查询有几个蛋糕头的位置合法 01/31 00:50
7F：→ sifmelcara: *维护 prefix sums 01/31 00:50
8F：→ vincent97198: 谢谢我懂了 01/31 02:09
9F：推 tccw0941: 这样每次维护是O(n)？ 01/31 12:34
10F：→ vincent97198: 对诶，这样好像不能在时限内诶 01/31 14:11
11F：→ sifmelcara: 对耶，C++的set没办法O(logN)查询比x小的元素数量 01/31 16:45
12F：→ sifmelcara: 那就把set改成 离散化 + fenwick tree 应该就可以了？ 01/31 16:46
13F：→ sifmelcara: 谢谢你的P币 01/31 16:47
14F：→ vincent97198: s大可以说得更详细一点吗? 01/31 18:42
16F：推 ckc1ark: 每个数减掉平均上/下限 找in/decreasing pair数 02/01 15:19
17F：→ ckc1ark: 这些pair就是不符合的 02/01 15:19
18F：→ ckc1ark: 找pair数的方法可以从merge sort过程找 02/01 15:20
19F：→ ckc1ark: 这边的每个数=prefix sum的array(最前面补0) 02/01 15:21
20F：→ ckc1ark: 有点描述错误 是所有数减完上/下限再做 prefix sum 02/01 15:24