五條淵

阅读量

+关注发消息

离线：2个月前

最近来访(11)

Kokaze

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

五條淵
3个月前

                #include <iostream>

using namespace std;

const int N = 1010;

int a[N][N], S[N][N];

void insert(int x1, int y1, int x2, int y2, int c){
    a[x1][y1] += c;
    a[x2 + 1][y2 + 1] += c;
    a[x1][y2 + 1] -= c;
    a[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 >> S[i][j];

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            insert(i, j, i, j, S[i][j]);

    int x1, y1, x2, y2, c;
    while(q -- ){
        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 ++ )
            S[i][j] = a[i][j] + S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];

    for(int i = 1; i <= n; i ++ ){                                     //输出矩阵的标准格式，在行循环的末尾增加一个回车
        for(int j = 1; j <= m; j ++ ) cout << S[i][j] << " ";
        cout << endl;
    }

    return 0;
}

            

活动打卡代码 AcWing 797. 差分

五條淵
3个月前

                #include <iostream>

using namespace std;

const int N = 100010;

int S[N], a[N];

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

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

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

    for(int i = 1; i <= n; i ++ ) insert(i, i, S[i]);    //初始化差分数组

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

    for(int i = 1; i <= n; i ++ ) S[i] = S[i - 1] + a[i];  //记得重新组装前缀和

    for(int i = 1; i <= n; i ++ ) cout << S[i] << " "; 

    return 0;
}


            

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

五條淵
3个月前

                #include <iostream>

using namespace std;   //不用cin, cour, endl可以用写,写了可以在cin前省略std::

const int N = 1010;

int a[N][N], S[N][N];

int main(){
    int n, m, q;
    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 ++ )
            S[i][j] = S[i - 1][j] + S[i][j - 1] + a[i][j] - S[i - 1][j - 1];

    int x1, y1, x2, y2;
    while(q -- ){
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", S[x2][y2] + S[x1 - 1][y1 - 1] - S[x1 - 1][y2] - S[x2][y1 - 1]);
    }

    return 0;
}

            

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

五條淵
3个月前

                #include <iostream>

using namespace std;

const int N = 100010;

int a[N], S[N];

int main(){
    int n, m;
    scanf("%d%d", &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]; //计算前缀和


    int l, r;
    while(m -- ){
        scanf("%d%d",&l, &r);
        printf("%d\n", S[r] - S[l - 1]);          //计算区间和（前缀和将O(n)的区间和变为O(1)）
    }

    return 0;
}

            

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

五條淵
3个月前

                #include<iostream>

using namespace std;

int main(){                           //二分本质是查找到某个点
    double n, mid
    cin >> n;
    double l = -10000 ,r = 10000;

    while(r - l > 1e-8){
        mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    }

    printf("%lf\n", l);  //printf 小数默认保留6位

    return 0;
}

            

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

五條淵
4个月前

                #include<iostream>

using namespace std;

const int N = 1e5 + 10;        //设置常量，这样申明数组的时候不需要一个个去写了
int q[N];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> q[i];

    int k;
    while(m -- ){
        cin >> k;
        int l = 0, r = n - 1, mid;   
        while(l < r){
            mid = l + r >> 1;
            if(q[mid] >= k) r = mid;      //想清楚用以区分分界点两边的性质
            else l = mid + 1;
        }
        if(q[r] != k) cout << "-1 -1" << endl;
        else{
            cout << r << " ";
            l = 0, r = n - 1;
            while(l < r){
                mid = l + r + 1>> 1;
                if(q[mid] <= k) l = mid;
                else r = mid - 1;
            }
            cout << r << endl;
        }
    }

    return 0;
}

            

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

五條淵
4个月前

                #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> div(vector<int> &A, int b, int &r){
    vector<int> C;
    for(int i = A.size() - 1; i >= 0; i -- ){         //除法从最高位开始
        r = 10 * r + 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, r = 0;
    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 -- ) cout << C[i];

    cout << endl << r;

    return 0;
}

            

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

五條淵
4个月前

                #include<iostream>
#include<vector>

using namespace std;

vector<int> mul(vector<int> &A, int &b){
    vector<int> C;
    int t = 0;                                                //乘法可能位数增加，所以t在循环外定义
    for(int i = 0; i < A.size() || t; i ++ ){                 //处理可能增加的最高位需要 || t
        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 -- ) cout << C[i];

    return 0;
}

            

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

五條淵
4个月前

’‘’

include[HTML_REMOVED]

using namespace std;

vector[HTML_REMOVED] mul(vector[HTML_REMOVED] &A, int &b){
vector[HTML_REMOVED] C;
int t = 0; //乘法可能位数增加，所以t在循环外定义
for(int i = 0; i < A.size() || t; i ++ ){ //处理可能增加的最高位需要 || t
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 -- ) cout << C[i];

return 0;

}
‘’‘

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

五條淵
4个月前

                #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();   //先把不等于的情况单拎出来，在用一个式子区分大于和小于
    else{
        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;
    for(int i = 0, t = 0; i < A.size(); i ++ ){
        t = A[i] - t;
        if(i < B.size()) t -= B[i];  //总之要起到 A[i] - B[i] - t 的效果 
        C.push_back((t + 10) % 10);  //不论t是否大于 0，(t + 10) % 10 都能处理
        if(t < 0) t = 1;             //减法的进位处理只有可能是 0 或 1
        else t = 0;
    }

    while(C.back() == 0 && C.size() > 1) C.pop_back();

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

    if(cmp(A, B)){
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    }

    else{                                                               //处理出现负数的情况
        auto C = sub(B, A);
        cout << "-";
        for(int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    }

    return 0;
}

            

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

include[HTML_REMOVED]

include[HTML_REMOVED]

0 评论

0 评论