头像

lyclyc_NSP

HMS


访客:1323

离线:17小时前


活动打卡代码 AcWing 90. 64位整数乘法

lyclyc_NSP
1个月前
#include <cstdio>

#define LL long long

using namespace std;

LL smul(LL a, LL b, LL p) {
    LL res = 0;

    while (b) {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }

    return res;
}

int main() {

    LL a, b, p;

    scanf("%lld%lld%lld", &a, &b, &p);

    printf("%lld", smul(a, b, p));

    return 0;

}



lyclyc_NSP
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], s[N];

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

    for (int i=1; i<=n; i++)
        cin >> a[i];

    a[n+1] = a[n];

    int head = 1, tail = 1;

    int sum = 1, ans = 0;

    s[a[1]] = 1;

    while (head <= tail && tail <= n+1) {
        tail ++;
        s[a[tail]] ++;

        if (s[a[tail]] == 1) sum ++; else {
            if (sum > ans) ans = sum;

            while (a[head] != a[tail]) s[a[head]]--, head ++, sum --;

            head ++;

            s[a[tail]] --;
        }
    }

    cout << ans << endl;
}


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

lyclyc_NSP
1个月前
#include <iostream>

using namespace std;

const int N = 1005;

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

            s[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1];
        }
    }

    while (q --) {
        int x, y, xx, yy, c;

        cin >> x >> y >> xx >> yy >> c;

        s[x][y] += c;
        s[x][yy+1] -= c;
        s[xx+1][y] -= c;
        s[xx+1][yy+1] += c;
    }

    for (int i=1; i<=n; i++, cout << endl) {
        for (int j=1; j<=m; j++) {
            s[i][j] = s[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];

            cout << s[i][j] << ' ';
        }
    } 
}


活动打卡代码 AcWing 797. 差分

lyclyc_NSP
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], s[N];

int main() {
    int n, m;

    cin >> n >> m;

    for (int i=1; i<=n; i++) {
        cin >> a[i];

        s[i] = a[i] - a[i-1];
    }

    while (m --) {
        int l, r, c;

        cin >> l >> r >> c;

        s[l] += c;
        s[r+1] -= c;
    }

    for (int i=1; i<=n; i++) {
        s[i] = s[i] + s[i-1];
        cout << s[i] << ' ';
    }
}


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

lyclyc_NSP
1个月前
#include <iostream>

using namespace std;

int a[1005][1005];

int main() {
    int n, m, q;


    cin >> n >> m >> q;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            int x;
            cin >> x;
            a[i][j] = x + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        }
    }

    for (int i=1; i<=q; i++) {

        int x, y, xx, yy;

        cin >> x >> y >> xx >> yy;
        cout << a[xx][yy] - a[x-1][yy] - a[xx][y-1] + a[x-1][y-1] << endl;
    }
}


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

lyclyc_NSP
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int a[N], l, r;

int main() {
    int n ,m;
    cin >> n >> m;

    for (int i=1; i<=n; i++) {
        cin >> a[i];
        a[i] += a[i-1];
    }

    for (int i=1; i<=m; i++) {
        cin >> l >> r;
        cout << a[r] - a[l-1] << endl;
    }
}


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

lyclyc_NSP
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int A[N], C[N];

int div(int a[], int b, int c[], int &r, int cnt) {
    r = 0;

    for (int i=cnt; i>=1; i--) {
        r = r * 10 + a[i];
        c[i] = r / b;
        r %= b;
    }

    while (cnt > 1 && c[cnt] == 0) cnt --;

    return cnt;
}

int main() {
    string a;
    int b;

    cin >> a >> b;

    int cnt1 = 0;
    for (int i=a.size()-1; i>=0; i--) 
        A[++cnt1] = a[i] - '0';

    int r;

    int tot = div(A, b, C, r, cnt1);

    for (int i=tot; i>=1; i--)
        cout << C[i];

    cout << endl << r;
}


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

lyclyc_NSP
1个月前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int A[N], C[N];

int mul(int a[], int b, int c[], int cnt) {

    int t = 0;

    for (int i=1; i<=cnt; i++) {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }

    if (t) c[++cnt] = t;

    while (cnt > 1 && c[cnt] == 0) cnt --;

    return cnt;
}

int main() {
    string a;
    int b;

    cin >> a >> b;

    int cnt1 = 0;
    for (int i=a.size()-1; i>=0; i--)
        A[++cnt1] = a[i] - '0';

    int tot = mul(A, b, C, cnt1);

    for (int i=tot; i>=1; i--)
        cout << C[i];
}


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

lyclyc_NSP
1个月前
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+10;

int A[N], B[N], C[N];

int Minus(int a[], int b[], int c[], int cnt) {

    int t = 0;

    for (int i=1; i<=cnt; i++) {
        t = a[i] - b[i] - t;
        c[i] = (t + 10) % 10;

        if (t < 0) t = 1; else t = 0;
    }

    while (cnt > 1 && c[cnt] == 0) cnt --;

    return cnt;

}

int main() {
    string a, b;
    cin >> a >> b;

    if (a.size() < b.size() || a.size() == b.size() && a < b) {
        cout<< '-';
        swap(a, b);
    }

    int cnt1 = 0;
    for (int i=a.size()-1; i>=0; i--)
        A[++cnt1] = a[i] - '0';

    int cnt2 = 0;
    for (int i=b.size()-1; i>=0; i--)
        B[++cnt2] = b[i] - '0';

    int tot = Minus(A, B, C, max(cnt1, cnt2));

    for (int i=tot; i>=1; i--)
        cout << C[i];

}



lyclyc_NSP
1个月前

题目描述

高精度加法


样例

$a, b$ 均为正整数


C++ 代码

#include <iostream>
using namespace std;

const int N = 100010;
int A[N], B[N], C[N];

int Add(int a[], int b[], int c[], int cnt) {

    int t = 0;//t表示进位

    for (int i=1; i<=cnt; i++) {
        t += a[i] + b[i];//进位加上a和b第i位上的数
        c[i] = t % 10;//c的值就是进位的个位数
        t /= 10;//把t的个位数去掉只剩下十位数,即只剩下这个位置的进位
    }
    if (t) c[++cnt] = 1;//如果t==1,表示还有一个进位,要补上

    return cnt;
}

int main() {

    string a, b;
    cin >> a >> b;  


    //A和B倒着放进int数组,因为有进位,倒着放容易处理
    int cnt1 = 0;
    for (int i=a.size()-1; i>=0; i--)
        A[++cnt1] = a[i] - '0';

    int cnt2 = 0;
    for (int i=b.size()-1; i>=0; i--)
        B[++cnt2] = b[i] - '0';

    int tot = Add(A, B, C, max(cnt1, cnt2));

    //因为A和B是倒着放的,所以C也要倒着输出
    for (int i=tot; i>=1; i--)
        cout << C[i];
}