1 条题解

  • 0
    @ 2026-11-16 20:48:26

    差值配对:解题说明

    用 unordered_map<long long,long long> 统计频数。对每个不同值 x,查找 x−C;若 C>0,贡献 freq[x]·freq[x−C],两个值不同,自然没有同一下标。若 C=0,必须扣除与自己配对的选择,贡献 freq[x]·(freq[x]−1)。将各贡献相加即可。

    reserve 预留哈希表空间;find 查询且不插入元素。键也使用 long long,因为 x−C 最低可达 −3000000000。求积前频数就是 long long,避免 32 位溢出。

    期望时间 O(n),空间 O(n)。哈希表在恶意碰撞下可能变慢;稳定复杂度替代方案是排序后,对每个元素用 lower_bound、upper_bound 查找 x−C 的次数,并在 C=0 时扣一,时间 O(n log n)。

    常见错误:C=0 直接平方频数而包含 i=j;将有序对除以 2;用 int 保存答案;查询时随意使用 operator[] 并在遍历中插入新键。

    验证期望由独立 Python 算法生成,不读取参考程序。样例先手算,再以空实现确认测试失败;正式数据包含边界、固定种子随机及两个最大规模用例。

    C++17 参考实现

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n; long long C; cin >> n >> C;
        unordered_map<long long, long long> freq;
        freq.reserve(2 * n + 1);
        for (int i=0;i<n;++i) { long long x; cin>>x; ++freq[x]; }
        long long answer=0;
        for (const auto &entry:freq) {
            long long x=entry.first, f=entry.second;
            auto it=freq.find(x-C);
            if (it!=freq.end()) answer+=f*(it->second-(C==0?1:0));
        }
        cout << answer << '\n';
        return 0;
    }
    
    
    • 1

    信息

    ID
    5266
    时间
    2000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    2
    已通过
    1
    上传者