UVa 12879 位运算 + STL

题意

传送门 UVa 12879

题解

求至多 $2$ 个元素的组合恰好等于所需距离的数量，暴力 $O(n^2)$ 显然不行。由于 $k_i,d_j$ 范围有限，考虑位运算，将每次敲击 $knob$ 与球洞距离 $hole$ 元素值对应的下标位置赋 $1$；$2$ 个元素的组合则可以通过位移实现，是否等于所求距离 $knob\&hole$ 观察对应位置是否为 $1$ 即可，或运算统计其数量。

#include <bits/stdc++.h> using namespace std; #define maxn 200005 int k[maxn]; int main() { int n, m, d; while (~scanf("%d", &n)) { bitset<maxn> knob, hole, res; for (int i = 1; i <= n; i++) { scanf("%d", k + i); knob[k[i]] = 1; } scanf("%d", &m); while (m--) { scanf("%d", &d); hole[d] = 1; } for (int i = 0; i <= n;i++){ res |= hole & (knob << k[i]); } printf("%d\n", (int)res.count()); } return 0; }