AT_abc296_c [ABC296C] Gap Existence 题解

Comet387 · 2023-04-08 21:52:10 · 题解

前言

STL 大法好！

考场上做这道题，由于细节挺多，罚了几次时，终于 AC 了。

思路

若存在 A_i-A_j=X，则一定保证 A_j+X=A_i。

所以可以用一个 bool 数组标记每一个满足 1\leq k\leq N 的 A_k，判断 A_k+X 是否被标记即可。因为存在负数，所以将所有数加上 10^9+1 保证所有数都为正数即可。

奈何，我们掐指一算，空间约 (\max(A_i)+10^9+1+\max(X))\text{ Byte}\approx3\times10^9\text{ Byte}\approx2861\text{ MB}。显然 MLE。

但是，我们可以使用 bitset。先介绍一下 bitset 吧：

bitset 是一种类似布尔数组的结构，它的每一个元素只能是 0 或 1，但是经过优化，每个元素仅用 1\text{ bit}=\dfrac{1}{8}\text{ Byte} 空间。

于是，空间最大使用为 2861\text{ MB}\div8\approx358\text{ MB}，完美解决 MLE。

下面是 bitset 常见的使用方法（设名称为 b）：

• 定义：bitset<x>b，其中 x 为 bitset 长度；
• 标记：b.set(y)，其中 y 为想要标记的下标；
• 查看是否被标记：b.test(z)，其中 z 为想要查看是否被标记的下标。

于是，我们很快就能写出代码了！时间复杂度 \Theta(n)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,x,l[200001]; // l 数组为题目中的 A 数组
bitset<3000000002> a; // 定义 bitset
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;++i)
    {
        cin>>l[i];
        l[i]+=1000000001; // 保证为正数
        a.set(l[i]); // 标记
    }
    for(int i=1;i<=n;++i)
    {
        if(l[i]+x>=0&&l[i]+x<=3000000002) // 判断，防止越界 RE
            if(a.test(l[i]+x)) // 查看是否被标记
                return puts("Yes"),0; // 若被标记，即满足题目要求，直接输出 Yes
    }
    puts("No"); // 否则输出 No
    return 0;
}