AcWing
学习笔记
AcWing 785. 快速排序
1
2
3
4
5
6
7
8
9
10
|
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);
}
|
AcWing 786. 第k个数
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int q[N];
int quick_select(int l, int r, int k) { // 在[l, r]查找第k大的数
if (l >= r) return q[l];
int x = q[l], i = l - 1, j = r + 1;
while (i < j) {
while (q[++i] < x);
while (q[--j] > x);
if (i < j) swap(q[i], q[j]);
}
int sl = j - l + 1;
if (k <= sl) return quick_select(l, j, k);
return quick_select(j + 1, r, k - sl);
}
|
AcWing 787. 归并排序 AcWing 788. 逆序对的数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int q[N], t[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 k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (q[i] < q[j]) t[k++] = q[i++];
else t[k++] = q[j++]; // res += mid - i + 1; res为逆序对的数量
}
while (i <= mid) t[k++] = q[i++];
while (j <= r) t[k++] = q[j++];
for (int i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
}
|
AcWing 789. 数的范围
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
bool check(int x) {};
int bsearch_1(int l, int r) {
while(l < r) {
int mid = (long long)l + r >> 1;
if(check[mid]) r = mid;
else l = mid + 1;
}
return l;
}
int bsearch_2(int l, int r) {
while(l < r) {
int mid = l + r + 1ll >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
|
AcWing 790. 数的三次方根
1
2
3
4
5
6
7
8
9
10
11
12
|
const double eps = 1e-6;
bool check(double x) {};
double bsearch_3(double l, double r) {
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
|
# define vint vector<int>
#define pb push_back
AcWing 791. 高精度加法
1
2
3
4
5
6
7
8
9
10
|
vint add(vint &a, vint &b) {
vint c;
for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++) {
if (i < a.size()) t += a[i];
if (i < b.size()) t += b[i];
c.pb(t % 10);
t /= 10;
}
return c;
}
|
AcWing 792. 高精度减法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
bool isgreater(vint &a, vint &b) {
if (a.size() != b.size()) return a.size() > b.size();
return vint(a.rbegin(), a.rend()) > vint(b.rbegin(), b.rend());
}
// 使用条件：a > b
vint sub(vint &a, vint &b) {
vint c;
for (int i = 0, t = 0; i < a.size(); i++) {
t = a[i] - t;
if (i < b.size()) t -= b[i];
c.pb((t + 10) % 10);
if (t >= 0) t = 0;
else t = 1;
}
while (c.back() == 0 && c.size() > 1) c.pop_back();
return c;
}
|
AcWing 793. 高精度乘法
1
2
3
4
5
6
7
8
9
|
vint mul(vint &a, int b) {
vint c;
for (int i = 0, t = 0; i < a.size() || t; i++) {
if (i < a.size()) t += a[i] * b;
c.pb(t % 10);
t /= 10;
}
return c;
}
|
AcWing 794. 高精度除法
1
2
3
4
5
6
7
8
9
10
11
12
|
vint div(vint a, int b, int &r) {
vint c;
r = 0;
for (int i = a.size() - 1; i >= 0; i--) {
r = r * 10 + a[i];
c.pb(r / b);
r %= b;
}
reverse(c.begin(), c.end());
while (c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
|
AcWing 795. 前缀和
S[i] = a[1] + a[2] +...+ a[i]
sum[l,r] = a[l] +···+ a[r] = S[r] - S[l-1]
AcWing 796. 子矩阵的和
前缀和S[i, j]：
S[i,j]=S[i,j-1]+S[i-1,j]-S[i-1,j-1]+a[i,j]
(x1,y1),(x2,y2)子矩阵之和为：
S[x2,y2]-S[x1-1,y2]-S[x2,y1-1]+S[x1-1,y1-1]
AcWing 797. 差分
给定原数列a[]，构造差分数列b[],使得a[i] = b[1] + b[2] +... + b[i]
核心操作insert：将a[l~r]全部加上c，等价于：b[l] += c, b[r + 1] -= c
一般假定初始b[]全为0，用insert(i, i, a[i])即可构造出b[]
AcWing 798. 差分矩阵
给定原矩阵a[][]，构造差分矩阵b[][]，使得a[][]是b[][]的二维前缀和。
核心操作insert：给以(x1,y1),(x2,y2)子矩阵中的所有数a[i][j]加上c，等价于b[x1][y1] += c,b[x2 + 1][y1] -= c, b[x1][y2 + 1] -= c, b[x2 + 1][y2 +1] += c;
一般用insert(i, j, i, j, a[i][j])即可构造出b[][]
AcWing 802. 区间和
1
2
3
4
5
6
7
8
9
10
11
12
13
|
vector<int> alls;
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
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; // 映射到1.2.3...
}
|