#include<algorithm> #include<cstdio> using namespace std; const int N = 1e6 + 10; int n; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[l + r >> 1], i = l - 1, j = r + 1; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); // ^ 在[1,2]数组情况下x不能取右边界点，否则会陷入死循环 // quick_sort(q, l, i-1), quick_sort(q, i, r); // ^ 在[1,2]数组情况下x不能取左边界点，否则会陷入死循环 } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &q[i]); quick_sort(q, 0, n - 1); for (int i = 0; i < n; i++) printf("%d ", q[i]); return 0; }
#include<algorithm> #include<cstdio> #include<iostream> using namespace std; const int N = 1e5 + 10; int q[N]; void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[l + r >> 1], i = l - 1, j = r + 1; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); } int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } quick_sort(q, 0, n - 1); printf("%d", q[k - 1]); return 0; }
#include<cstdio> #include<iostream> using namespace std; const int N = 1e6 + 10; int n; int q[N], tmp[N]; void merge_sort(int q[], int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid), merge_sort(q, mid + 1, r); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; } while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } merge_sort(q, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", q[i]); } return 0; }
还要考虑逆序对数量，最大数 n * (n - 1) / 2 = 5 * 1e9 大于 INT_MAX，需要用 long long
#include<cstdio> #include<iostream> using namespace std; typedef long long LL; const int N = 1e6 + 10; int n; int q[N], tmp[N]; LL merge_sort_count(int q[], int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; int k = 0, i = l, j = mid + 1; LL count = merge_sort_count(q, l, mid) + merge_sort_count(q, mid + 1, r); while (i <= mid && j <= r) { if (q[i] <= q[j]) tmp[k++] = q[i++]; else { count += mid - i + 1; tmp[k++] = q[j++]; } } while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; for (int i = l, k = 0; i <= r; i++, k++) q[i] = tmp[k]; return count; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } cout << merge_sort_count(q, 0, n - 1); return 0; }
整数二分
整数二分的本质并不是单调性。本质是将区间一分为二，寻找边界点（左区间边界还是右区间边界）。
每次缩短区间一半，答案依旧在缩短的区间内，直到区间长度为1，此时就是边界点。
二分一定是有解的，此时 l==r，根据二分出来的边界点判断题目有没有解
左区间边界点
取中点mid = l+r+1 >> 1，判断该点是否符合左区间性质
如果成立说明mid在左区间，边界点在 [mid,r]，此时 l = mid
不成立说明mid不在左区间，边界点在 [l,mid-1]，此时 r = mid-1
右区间边界点
取中点mid = l+r >> 1，判断该点是否符合右区间性质
如果成立说明mid在右区间，边界点在 [l,mid]，此时 r = mid
不成立说明mid不在左区间，边界点在 [mid+1,r]，此时 l = mid+1
mid分子加1
性质成立条件中：l = mid ，加1；r = mid ，不加1
不加 1，当 l = r - 1 时，由于向下取整，mid = l，当性质条件成立， l = mid = l 死循环。加1后，mid = r，不会死循环。
#include<cstdio> #include<iostream> using namespace std; typedef long long LL; const int N = 1e6 + 10; int q[N]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } while (m--) { int k; cin >> k; // ^ 寻找右区间边界点 int l = 0, r = n - 1; while (l < r) { int mid = l + r >> 1; if (q[mid] >= k) r = mid; else l = mid + 1; } if (q[l] != k) { cout << "-1 -1" << endl; continue; } else cout << l << " "; l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (q[mid] <= k) l = mid; else r = mid - 1; } cout << r << endl; } return 0; }
#include<cstdio> #include<iostream> #include<vector> using namespace std; // 加引用符不用拷贝一遍效率更高 vector<int> add(vector<int>& A, vector<int>& B) { vector<int> C; int t = 0; for (int i = 0; i < A.size() || i < B.size(); i++) { if (i < A.size()) t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(1); return C; } int main() { string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); auto C = add(A, B); for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]); return 0; }
要保证 A >= B，如果B大，则算 -(B - A) ；如果 A、B 有负数，可以转换成 |A| - |B| 或 |A| + |B|。
#include<cstdio> #include<iostream> #include<vector> using namespace std; // 加引用符不用拷贝一遍效率更高 vector<int> sub(vector<int>& A, vector<int>& B) { vector<int> C; int t = 0; for (int i = 0; i < A.size(); i++) { t = A[i] - t; // 判断越界 if (i < B.size()) t -= B[i]; // ^ 两种情况合二为一 C.push_back((t + 10) % 10); t = t < 0 ? 1 : 0; } // ^ 去掉前导0 while (C.size() > 1 && C.back() == 0) { C.pop_back(); } return C; } // 判断 A>=B bool cmp(vector<int>& A, vector<int>& B) { if (A.size() > B.size()) return true; else if (A.size() < B.size()) return false; else for (int i = A.size() - 1; i >= 0; i--) { if (A[i] != B[i]) return A[i] > B[i]; } return true; } int main() { string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0'); if (cmp(A, B)) { auto C = sub(A, B); for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]); } else { auto C = sub(B, A); cout << '-'; for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]); } return 0; }
#include<cstdio> #include<iostream> #include<vector> using namespace std; vector<int> mul(vector<int> A, int b) { if (b == 0) return vector<int>{0}; vector<int> C; int t = 0; // 进位 for (int i = 0; i < A.size() || t; i++) { if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } return C; } int main() { string a; int b; cin >> a >> b; vector<int> A; for (int i = a.size() - 1; i >= 0; i--) { A.push_back(a[i] - '0'); } auto C = mul(A, b); for (int i = C.size() - 1; i >= 0; i--) cout << C[i]; return 0; }
#include<algorithm> #include<cstdio> #include<iostream> #include<vector> using namespace std; // A / b 商 C 余 r vector<int> div(vector<int> A, int b, int& r) { vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; i--) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main() { string a; int b; cin >> a >> b; vector<int> A; for (int i = a.size() - 1; i >= 0; i--) { A.push_back(a[i] - '0'); } int r; auto C = div(A, b, r); for (int i = C.size() - 1; i >= 0; i--) cout << C[i]; cout << endl << r << endl; return 0; }
#include<cstdio> #include<iostream> using namespace std; const int N = 1e6 + 10; int s[N]; int main() { int n, m; cin >> n >> m; int a; for (int i = 1; i <= n; i++) { scanf("%d", &a); s[i] = a + s[i - 1]; } while (m--) { int l, r; cin >> l >> r; cout << s[r] - s[l - 1] << endl; } return 0; }
#include<cstdio> #include<iostream> using namespace std; const int N = 1e6 + 10; int a[N], b[N]; void insert(int l, int r, int c) { b[l] += c; b[r + 1] -= c; } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } // 前缀和转差分 for (int i = 1; i <= n; i++) { insert(i, i, a[i]); } int l, r, c; while (m--) { scanf("%d%d%d", &l, &r, &c); insert(l, r, c); } // 差分转前缀和 for (int i = 1; i <= n; i++) b[i] += b[i - 1]; for (int i = 1; i <= n; i++) cout << b[i] << " "; return 0; }
#include<algorithm> #include<cstdio> #include<iostream> using namespace std; const int N = 1e6 + 10; int a[N], b[N]; int main() { int n, m, x; cin >> n >> m >> x; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } for (int i = 0; i < m; i++) { scanf("%d", &b[i]); } for (int i = 0, j = m - 1; i < n && a[i] < x; i++) { while (j >= 0 && b[j] > x - a[i]) j--; if (a[i] + b[j] == x) { cout << i << " " << j; break; } } return 0; }
由于堆数组初始化默认为0，如下输入会导致 i 最终为 2(i) 而不是 1(n)，在最后的判断中输出 No。因此向右移动 i 时需要添加一个 i<n 的条件，避免将数组外元素纳入判断。
12110
#include<algorithm> #include<cstdio> #include<iostream> using namespace std; const int N = 1e6 + 10; int a[N], b[N]; int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } for (int i = 0; i < m; i++) { scanf("%d", &b[i]); } // i 是 a 指针，j 是 b 指针 int i, j; for (i = 0, j = 0; j < m; j++) { if (i < n && a[i] == b[j]) i++; // 注意 i < n } if (i == n) cout << "Yes"; else cout << "No"; return 0; }
位运算
原码、反码、补码
原码 x = 00001010
反码 x = 11110101
补码 x = 11110110 （反码+1）
计算机底层实现没有减法，只能用加法来做减法
求某一位数字
int i = a >> 2 & 1;
返回最后一位1 lowbit
a & (~a + 1) // 0000001000 // 整数x的负数是取反x后加1 // -a 等同 ~a+1 a & -a
#include<algorithm> #include<cstdio> #include<iostream> using namespace std; const int N = 1e5 + 10; int a[N]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } for (int i = 0; i < n; i++) { int count = 0; while (a[i]) { a[i] -= a[i] & -a[i]; count++; } cout << count << " "; } return 0; }
#include<algorithm> #include<cstdio> #include<iostream> #include<vector> using namespace std; typedef pair<int, int> PII; const int N = 3e5 + 10; // 差分 int s[N]; vector<int> alls; vector<PII> add, query; int find(int x) { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return l + 1; } int main() { int n, m; cin >> n >> m; while (n--) { int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x); } for (int i = 0; i < m; i++) { int l, r; cin >> l >> r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } // 去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 插入 for (auto item : add) { int x = find(item.first); s[x] += item.second; } // 差分转前缀和 for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + s[i]; // 处理询问 for (auto item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; }
unique
本质上是第一类双指针算法
#include<algorithm> #include<cstdio> #include<iostream> #include<vector> using namespace std; vector<int> a; // a 升序序列，i 指针存放当前位置，j 遍历整个数组 vector<int>::iterator unique(vector<int>& a) { int i = 0; for (int j = 0; j < a.size(); j++) { if (!j || a[j - 1] != a[j]) a[i++] = a[j]; } // a[0~i-1] 所有不同的数 return a.begin() + i; } // vector<int>::iterator unique(vector<int>& a) { // int i = 1; // for (int j = 0; j < a.size(); j++) { // if (a[i - 1] != a[j]) a[i++] = a[j]; // } // // a[0~i-1] 所有不同的数 // return a.begin() + i; // } int main() { int n; cin >> n; for (int i = 0, x; i < n; i++) { scanf("%d", &x); a.push_back(x); } sort(a.begin(), a.end()); auto x = unique(a); for (int i = 0; i < x - a.begin(); i++) { cout << a[i] << " "; } return 0; }
