P5691 题解

Melo.VVちゃん · 2024-08-18 10:35:12 · 题解

讲一种暴力统计答案的方法。

如果你不想用 upper_bound、lower_bound，或者认为哈希表和迭代器指针太麻烦，那么请看下去。

首先我们发现 x 的取值最多有 150 种，而 150^3 是可过的，所以用折半搜索，这不是重点，这部分内容请看其他题解，主要讲一讲如何暴力的统计答案再优美的切掉这道题。

首先对于这种统计答案，如果想要单纯的使用 STL 的话，无非就两种选择：set 或者 map。分别考虑这两种。

首先我们应该注意到折半搜索找到的和不满足唯一性，所以应该使用 multiset。

那么我们将这两个玩意分别考虑：

• 如果想要使用 multiset，那么我们的思路应该是将前后两半分别存进两个 multiset 里面，最后对第一个中的每个值 i，去查找第二个中的 -i 的个数，需要用到 count 函数，但是它的复杂度是 \mathcal{O}(k+\log n) 的，非常危险，时间比较大。

• 如果是 map，可以做到（理论上的）\mathcal{O}(1) 查询，但是空间比较大，而且遍历很不方便（只能用麻烦的迭代器），同样会愉快的 T 掉几个点。

那么我们现在可以有这样一种想法：极限的卡过时间的同时极限的卡过空间，怎么办？

注意到用 multiset 的瓶颈在于 count 函数，那么我们不妨将第二个 multiset 变成 map 从而做到常数级别的查询。

同时，我们也可以看做将第 1 个 map 变成了 multiset，那么遍历就没有那么麻烦，同时降低一些空间。

要是想卡一卡可以用 unordered_map。

实际上最慢的点只有 3.33 秒。

代码：

inline void dfs (int num ,int end ,int sum ,bool flag) {
    if (num >= end + 1) {
        if (! flag) s1.insert (sum) ; // s1 是 multiset
        else s2[sum] ++ ; // s2 是 map
        return ;
    }
    f (i ,1 ,m ,1) {
        dfs (num + 1 ,end ,sum + k[num] * qpow (i ,p[num]) ,flag) ;
    }
}
for (auto i : s1) { // auto 遍历非常方便
    ans += s2[-i] ; // O (1) 访问
 }