头像

平行时空_8




离线:1天前


最近来访(0)

活动打卡代码 AcWing 797. 差分

#include<iostream>
using namespace std;

constexpr int N = 100010;
int n,m;
int dd[N];
int pre[N];

void insert(int l, int r, int v){
    //差分 l 位置+v  r+1 位置-v
    dd[l] += v;
    dd[r+1] -= v;
}

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

    for(int i = 1; i <= n; ++i){
        int num;
        cin >> num;
        insert(i, i, num);
    }

    for(int i = 1; i <= m; ++i){
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    for(int i = 1; i <= n; ++i){
        pre[i] = pre[i-1] + dd[i];
        cout << pre[i] << " ";
    }
}


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

#include<iostream>
using namespace std;

int n, m, q;
constexpr int N = 1010;
int dd[N][N];
int pre[N][N];


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

int main(){

    cin >> n >> m >> q;

    for (int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            int v;
            cin >> v;
            insert(i,j,i,j,v);
        }
    }

    for (int i = 1;i <= q; ++i){
        int x1, y1, x2, y2, v;
        cin >> x1 >> y1 >> x2 >> y2 >> v;
        insert(x1,y1,x2,y2,v);
    }

    for (int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + dd[i][j];
            cout << pre[i][j] <<' ';
        }
        cout << endl;
    }
}


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

#include<iostream>
using namespace std;

constexpr int N = 100010;
int n,m;
int dd[N];
int pre[N];

void insert(int l, int r, int v){
    //差分 l 位置+v  r+1 位置-v
    dd[l] += v;
    dd[r+1] -= v;
}

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

    for(int i = 1; i <= n; ++i){
        int num;
        cin >> num;
        insert(i, i, num);
    }

    for(int i = 1; i <= m; ++i){
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    for(int i = 1; i <= n; ++i){
        pre[i] = pre[i-1] + dd[i];
        cout << pre[i] << " ";
    }
}


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

#include<iostream>
using namespace std;

constexpr int N = 1010;
int n, m, q;
int pre[N][N];

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

    for(int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            int num = 0;
            cin >> num;
            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + num;
        }
    }

    for(int i = 0; i < q; ++i){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >>y2;
        cout << pre[x2][y2] - pre[x2][y1-1] - pre[x1-1][y2] + pre[x1 - 1][y1 -1] << endl;
    }

}


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

#include<iostream>
using namespace std;

int n,m;
constexpr int N = 100010;
int nums[N];
int prefix[N];

int main(){
    cin >> n >> m;
    int num = 0;
    for (int i = 1;i <= n; ++i){
        cin >> num;
        prefix[i] = prefix[i-1] + num;
    }

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


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

#include<iostream> 
using namespace std;
double n;
constexpr double erp = 1e-8; 
int main(){
    cin >> n;


    double l = -10000;
    double r = 10000;

    while(r - l > erp){
        double mid = (l + r)/2 ;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    }

    printf("%.6f",l) ;

}


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

#include<iostream>
using namespace std;

constexpr int  N = 100010;
int n, q;
int nums[N];

void search1(int q){
    int l = 0;
    int r = n - 1;

    while(l < r){
        int mid = l + r >> 1;
        if(nums[mid] >= q) r = mid;
        else l = mid + 1;
    }

    if(nums[l] != q) cout<< "-1" << " " << "-1" << endl;
    else {
        cout << l << " ";
        int l = 0;
        int r = n - 1;

    while(l < r){
        int mid = l + r + 1 >> 1;
        if(nums[mid] <= q) l = mid;
        else r = mid - 1;
    }

    cout<< l << endl;
    }

}


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

    for(int i = 0; i < q; ++i){
        int q = 0;
        cin >>  q;
        search1(q);
    }
}


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

#include<iostream>

using namespace std;

constexpr int N = 100010;
int n;
int nums[N];
long long res;

void reverse_num(int s, int e){
    if(s >= e) return;
    int mid = (s + e) >> 1;
    reverse_num(s, mid);
    reverse_num(mid + 1, e);

    //合并
    int i = s;
    int j = mid + 1;
    int cur = 0;
    int tmp[e - s + 1];

    while(i <= mid && j <= e){
        if(nums[i] <= nums[j]) tmp[cur++] = nums[i++];
        else{
            tmp[cur++] = nums[j++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) tmp[cur++] = nums[i++];
    while(j <= e) tmp[cur++] = nums[j++];

    for(int ii = s; ii <= e; ++ii){
        nums[ii] = tmp[ii - s]; 
    }
}





int main(){
    scanf("%d",&n);

    for(int i = 0; i< n; ++i){
        scanf("%d", &nums[i]);
    }
    reverse_num(0, n - 1);
    printf("%lld", res);

}


活动打卡代码 AcWing 787. 归并排序

#include<iostream>

constexpr int N = 100010;
int n;
int nums[N];

void merge_sort(int s, int e){
    if(s >= e) return;
    int mid = (s + e) >> 1;
    merge_sort(s, mid);
    merge_sort(mid+1 , e);

    //合并
    int tmp[e-s+1];

    int i = s;
    int j = mid + 1;
    int cur = 0;
    while(i <= mid && j<= e){
        if(nums[i]<= nums[j]) tmp[cur++] = nums[i++];
        else tmp[cur++] = nums[j++];
    }
    while(i<=mid) tmp[cur++] = nums[i++];
    while(j<=e) tmp[cur++] = nums[j++];

    for (int ii = s; ii <= e; ++ii){
        nums[ii] = tmp[ii - s];
    }
}


int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &nums[i]);
    }
    merge_sort(0,n-1);
    for(int i = 0; i< n; ++ i){
        printf("%d ", nums[i]);
    }
}


活动打卡代码 AcWing 786. 第k个数

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

int n,k;

int quickchoose(vector<int>& nums, int s, int e ,int  k){
    if(s >= e) return nums[s];
     int l = s - 1;
     int r = e + 1;
     int p = nums[(l + r) >> 1];
     while(l<r){
         do(++l);while(nums[l] < p);
         do(--r);while(nums[r] > p);
         if(r > l) swap(nums[l], nums[r]);
     }
     int sl = r - s + 1;
     if(k <= sl ) return quickchoose(nums, s, r, k);
     return  quickchoose(nums, r+1, e, k - sl);
}

int main(){
    scanf("%d%d", &n, &k);
    vector<int> nums(n);
    for(int i = 0; i < n; ++ i){
        scanf("%d", &nums[i]);
        // printf("%d", nums[i]);
    }
    printf("%d",quickchoose(nums, 0 , n - 1, k));
}