快排
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
void qsort(int left, int right) {
int l = left, r = right;
int mid = a[l + r >> 1];
while(l < r) {
while(a[l] < mid) l++;
while(a[r] > mid) r--;
if(l <= r) swap(a[l++], a[r--]);
}
if(left < r) qsort(left, r);
if(l < right) qsort(l, right);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
qsort(0, n - 1);
for(int i = 0; i < n; i++) cout << a[i] << ‘ ‘;
return 0;
}
高精度加法
#include<iostream>
#include<algorithm>
#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(t);
return c;
}
int main() {
vector<int> a, b;
string s1, s2;
cin >> s1 >> s2;
for(int i = s1.size() - 1; i >= 0; i--) {
a.push_back(s1[i] - ‘0‘);
}
for(int i = s2.size() - 1; i >= 0; i--) {
b.push_back(s2[i] - ‘0‘);
}
auto c = add(a, b);
for(int i = c.size() - 1; i >= 0; i--) cout << c[i];
return 0;
}
高精度减法
#include<iostream>
#include<algorithm>
#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);
if(t < 0) t = 1;
else t = 0;
}
while(c.size() > 1 && c.back() == 0) {
c.pop_back();
}
return c;
}
int main() {
string s1, s2;
vector<int> a, b;
cin >> s1 >> s2;
if(s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)) {
cout << ‘-‘;
swap(s1, s2);
}
for(int i = s1.size() - 1; i >= 0; i--) a.push_back(s1[i] - ‘0‘);
for(int i = s2.size() - 1; i >= 0; i--) b.push_back(s2[i] - ‘0‘);
auto c = sub(a, b);
for(int i = c.size() - 1; i >= 0; i--) cout << c[i];
return 0;
}
高精度乘法
#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> a, int b) {
vector<int> c;
int t = 0;
for(int i = 0; i < a.size(); i++) {
t = t + a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while(t) {
c.push_back(t % 10);
t /= 10;
}
while(c.size() > 1 && c.back() == 0){
c.pop_back();
}
return c;
}
int main() {
string s;
int x;
vector<int> a;
cin >> s >> x;
for(int i = s.size() - 1; i >= 0; i--) a.push_back(s[i] - ‘0‘);
auto ans = mul(a, x);
for(int i = ans.size() - 1; i >= 0; i--) cout << ans[i];
return 0;
}
高精度除法
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> a, int b, int& r) {
vector<int> c;
for(int i = 0; i < a.size(); 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 s;
int b;
vector<int> a;
cin >> s >> b;
for(int i = 0; i < s.size(); i++) a.push_back(s[i] - ‘0‘);
int r = 0;
auto c = div(a, b, r);
for(int i = c.size() - 1; i >= 0; i--) cout << c[i];
cout << endl << r;
return 0;
}
一维前缀和
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n, m;
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
a[i] = a[i - 1] + x;
}
while(m--) {
int l, r;
cin >> l >> r;
cout << a[r] - a[l - 1] << endl;
}
return 0;
}
二维前缀和
#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
int main() {
int n, m, k;
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int x;
cin >> x;
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + x;
}
}
while(k--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1] << endl;
}
return 0;
}
一维拆分
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
void insert(int l, int r, int c) {
a[l] += c;
a[r + 1] -= c;
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
insert(i, i, x);
}
while(m--) {
int l, r, c;
cin >> l >> r >> c;
insert(l, r, c);
}
for(int i = 1; i <= n; i++) {
a[i] += a[i - 1];
cout << a[i] << ‘ ‘;
}
return 0;
}
二维拆分
#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {
a[x1][y1] += c;
a[x2 + 1][y1] -= c;
a[x1][y2 + 1] -= c;
a[x2 + 1][y2 + 1] += c;
}
int main() {
int n, m, q;
cin >> n >> m >> q;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int x;
cin >> x;
insert(i, j, i, j, x);
}
}
while(q--) {
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1, y1, x2, y2, c);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
a[i][j] += a[i - 1][j] + a[i][j -1] - a[i -1][j - 1];
cout << a[i][j] << ‘ ‘;
}
cout << endl;
}
return 0;
}
双指针(最长连续不重复子序列)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int c[N];
int main() {
int n, ans = 0;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
for(int i = 0, j = 0; i < n; i++) {
c[a[i]]++;
while(c[a[i]] > 1) {
c[a[j]]--;
j++;
}
ans = max(ans, i - j + 1);
}
cout << ans;
return 0;
}
lowbit
#include<iostream>
using namespace std;
int lowbit(int x) {
return x & -x;
}
int main() {
int n;
cin >> n;
while(n--) {
int x;
cin >> x;
int ans = 0;
while(x) {
x -= lowbit(x);
ans++;
}
cout << ans << ‘ ‘;
}
return 0;
}
离散化
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 3e5 + 10;
int a[N];
vector<int> point;
vector<pair<int, int>> add, query;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, x, c, l, r;
cin >> n >> m;
while(n--) {
cin >> x >> c;
point.push_back(x);
add.push_back({x, c});
}
while(m--) {
cin >> l >> r;
point.push_back(l);
point.push_back(r);
query.push_back({l, r});
}
sort(point.begin(), point.end());
point.erase(unique(point.begin(), point.end()), point.end());
for(pair<int, int> item: add) {
int x = lower_bound(point.begin(), point.end(), item.first) - point.begin();
a[x + 1] += item.second;
}
for(int i = 1; i <= point.size(); i++) {
a[i] += a[i - 1];
}
for(pair<int, int> item: query) {
l = lower_bound(point.begin(), point.end(), item.first) - point.begin();
r = lower_bound(point.begin(), point.end(), item.second) - point.begin();
cout << a[r + 1] - a[l] << endl;
}
return 0;
}
区间合并
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<PII> v;
int main() {
int n, ans = 0;
cin >> n;
while(n--) {
int l, r;
cin >> l >> r;
v.push_back({l, r});
}
sort(v.begin(), v.end());
int start = v[0].first, end = v[0].second;
for(PII item: v) {
if(item.first <= end && item.second > end) {
end = item.second;
} else if(item.first > end) {
ans++;
start = item.first;
end = item.second;
}
}
ans++;
cout << ans;
return 0;
}
原文：https://www.cnblogs.com/bleso/p/14684746.html