小G的LY数对 非正解做法：unordered_map + 剪枝优化常数

由于本人过于菜鸡，没有想到正解做法，只想到了比较暴力的做法：用 unordered_map 存下所有数组 a 中各数的个数，然后对于数组 b 中的数暴力枚举修改的两位，然后在 unordered_map 查询对应数的个数加到答案中，复杂度 。

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

const int N=300010;

int n,m,a[N],b[N];
unordered_map<int,int> cnt;

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }
    long long ans=0;
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&b[i]);
        bitset<30> bi=b[i];
        for (int x=0;x<30;x++)
        {
            for (int y=0;y<x;y++)
            {
                bitset<30> t=bi;
                t.flip(x); t.flip(y);
                int c=t.to_ulong();
                ans+=cnt[c];
            }
        }
    }
    printf("%lld\n",ans);
    getchar(); getchar();
    return 0;
}

然后喜闻乐见的 T 了（
由于 unordered_map 常数较大，因此考虑在这上面优化。可以发现，在枚举 b 数组的所有修改方案时，有相当多的方案是数组 a 没有的，也就是不在 unordered_map 中。对于不在 unordered_map 中的数，如果直接跳过查询的话，会减少很多不必要的时间开销。
那么怎么判断某个数 a 数组中有没有呢？开 大小的数组内存是不够的，这时就要用上 bitset 神器了。

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

const int N=300010;

int n,m,a[N],b[N];
unordered_map<int,int> cnt;
bitset<1<<30> vis;

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        vis.set(a[i]);
        cnt[a[i]]++;
    }
    long long ans=0;
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&b[i]);
        bitset<30> bi=b[i];
        for (int x=0;x<30;x++)
        {
            for (int y=0;y<x;y++)
            {
                bitset<30> t=bi;
                t.flip(x); t.flip(y);
                int c=t.to_ulong();
                if (vis[c]) ans+=cnt[c];
            }
        }
    }
    printf("%lld\n",ans);
    getchar(); getchar();
    return 0;
}

跑得还挺快，不到 500ms，不知道能不能卡掉。