头像

mdmddn




离线:7天前


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

mdmddn
3个月前
#include <iostream>
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) {
    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", &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;
        scanf("%d%d%d%d%d", &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]);
        printf("\n");
    }

    return 0;
}


活动打卡代码 AcWing 797. 差分

mdmddn
3个月前
#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) {
    b[l] += c;
    b[r + 1] -= c; 
}

int main() {
    cin >> 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]); //构造差分矩阵

    while (m--) {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    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;
}


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

mdmddn
3个月前
#include <iostream>
using namespace std;

const int N = 1010;
int a[N][N], s[N][N];
int n, m, q;

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) 
            scanf("%d", &a[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[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); //算子矩阵的和
    }
    return 0;
}


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

mdmddn
3个月前
#include <iostream>
using namespace std;

const int N = 100010;
int a[N], s[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

    while(m--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}


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

mdmddn
3个月前
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//A/b, 商是C,余数是r
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() > 1 && C.back() == 0) 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');

    int r;
    auto C = div(A, b, r);

    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    cout << endl << r << endl;
    return 0;
}


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

mdmddn
3个月前
#include <iostream>
#include <vector>
using namespace std;

vector<int> mul(vector<int>& A, int b) {
    vector<int> C;

    for (int i = 0, t = 0; i < A.size() || t; i++) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) 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');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

    return 0;
}


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

mdmddn
3个月前
#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> 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); // >0 t  <0 (-3 + 10) % 10 = 9
        if (t < 0) t = 1; //借1
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); //去掉前面的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--) printf("%d", C[i]);

    return 0;
}


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

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

    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');

    auto c = add(A, B);
    for (int i = c.size() - 1; i >= 0; i--) printf("%d", c[i]);
    return 0;
}


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

mdmddn
3个月前
#include <iostream>
using namespace std;

int main() {
    double n;
    cin >> n;

    double l = -10000, r = 10000;
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    printf("%lf", l);
    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

mdmddn
3个月前
#include <iostream>
using namespace std;

typedef long long LL;

const int N = 100010;
int n;
int q[N], tmp[N];

LL merge_sort(int q[], int l, int r) {
    if (l >= r) return 0;

    int mid = l + r >> 1;

    int k = 0, i = l, j = mid + 1;
    LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);

    while (i <= mid && j <= r) 
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }

    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];

    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);

    cout << merge_sort(q, 0, n - 1) << endl;

    return 0;
}