博客

http://acm.ecnu.edu.cn/problem/3272/


最近学校OJ需要挂VPN才能进……

有集合 A={a1,a2,…,an}，如果存在 i,j,k(i≠j,i≠k,j≠k) 使得 ai+aj=ak，则输出 NO；否则输出 YES。

数据没加强前很简单，暴力枚举加一点小优化就可以过。加强之后的标准做法FFT，暂时还不太会。有学长写了一种类似分块的办法：

用一个数组 b[] 表示集合，即当且仅当集合中存在 x 时 b[x]=1。将数组 b[] 分块，每块都用二进制数表示。由于 C++ 中最大的整数类型占 64 位，因此可以把每 64 各元素合成一个二进制数。这样的复杂度是 n∗maxa[i]/64，可以在规定时间（4s）内跑完。

受其启发，我偷懒采用了如下野鸡做法：

将数组 b[] 用二进制数 B 表示，于是可以直接判断 B&(B≪a[i]) 是否为零来获得答案。

问题在于，这样一来B最大可以有











2








200000

















2

200000


$2^{200000}$
，远远超出

long long/long double

范围。而如果用高精度写则丧失了位运算的优势。

不过我们还有STL。

嗯，就是bitset啦。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 2e5+5;
bitset<maxn> bs;
int a[maxn], n;

int main()
{
    int cas;
    cin >> cas;
    for (int t = 1; t <= cas; ++t)
    {
        scanf("%d", &n);
        int maxa = 0;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", a+i);
            maxa = max(maxa, a[i]);
        }
        printf("Case %d: ", t);
        try
        {
            bs.reset();
            for (int i = 1; i <= n; ++i)
                bs.flip(a[i]);
            for (int i = 1; i <= n; ++i)
            {
                if (a[i]*2  > maxa) continue;
                bs.flip(a[i]);
                if (( (bs << a[i]) & bs).any())
                    throw 1;
                bs.flip(a[i]);
            }
            puts("YES");
        } catch (int e)
        {
            puts("NO");
        }
    }
    return 0;
}