preface
- 🌰 Welcome to OpenAll_Zzz's blog, here we work together and make progress together!
- 🎁 The content shared in this issue is a little huge - algorithm. It mainly shares the very stable algorithm template, which mainly helps the author review and use.
- 📝 If you have doubts about an algorithm template, please post your questions in the comment area.
- 🎄 The content of this article is OpenAll_Zzz original, reprinted small partners, please also mark the source.
- 📃 This article began on December 4, 2021 and was last updated on December 12, 2021.
- 🎁 Welcome to comment 📖, forward 📤, follow 👓， If the article is helpful to you, I hope I can get a great praise from you 👍.
Chapter 1 basic algorithm
1.1 quick sort
Fast scheduling is the best overall performance among many sorts.
C + + template
#include <iostream>
using namespace std;
const int N = 10e6 + 10; // Test the data volume of one million, Accepted.
int n;
int q[N];
// Current fast scheduling template (very stable)
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; // Select the middle value as the dividing point
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()
{
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;
}
1.1. 1. Number k of related exercises
#include <iostream>
using namespace std;
const int N = 100010;
int n, k;
int q[N];
int quick_select(int l, int r, int k) // The fast selection algorithm uses the idea of fast scheduling
{
if(l == r) return q[l];
int x = q[l + r >> 1], 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);
}
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i ++) scanf("%d", &q[i]);
cout << quick_select(0, n - 1, k) << endl;
return 0;
}
1.2 merge sort
C + + template
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10e6 + 10;
int n;
int q[N], tmp[N];
void meger_sort(int* q, int l, int r)
{
if(l >= r) return;
int mid = l + r >> 1;
meger_sort(q, l, mid), meger_sort(q, mid + 1, r); // "Division" of divide and conquer
int k = 0, i = l, j = mid + 1; // "Rule" of divide and conquer
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j ++];
}
// Finishing
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];
// Integrate into the original array to make it partially ordered, and then merge it
for(i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &q[i]);
meger_sort(q, 0, n - 1);
for(int i = 0; i < n; i++) printf("%d ", q[i]);
return 0;
}
1.2. 1 related exercise: number of pairs in reverse order
C + + code
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N];
LL meger_sort(int l, int r)
{
if(l == r) return 0;
int mid = l + r >> 1; // +Priority number is higher than > >
LL res = meger_sort(l, mid) + meger_sort(mid + 1, r);
// The process of merging ([l, mid] and [mid + 1, r] are ordered)
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
{
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else
{
tmp[k ++] = q[j ++];
// In the process of merging, if a number x in the first half is greater than a number y in the second half, then all the numbers after X are greater than y, then the reverse order pair of Y is
// Mid - I + 1 (mid is the right endpoint of the first half)
res += mid - i + 1;
}
}
// Finishing
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];
// tmp array is returned to the original array q to make it ordered in the interval [l, r]
for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
cout << meger_sort(0, n - 1) << endl;
return 0;
}
1.3 two points
1.3. 1 integer dichotomy
C + + template
bool check(int x) {/* ... */} // Check whether x satisfies a certain property
// When the interval [l, r] is divided into [l, mid] and [mid + 1, r], use:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check() determines whether the mid satisfies the property
else l = mid + 1;
}
return l;
}
// The interval [l, r] is divided into [l, mid - 1] and [mid, r]:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; // When l is mid, you need to set mid to l + r + 1 / 2, otherwise it will be dead circulation (when l=r-1)
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
1.3. 1.1 related exercises: range of numbers
C + + code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10e6 + 10;
int n, T, x;
int q[N];
int main()
{
scanf("%d%d", &n, &T);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
while(T --)
{
scanf("%d", &x);
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(q[mid] >= x) r = mid;
else l = mid + 1;
}
if(q[l] != x) cout << "-1 -1" << endl;
else{
cout << l << " ";
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1>> 1;
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
1.3. 2 floating point binary
C + + template
bool check(double x) {/* ... */} // Check whether x satisfies a certain property
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps indicates accuracy, which depends on the accuracy requirements of the subject
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
1.3. 2.1 related exercises: the cubic root of numbers
C + + code
#include <iostream>
using namespace std;
int main()
{
double x;
cin >> x;
double l = -100, r = 100; // double %lf; float %f.
while(r - l > 1e-8)
{
double mid = (l + r) / 2;
if(mid * mid * mid >= x) r = mid;
else l = mid;
}
printf("%.6lf", l);
return 0;
}
1.4 high precision simulation
1.4. 1 high precision addition
C + + template
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int>& A, vector<int>& B)
{
vector<int> C;
int t = 0; // Define the carry variable, which is initially 0, because the first bit is the first bit to generate the carry, and the carry is generated when calculating the previous bit.
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); // Calculate the added value of each bit
t /= 10; // Calculate carry
}
if(t) C.push_back(t);
return C;
}
int main()
{
vector<int> A, B;
string 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 --) cout << C[i];
return 0;
}
// 1. High precision addition focuses on converting large numbers into array representation
// 2. Use the number of bits of each bit of the array to simulate manual addition
// 3. Consider the carry of each bit and the final boundary condition, that is, the last bit may need carry
1.4. 2 high precision subtraction
C + + template
#include <iostream>
#include <vector>
using namespace std;
// Judge whether there is a > = b
bool cmp(vector<int>& A, vector<int>& B)
{
if(A.size() != B.size()) return A.size() > B.size();
else{
for(int i = A.size() - 1; i >= 0; i--) // Judge from high position
{
if(A[i] != B[i]) return A[i] > B[i];
}
}
return true;
}
// Subtraction is simulated from the low position, which is consistent with manual calculation
vector<int> sub(vector<int>& A, vector<int>& B) // A > = b
{
vector<int> C;
for(int i = 0, t = 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(); // Eliminate leading 0
return C;
}
int main()
{
string a, b;
cin >> a >> b;
vector<int> 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');
vector<int> C;
if(cmp(A, B))
{
C = sub(A, B);
}
else {
C = sub(B, A);
printf("-");
}
for(int i = C.size() - 1; i >= 0; i-- ) cout << C[i];
return 0;
}
1.4. 3 high precision multiplication
C + + template
#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A, int b) // A * b A is a large number and b is small
{
vector<int> C;
for(int i = 0, t = 0; i < A.size() || t; i++)// Multiplication is calculated from the lowest order, which is consistent with the manual multiplication of two numbers
{
if(i < A.size()) t += A[i] * b; // Note that the bit by bit carry of multiplication will be realized only when + =
C.push_back(t % 10);
t /= 10;
}
while(C.size() > 1 && C.back() == 0) C.pop_back(); // Remove leading 0
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;
}
1.4. 4 high precision Division
C + + template
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> div(vector<int>& A, int b, int& r) // A / B: C is quotient, r is quotient
{
vector<int> C;
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()); // Keep the form consistent and facilitate the removal of leading 0
while(C.size() > 1 && C.back() == 0) C.pop_back(); // Remove leading 0
return C;
}
int main()
{
string a;
int b;
vector<int> A;
cin >> a >> b;
for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[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;
}
1.5 prefix and difference
Prefix sum and difference are a set of reciprocal relations
For example, array a = {1, 3, 4, 6, 8}, whose prefix and array are s = {1, 4, 8, 14, 22}
At this time, the prefix of a and the array are s, and the differential array of S (starting from the second term, each term minus the value of the previous term) is a
1.5. 1 related exercise: prefix and (one-dimensional prefix and)
C + + code
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int s[N]; // You can modify the original array directly to reduce the memory overhead of array a
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) scanf("%d", &s[i]);
for(int i = 1; i <= n; i ++) s[i] += s[i - 1]; // Calculate prefix and original -- s[i] = s[i - 1] + a[i]
while(m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
1.5. 2 related exercise: sum of submatrix (two-dimensional prefix and)
C + + code
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int s[N][N];
int main()
{
scanf("%d%d%d", &n,&m,&q);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d",&s[i][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) // Original -- s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; // Calculate prefix and
while(q --)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 -1][y2] + s[x1 -1][y1 - 1]); // Calculation part and
}
return 0;
}
1.5. 3 related exercises: difference (one-dimensional difference)
The core of difference is to insert the original array to construct the difference group
The difference fraction group can be added and transformed to the original array
C + + code
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c) // Insert in one-dimensional difference group
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
scanf("%d%d", &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]; // To calculate the prefix and the a array, you don't have to
}
for(int i = 1; i <= n; i ++) cout << b[i] << ' ';
return 0;
}
1.5. 4 related exercise: difference matrix (two-dimensional difference)
C + + code
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) // Draw a matrix to understand
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
// for(int i = 1; i <= n; i ++)
// for(int j = 1; j <= m; j ++)
// scanf("%d", &b[i][j]); // In fact, you don't need the a array, you can operate the difference fraction group B in place
int x = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
cin >> x;
insert(i, j, i, j, x); // Insert in the difference group b
}
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 ++)
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; // Calculating the prefix sum of itself becomes the original array
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++) printf("%d ", b[i][j]); // At this point, the b array is the original array
puts("");// Put function wrap
}
return 0;
}
1.6 double pointer
Double pointer is an optimization idea, which optimizes the time complexity by reducing the dimension of the problem.
It is usually optimized into a double pointer algorithm by virtue of the monotonicity, uniqueness and verifiability of the problem
1.6. 1. Longest continuous non repeating subsequence of related exercises
C + + code
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N], s[N];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
// If the added number a[i] causes repetition, we can only
// The repeated number a[i] is removed by reducing the number of numbers in the interval
// That is, j + +, and reduce the number of a[j] in the count array at the same time
int res = 0;
for(int i = 0, j = 0; i < n; i ++)
{
s[a[i]] ++; // It will only be the addition of a[i] that leads to repetition
while(s[a[i]] > 1)
{
s[a[j]] --;
j ++; // When i == j, there is only one number in the interval, and the cycle ends without out of bounds
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}
1.6. 2. Practice the objectives and of array elements
C + + code
#include <iostream>
using namespace std;
const int N = 100010;
int n, m, x;
int A[N], B[N];
int main()
{
scanf("%d%d%d", &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; i ++) // The second pointer points to the end of the array, maintaining monotonicity
{
while(j >= 0 && A[i] + B[j] > x) j --;
if(A[i] + B[j] == x)
{
printf("%d %d\n", i, j);
break;
}
}
return 0;
}
1.6. 3. Relevant exercise judgment subsequence
C + + code
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
for(int i = 0; i < m; i ++) scanf("%d", &b[i]);
int i = 0, j = 0;
while(i < n && j < m) // Verifiability: when the numbers found by the double pointer match, it will not affect whether the subsequent numbers are matched
{
if(a[i] == b[j]) i ++;
j ++;
}
if(i == n) puts("Yes");
else puts("No");
return 0;
}
1.7 bit operation
The content of bit operation is relatively single, and there are only two core operations.
🌰 1. Get the number of the k-th bit in a binary bit: x > > k & 1
🌰 2. Return the last binary bit starting with 1 (lowbit function): X & - X.
PS: - x = = ~ x + 1 (the negative number of a number is equal to its bitwise negation plus one)
stay 🌰 2. After x is inversed and 1 is added, the binary bits on the left of the last 1 in x are opposite to the original, and the binary bits on the right of the last 1 in x are all 0. After operation with (&), the result can be obtained.
1.7. 1 the number of 1 in the binary of related exercises
C + + code
#include <iostream>
using namespace std;
int lowbit(int x)
{
return x & -x;
}
int main()
{
int n;
cin >> n;
while(n --)
{
int x;
scanf("%d", &x);
int res = 0;
while(x) res ++, x -= lowbit(x);
cout << res << ' ';
}
return 0;
}
1.8 discretization
🌰 Discretization refers to operating a group of data with a particularly large data range on the number axis, but the number of operating them is much smaller than their range.
📃 That is, we need to operate on a large amount of data (of course, it is much smaller than their data range). We need to use arrays to store them
📃 We need to find a way to store this set of data. The idea of this method is discretization. (similar to the idea of hash mapping)
1.8. 1 relevant practice intervals and
C + + code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N]; // Discretized array, its prefix and
vector<int> alls; // All points to be discretized on the number axis
vector<PII> add, query; // Added information and queried information
int find(int x) // The order from small to large is used as the mapping value and as the coordinates in the discretized array
{
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 r + 1;
}
int main()
{
scanf("%d%d", &n, &m);
// Read in the points and values to be added
for(int i = 0; i < n; i ++)
{
int x, c;
scanf("%d%d", &x, &c);
alls.push_back(x);
add.push_back({x, c});
}
// Read in query interval
for(int i = 0; i < m; i ++)
{
int l, r;
scanf("%d%d", &l, &r);
alls.push_back(l);
alls.push_back(r);
query.push_back({l, r});
}
// Discretization
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
// Add operation
for(auto item : add)
{
int x = find(item.first);
a[x] += item.second;
}
// Preprocessing prefix and
for(int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];
// Process each query
for(auto item : query)
{
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}