AcWing basic algorithm (2) notes

Try not to become a man of success but rather try to become a man of value. — Albert Einstein

High precision addition

General high-precision problems are usedAn array ofIn the form ofReverse orderStore each bit of a number
Reverse orderBecause it’s easy to carry

Addition template

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(a); i ++ ) { 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;
}
Copy the code

AcWing 791. High precision addition

Core: t = A[I] + B[I] + CARRY Current bit = t % 10 CARRY = t / 10

Given two positive integers, calculate their sum. The input format consists of two lines, each containing an integer. The output format is a single line containing the sum. Data range 1≤ Integer length ≤100000 Input example: 12 23 Output example: 35Copy the code

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size () < B.size()) return add(B, A);
    
    vector<int> c;
    int t = 0; / / carry
    
    for (int i = 0; i < A.size(a); i++) { 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(a)
{
    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');
    
    auto c = add(A, B);
    for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    return 0;
}
Copy the code

High precision subtraction

Subtraction template

// C = a-b, A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(a); 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(a) >1 && C.back() = =0) C.pop_back(a);return C;
}
Copy the code

AcWing 792. High precision subtraction

Core: t = A[I] -b [I] -carry current bit = t < 0? (t + 10) : whether t is borrowed: t < 0? 1:0

Given two positive integers and calculate their difference, the result may be negative. The input format consists of two lines, each containing an integer. The output format is a single line containing the desired difference. Data range 1≤ Integer Length ≤105 Input example: 32 11 Output example: 21Copy the code

#include <iostream>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size(a);for (int i = A.size() - 1; i >= 0; i--)
    {
        if(A[i] ! = B[i])return A[i] > B[i];
    }
    return true;
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < A.size(a); i++) { t = A[i] - t;if (i < B.size()) t -= B[i];
        c.push_back((t + 10) % 10);
        t = t < 0 ? 1 : 0;
    }
    while (c.size(a) >1 && c.back() = =0) c.pop_back(a);return c;
}

int main(a)
{
    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
    {
        printf("-");
        c = sub(B, A);
    }
    for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    return 0;
}
Copy the code

High precision multiplication

High precision times low precision template

// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    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;
    }

    while (C.size(a) >1 && C.back() = =0) C.pop_back(a);return C;
}
Copy the code

AcWing 793. High precision multiplication

Core: t = A[I] * b + CARRY Current bit = t % 10 CARRY = t / 10

Given two positive integers A and B, calculate the value of A * B. The input format consists of two lines. The first line contains the integer A and the second line contains the integer B. The output format is one line containing the values of A * B. Data range 1≤ Length of A ≤100000, 0≤B≤10000 Input example: 2 3 Output example: 6Copy the code

#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(a); i++) { t += A[i] * b; c.push_back(t % 10);
        t /= 10;
    }
    if (t) c.push_back(t);
    while (c.size(a) >1 && c.back() = =0) c.pop_back(a);return c;
}

int main(a)
{
    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--) printf("%d", c[i]);
    return 0;
}
Copy the code

High precision division

High precision divided by low precision template

// A / b = C ... r, A >= 0, b > 0
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(a) >1 && C.back() = =0) C.pop_back(a);return C;
}
Copy the code

AcWing 793. High precision division

Core: t = r * 10 + A[I] current bit = t/b remainder r = t % b

Given two non-negative integers A, B, compute the quotient and remainder of A/B. The input format consists of two lines. The first line contains the integer A and the second line contains the integer B. The output format is two lines. The first line outputs the quotient and the second line outputs the remainder. Data range 1≤ Length of A ≤100000, 1≤B≤10000 B must not be 0. Input example: 7 2 Output example: 3 1Copy the code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> c;
    r = 0;
    
    // Division starts at the high level
    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(a) >1 && c.back() = =0) c.pop_back(a);return c;
}

int main(a)
{
    string a;
    int b, r;
    cin >> a >> b;
    
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    
    auto c = div(A, b, r);
    for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    puts("");
    cout << r << endl;
    return 0;
}
Copy the code

The prefix and

Prefix sum: s[I] is the sum of elements from 1 to I
Function: To find the sum of elements in the range [L, r] in O(1) time

One-dimensional prefixes and templates

S[i] = a[1] + a[2] +... a[i] a[l] + ... + a[r] = S[r] - S[l -1]
Copy the code

AcWing 795. Prefix and

Enter a sequence of integers of length N. Then enter m more queries, each with a pair of l and R. For each query, the sum from the l to r numbers in the original sequence is printed. The first line of the input format contains two integers n and m. The second row contains n integers, representing the integer sequence. The next m lines, each containing two integers L and r, represent the range of an inquiry. The output format is m lines, and each line outputs the result of one query. Data range 1≤ L ≤ R ≤ N, 1≤ N,m≤100000, −1000≤ Value of elements in the sequence ≤1000 Input example: 5 3 2 1 3 6 4 1 2 1 3 2 4 Output example: 3 6 10Copy the code

#include <iostream>

using namespace std;

int const N = 100010;

int a[N], s[N];

int main(a)
{
    int n, m;
    cin >> n >> m;
    
    // We can use the s[N] array directly, instead of borrowing a[N], mainly for easy comprehension
    for (int i = 1; i <= n; i++) cin >> a[i];
    // Prefixes and preprocessing
    for (int i = 1; i <= n; i++) s[i] += s[i - 1] + a[i];
    
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}
Copy the code

Two-dimensional prefixes and templates

S[I, j] = the sum of all elements in the upper left part of the lattice of column J of row I with (x1, y1) as the upper left corner and (x2, y2) as the lower right corner of the submatrix is: S[x2, y2] -s [x1 -1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
Copy the code

AcWing 796. Sum of submatrices

Enter a matrix of n rows and m columns of integers, followed by q queries, each containing four integers x1, y1, x2, y2, representing the upper-left and lower-right coordinates of a submatrix. Output the sum of all numbers in the submatrix for each query. The first line of the input format contains three integers n, m, and q. The next n rows, each containing m integers, represent the integer matrix. The next q line, each containing four integers x1, y1, x2, y2, represents a set of queries. Output format a total of Q lines, each line output one query result. Data range 1≤ N, M ≤1000, 1≤ Q ≤200000, 1≤ X1 ≤ X2 ≤ N, 1≤ Y1 ≤ Y2 ≤m, −1000≤ Values of elements in the matrix ≤1000 Input example: 3 4 3 17 2 4 3 6 2 8 21 2 3 1 1 2 2 21 3 4 1 3 3 4 Example output: 17 27 21Copy the code

#include <iostream>

using namespace std;

int const N = 1010;
int a[N][N], s[N][N];

int main(a)
{
    int n, m, q;
    cin >> n >> m >> q;
    
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    // s[I][J]
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    }
    
    while (q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        printf("%d\n", s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}
Copy the code

The differential

a[i] = b[1] + b[2] + … + b[i]
A is the prefix sum of B, and B is the difference of A
Function: in O(1) time to operate on [L, r] range of numbers

One-dimensional difference template

Add c: B[l] += c, B[r + to each number in the interval [l, r]1] -= c
Copy the code

Acwing 797. Difference

Enter a sequence of integers of length N. Next, enter m operations, each containing three integers L, r, c, to add c to each number between [l, r] in the sequence. Print the sequence after all the operations have been done. The first line of the input format contains two integers n and m. The second line contains n integers, representing a sequence of integers. The next m lines, each containing three integers L, R, and c, represent an operation. The output format is a single line containing N integers, representing the final sequence. Data range 1≤ N, M ≤100000, 1≤ L ≤ R ≤ N, −1000≤ C ≤1000, −1000≤ Value of the elements in the integer sequence ≤1000 Input example: 6 3 1 2 2 1 2 1 3 1 3 5 1 1 6 1 Output example: 3 4 5 3 4 2Copy the code

#include <iostream>

using namespace std;

int const N = 100010;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main(a)
{
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) insert(i, i, a[i]);
    
    while (m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    
    // Get the prefix and array for b[I]
    for (int i = 1; i <= n; i++) b[i] += b[i - 1];
    for (int i = 1; i <= n; i++) printf("%d ", b[i]);
    return 0;
}
Copy the code

Two dimensional difference template

Add c: S[x1, y1] += c, S[x2 + to the submatrix with (x1, y1) as the upper-left corner and (x2, y2) as the lower-right corner1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
Copy the code

AcWing 798. Difference matrix

Enter a matrix of n rows and m columns of integers, followed by q operations, each containing five integers x1, y1, X2, y2, c, where (x1, y1) and (x2, y2) represent the upper-left and lower-right coordinates of a submatrix. Each operation adds c to the value of each element in the selected submatrix. You will perform all operations after the matrix output. The first line of the input format contains the integers n,m,q. The next n rows, each containing m integers, represent the integer matrix. The next q line, each containing five integers x1, y1, x2, y2, c, represents an operation. The output format consists of N lines, each line contains m integers, representing the final matrix after all operations are completed. Data range 1≤ N, M ≤1000, 1≤ Q ≤100000, 1≤ X1 ≤ X2 ≤ N, 1≤ Y1 ≤ Y2 ≤m, −1000≤ C ≤1000, −1000≤ Values of elements in the matrix ≤1000 Input example: 3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 2 2 1 1 3 2 2 3 1 3 4 1 Example output: 2 3 4 1 4 3 4 1 2 2 2 2 2 2Copy the code

#include <iostream>

using namespace std;

int const N = 1010;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main(a)
{
    int n, m, q;
    cin >> n >> m >> q;
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) insert(i, j, i, j, a[i][j]);
    }
    
    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];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) printf("%d ", b[i][j]);
        puts("");
    }
    return 0;
}
Copy the code

High precision addition

Addition template

AcWing 791. High precision addition

High precision subtraction

Subtraction template

AcWing 792. High precision subtraction

High precision multiplication

High precision times low precision template

AcWing 793. High precision multiplication

High precision division

High precision divided by low precision template

AcWing 793. High precision division

The prefix and

One-dimensional prefixes and templates

AcWing 795. Prefix and

Two-dimensional prefixes and templates

AcWing 796. Sum of submatrices

The differential

One-dimensional difference template

Acwing 797. Difference

Two dimensional difference template

AcWing 798. Difference matrix

Related Posts

Write a thread pool and learn how ThreadPoolExecutor thread pools work

Xi Jie said that writing (6) put the user’s thinking when designing IT products into the article

2. MD5 encryption is required for the test data