头像

弦上有春秋


访客:108

离线:6小时前


活动打卡代码 AcWing 798. 差分矩阵

#include <iostream>

using namespace std;

const int 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][y2 + 1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= 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++) {
            cin >> a[i][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];
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 797. 差分

#include<iostream>

using namespace std;

const int N = 100010;

int a[N], s[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {    //输入
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        s[i] = a[i] - a[i - 1];     // 差分
    }
    while(m--) {
        int l, r, c;
        cin >> l >> r >> c;
        s[l] = s[l] + c, s[r + 1] = s[r + 1] - c;  //加c
    }
    for(int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + s[i];       //改a[N]
    }
    for(int i = 1; i <= n; i++) {
        cout << a[i] << " ";       //输出
    }
    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

#include<iostream>

using namespace std;

const int N = 1010;

int a[N][N], s[N][N];

int main() {
    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++) {
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    while(q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] + s[x1 - 1][y1 - 1] - s[x2][y1 - 1] - s[x1 - 1][y2] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 795. 前缀和

#include<iostream>

using namespace std;

const int N = 100010;

int a[N], s[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    while(m--) {
        int l, r;
        cin >> l >> r;
        int m = s[r] - s[l - 1];
        cout << m << endl;
    }
    return 0;
}


活动打卡代码 AcWing 794. 高精度除法

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

using namespace std;

vector<int> div(vector<int> &A, int b, int &p) {
    vector<int> C;          //C就是商,p是余数
    int t = 0;
    for(int i = 0; i < A.size(); i++) {
        t = t * 10 + A[i];
        C.push_back(t / b);
        t = t % b;
    }
    p = t;
    reverse(C.begin(), C.end());
    while(C.back() == 0 && C.size() > 1)C.pop_back();
    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for(int i = 0; i < a.size(); i++)A.push_back(a[i] - '0');
    vector<int> C;
    int p = 0;      //余数
    C = div(A, b, p);
    for(int i = C.size() - 1; i >= 0; i--) {
        cout << C[i];
    }
    cout << endl;
    cout << p;
    return 0;
}


活动打卡代码 AcWing 793. 高精度乘法

#include<iostream>
#include<vector>

using namespace std;

vector<int> mut(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 = t / 10;
    }
    while(t) {
        C.push_back(t % 10);
        t = t / 10;
    }
    while(C.back() == 0 && C.size() > 1)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');
    vector<int> C;
    C = mut(A, b);
    for(int i = C.size() - 1; i >= 0; i--) {
        cout << C[i];
    }
    return 0;
}


活动打卡代码 AcWing 792. 高精度减法

#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();
    for(int i = A.size() - 1; i >= 0; i--) {
        if(A[i] != B[i])return A[i] > B[i];
    }
    return true;
}

vector<int> dec(vector<int> A, vector<int> B) {
    vector<int> C;
    int t = 0, p = 0;            // p是进位产生的,t是用来计算
    for(size_t i = 0; i < A.size() || i < B.size(); i++) {
        if(i < A.size())t = t + p + A[i];
        if(i < B.size())t = t - B[i];
        if(t < 0)p = -1;
        else p = 0;
        t = (t + 10) % 10;
        C.push_back(t);
        t = 0;
    }
    while(C.back() == 0 && C.size() > 1)C.pop_back();
    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');
    vector<int> C;
    if(cmp(A, B))C = dec(A, B);
    else C = dec(B, A), cout << "-";

    for(int i = C.size() - 1; i >= 0; i--) {
        cout << C[i];
    }
    return 0;
}


活动打卡代码 AcWing 791. 高精度加法

#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 = t + A[i];
        if(i < B.size())t = t + B[i];
        C.push_back(t % 10);
        t = t / 10;
    }
    if(t)C.push_back(t);
    return C;
}

int main() {
    string a, b;
    cin >> a;
    cin >> b;
    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i--) {
        A.push_back(a[i] - '0');
    }
    for(int j = b.size() - 1; j >= 0; j--) {
        B.push_back(b[j] - '0');
    }
    vector<int> C = add(A, B);
    for(int k = C.size() - 1; k >= 0; k--) {
        cout << C[k];
    }
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

#include<iostream>
//#include <cmath>
//#include <iomanip>

using namespace std;

int main() {
    double a;
    cin >> a;
    double left = -10000, right = 10000;
    while(right - left > 1e-10) {
        double mid = left + (right - left) / 2;
        double x = mid * mid * mid;
        if(x < a)left = mid;
        else right = mid;
    }
    printf("%.6lf\n", left);
    //cout << fixed << setprecision(6) << left;
    return 0;
}
/*
f格式:用来输出实数(包括单、双精度),以小数形式输出。有以下几种用法:
%f:不指定宽度,整数部分全部输出并输出6位小数。
%m.nf:输出共占m列,其中有n位小数,如数值宽度小于m左端补空格。 
%-m.nf:输出共占n列,其中有n位小数,如数值宽度小于m右端补空格
*/


活动打卡代码 AcWing 789. 数的范围

#include<iostream>

using namespace std;

const int N = 100010;

int p[N];

int main() {
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        cin >> p[i];
    }
    while(q--) {
        int a;
        cin >> a;
        int left = 0, right = n - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(p[mid] >= a)right = mid;
            else left = mid + 1;
        }
        if(p[left] != a) {
            cout << "-1 -1" << endl;
        }
        else {
            cout << left << " ";
            int left = 0, right = n - 1;
            while(left < right) {
                int mid = left + (right - left + 1) / 2;
                if(p[mid] <= a)left = mid;
                else right = mid - 1;
            }
            cout << left << endl;
        }
    }
    return 0;
}