Bitmasks

位运算题单 477. 汉明距离总和 先考虑两个数字的情况，按位考虑，如果二进制位不同，那么对答案的贡献是 1. 接下来考虑多个数字的情况，同样按位考虑，对于某一位来说，设 0 的个数是 $c_1$，1 的个数是 $c_2$，那么这一位对答案的贡献是 $c_1 \cdot c_2$ int totalHammingDistance(vector<int> &a) { int ans{}; For1(i, 0, 30) { int c1{}, c2{}; for (auto x : a) { if ((x >> i) & 1) c1++; else c2++; } ans += c1 * c2; } return ans; } 1863. 找出所有子集的异或总和再求和 因为数组长度只有 12，考虑暴力，枚举所有的子集，暴力计算每个子集的异或和。 int subsetXORSum(vector<int> &a) { int n{SZ(a)}, ans{}; For(i, 0, (1 << n)) { int cur{}; For(j, 0, n) { if ((i >> j) & 1) { cur ^= a[j]; } } ans += cur; } return ans; } 题解区的神奇做法。 按位考虑，先考虑第 $i$ 位，如果一个集合中，第 $i$ 位是 1 的数字的个数是奇数，那么这个集合在第 $i$ 位对答案有贡献，并且贡献等于 $2^i$。 接下来考虑有多少个集合在第 $i$ 位对答案有贡献。也就是求有多少个集合，满足集合内的所有数字在第 $i$ 位是 1 的个数是奇数。设数组内所有数字在第 $i$ 位是 1 的个数是 $m$，那么包含至少一个 1 的集合的个数是 $2^m - 1$ 个。其中包含奇数个 1 的集合的个数是 $\sum{2^{n - m} {m \choose k}}$ 其中 $k$ 是奇数。根据二项式公式，能够得到当 $k$ 是奇数的二项式系数之和是 $2^{m - 1}$，因此上面的和是 $2^{n - 1}$. ...

AGAGA XOOORRR 求出前缀 $XOR$ 和，$XOR$ 的简单性质，可以求出任意区间 $[l, r]$ 的 $XOR$ 和。 考虑最终局面，有两种情况：1. 只剩下两个数字。2. 只剩下三个数字。其它情况都可以通过操作转化成这两种情况。 因此可以考虑把原数组分成两个区间或者三个区间，而区间的 $XOR$ 和已经得到。 // Date: Sat Jan 13 20:56:11 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 2100; int n, a[N], b[N]; int check(int l, int r) { if (l > r) return 0; return b[r] ^ b[l - 1]; } void solve() { cin >> n; b[0] = 0; For1(i, 1, n) { cin >> a[i]; b[i] = b[i - 1] ^ a[i]; } bool flag = false; For1(j, 2, n) { if (flag) break; For(i, 1, j) { int c1 = check(1, i), c2 = check(i + 1, j - 1), c3 = check(j, n); if (i + 1 <= j - 1) { if (c1 == c2 && c2 == c3) { flag = true; break; } } else { if (c1 == c3) { flag = true; break; } } } } cout << (flag ? "YES" : "NO") << '\n'; } int main(void) { #ifdef _DEBUG freopen("1516b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

Iva & Pav tutorial 由于 $f(l, r) = a_l \And a_{l + 1} \ldots \And a_{r}$ 是有单调性的，因此可以考虑二分答案。接下来是如何快速求 $f(l, r)$，可以按位考虑，对每一个二进制位，计算区间内这个二进制位为 1 的个数，如果恰好等于区间的长度，说明区间内所有数字的这位都为 1，累加到答案中。数区间内 1 的个数可以使用前缀和快速得到。 // Date: Wed Dec 27 23:50:18 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010; int t, q, a[N], d[N][35], l, k, n; int check(int l, int r) { int res = 0; For(j, 0, 32) { int cn = d[r][j] - d[l - 1][j]; if (cn == r - l + 1) { res += (1 << j); } } return res; } int main(void) { #ifdef _DEBUG freopen("1878e.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n; For1(i, 1, n) { cin >> a[i]; } cin >> q; For(j, 0, 32) d[0][j] = 0; For1(i, 1, n) { int tmp = a[i]; For(j, 0, 32) { int cnt = 0; if (tmp & 1) cnt = 1; tmp >>= 1; d[i][j] = d[i - 1][j] + cnt; } } while (q--) { cin >> l >> k; int r = n, mid; int le = l; while (le < r) { mid = (le + r + 1) / 2; if (check(l, mid) >= k) le = mid; else r = mid - 1; } if (check(l, le) >= k) cout << le; else cout << -1; cout << ' '; } cout << '\n'; } return 0; }

Minimax Problem tutorial 要求数组 $b$ 的最小值最大，考虑二分，可以对 $min_{k = 1}^m b_k$ 进行二分，对于 $x$，判定是否存在两个数组 $a_i, a_j$，使得它们组成的数组 $b$ 中的所有的值都 $\ge x$，数组 $a_i$ 的个数有 $3 \cdot 10^5$ 个，但是长度只有 $8$，可以想到用二进制表示数组 $a_i$，当 $a_{i,k} \ge x$ 时，对应的二进制位为 1。这样数组 $a_i$ 最多只有 $2^8$ 个，因此一次判定操作的复杂度是 $O(n \cdot 8 + (2^8)^{2})$ // Date: Sun Dec 24 09:26:26 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) template <typename t> istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 3000'10, M = 10; int n, m, a[N][M]; PII check(int x) { set<int> s; map<int, int> b2i; For1(i, 1, n) { int tmp = 0, base = 1; For1(j, 1, m) { if (a[i][j] < x) { } else { tmp += base; } base <<= 1; } s.insert(tmp); b2i[tmp] = i; } for (auto x : s) { for (auto y : s) { int z = (x | y); if (z == ((1 << m) - 1)) { return {b2i[x], b2i[y]}; } } } return {-1, -1}; } int main(void) { #ifdef _DEBUG freopen("1288d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while (cin >> n >> m) { For1(i, 1, n) { For1(j, 1, m) { cin >> a[i][j]; } } int l = 0, r = 1e9 + 10, mid; while (l < r) { mid = (l + r + 1) / 2; if (check(mid) != PII{-1, -1}) l = mid; else r = mid - 1; } auto res = check(l); cout << res.f1 << ' ' << res.f2 << '\n'; } return 0; }

And It’s Non-Zero tutorial 只需要找到一个二进制位满足所有数字对应的二进制位都为 1 即可，如果没有，那么找到二进制为 1 的数字个数最大的那个位，然后把这位上为 0 的数字删除。接下来只需要求对于一个二进制位有多少个数字满足这个位为 1，题目给定的是左右端点，所以可以前缀和优化。 // Date: Sat Nov 25 10:27:53 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif const int N = 200010, M = 32; int t, l, r, b[N][M]; int main(void) { #ifdef _DEBUG freopen("1615b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); For1(i, 1, 31) { For1(j, 1, int(2e5)) { if (j & (1 << (i - 1))) b[j][i] = b[j - 1][i] + 1; else b[j][i] = b[j - 1][i]; } } cin >> t; while (t--) { cin >> l >> r; int res = 0, n = r - l + 1; For1(i, 1, 31) { int tmp = b[r][i] - b[l - 1][i]; res = max(res, tmp); } cout << n - res << '\n'; } return 0; }

Maximal AND 按位考虑，只有31位，要使得最后的结果某一位是1，需要所有 $a_i$ 的对应的位为1，统计出每个数字的第 $j$ 个二进制位为1的个数，从高位到低位依次考虑即可。 // Date: Thu Nov 23 21:01:56 2023 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; const ull Pr = 131; #define LN ListNode #define LNP ListNode * #define TN TreeNode #define TNP TreeNode * #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nonempty(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #else #define debug1 #define debug2 #define debug3 #endif #ifdef _DEBUG struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int val) : val(val), next(nullptr) {} ListNode(int val, ListNode *next) : val(val), next(next) {} }; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} }; #endif const int N = 200010, M = 40; int t, n, k, a[N], b[M], b1[M]; int main(void) { #ifdef _DEBUG freopen("1669h.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while (t--) { cin >> n >> k; memset(b1, 0, sizeof b1); memset(b, 0, sizeof b); For1(i, 1, n) { cin >> a[i]; int x = a[i], idx = 1; while (x) { if (x & 1) b1[idx]++; idx++; x >>= 1; } } For1(i, 1, 31) { b[i] = n - b1[i]; } Rof1(i, 1, 31) { if (k >= b[i]) { k -= b[i]; b[i] = 0; } } ll res = 0; Rof1(i, 1, 31) { res = res * 2 + (b[i] == 0); } cout << res << '\n'; } return 0; }