夜雨聆风https://github.com/dcjaychou-design/acm-icpc-cpp17-reference1 子集枚举
1.1 枚举0 ∼ 2n - 1
int n;for (int mask = 0; mask < (1 << n); ++mask){for (int i = 0; i < n; ++i){if (mask >> i & 1){// choose i}}}
1.2 枚举一个集合的所有子集
for (int sub = mask; ; sub = (sub - 1) & mask){//subisasubsetofmaskif (sub == 0) break;}
1.3 Meet-in-the-Middle 思路
当 n 约为 40，直接 2n 不现实，可拆成两半分别枚举，再排序或双指针合并。
2 一维前缀和
vector<long long> pre(n + 1, 0);for (int i = 1; i <= n; ++i)pre[i] = pre[i - 1] + a[i];longlongsunRange(int l, int r)return pre[r] - pre[l - 1];
3 二维前缀和
vector<vector> s(n + 1, vector(m + 1, 0));for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];long long sumRect(int x1, int y1, int x2, int y2){return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];}
4 差分
4.1 一维差分
vector diff(n + 2, 0);auto addRange = [&](int l, int r, long long v){diff[l] += v;diff[r + 1] -= v;};for (int i = 1; i <= n; ++i){diff[i] += diff[i - 1];a[i] += diff[i];}
4.2 二维差分
vector<vector> d(n + 2, vector(m + 2, 0));auto addRect = [&](int x1, int y1, int x2, int y2, long long v){d[x1][y1] += v;d[x2 + 1][y1] -= v;d[x1][y2 + 1] -= v;d[x2 + 1][y2 + 1] += v;};for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];a[i][j] += d[i][j];}}
5 离散化
vector xs = raw;sort(xs.begin(), xs.end());xs.erase(unique(xs.begin(), xs.end()), xs.end());auto getId = [&](long long x){return int(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1;};
6 双指针与滑动窗口
6.1 最长满足约束的区间
适合“连续子数组”且窗口条件随左右端点单调变化。
int l = 0, ans = 0;long long sum = 0;for (int r = 0; r < n; ++r){sum += a[r];while (l <= r && sum > limit)sum -= a[l++];ans = max(ans, r - l + 1);}
6.2 有序数组去重式双指针
sort(a.begin(), a.end());int j = 0;for (int i = 0; i < n; ++i)if (i == 0 || a[i] != a[i - 1])a[j++] = a[i];a.resize(j);
7 区间合并
vector<pair<int,int>> segs;sort(segs.begin(), segs.end());vector<pair<int,int>> merged;for (auto [l, r] : segs){if (merged.empty() || merged.back().second < l)merged.push_back({l, r});elsemerged.back().second = max(merged.back().second, r);}
8 整数二分
8.1 找第一个满足条件的位置
条件形如 false, false, false, true, true。
int l = 0, r = n; // answer in [0, n]while (l < r){int mid = l + (r - l) / 2;if (check(mid)) r = mid;else l = mid + 1;}// l is first satisfying position
8.2 找最后一个满足条件的位置
条件形如 true, true, true, false, false。
int l = 0, r = n; // answer in [0, n]while (l < r){int mid = l + (r - l + 1) / 2;if (check(mid)) l = mid;else r = mid - 1;}// l is last satisfying position
9 二分答案
先确定答案区间。
写出只回答“能不能”的 check(mid)。
验证单调性，再决定找第一个还是最后一个。
long long l = 0, r = 1e18;while (l < r){long long mid = l + (r - l) / 2;if (check(mid)) r = mid;else l = mid + 1;}cout << l << '\n';
10 浮点二分
double l = 0, r = 1e9;for (int it = 0; it < 100; ++it){double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}cout << fixed << setprecision(10) << r << '\n';
