头像

天空与海洋之间


访客:30

在线 


活动打卡代码 AcWing 797. 差分

#include <cstdio>
using namespace std;

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

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

int main(){

    scanf("%d%d",&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;
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    }
    //对b求前缀和
    for(int i = 1; i <= n; i++) d[i] += d[i-1];
    for(int i = 1; i <= n; i++) printf("%d ",d[i]);
    return 0;
}


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

#include <cstdio>
using namespace std;

const int N = 1010;
int a[N][N];
int s[N][N];
int n;//行
int m;//列
int q;//询问次数

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]);   
        }
    }
    //计算前缀和
    s[0][0] = 0;
    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;
        scanf("%d%d%d%d",&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. 前缀和

#include <cstdio>
using namespace std;

const int N = 10e5 + 10;
int n;
int m;//询问
int a[N];
int s[N];

int main(){

    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);//从下标1开始存储数据方便和下面对应
    s[0] = 0;
    for(int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r] - s[l-1]);
    }
    return 0;
}


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

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

const int N = 10e5 + 10;
int nums[N];
int n;
int q;
int main(){
    scanf("%d%d",&n,&q);
    for(int i = 0; i < n; i++){
        scanf("%d",&nums[i]);
    }
    while(q--){
        int k;
        int x;
        scanf("%d",&k);
        int l = 0,r = n-1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= k){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        x = l;
        if(nums[l] != k){
            cout << "-1 -1" << endl;
        }else{
            int l = 0,r = n-1;
            while(l < r){
                int mid = l + r + 1>> 1;
                if(nums[mid] <= k){
                    l = mid;
                }else{
                    r = mid - 1;
                }
            }
            cout << x << " " << l << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 785. 快速排序

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
int n;
int nums[N];

void quick_sort(int nums[],int l,int r){
    if(l >= r){
        return;
    }
    int pivot = nums[l + r >> 1];
    int i = l-1;
    int j = r+1;
    while(i < j){
        do i++; while(nums[i] < pivot);
        do j--; while(nums[j] > pivot);
        if(i < j) swap(nums[i],nums[j]);
    }
    quick_sort(nums,l,j);
    quick_sort(nums,j+1,r);
}

int main(){

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

    quick_sort(nums,0,n-1);

    for(int i = 0; i < n; i++){
        printf("%d ",nums[i]);
    }
    return 0;
}


活动打卡代码 AcWing 51. 数字排列

class Solution {
public:
    vector<vector<int>> permutation(vector<int>& nums) {
        vector<vector<int>> ans;
        if(nums.size() == 0){
            return ans;
        }
        do{
            ans.push_back(nums);
        }while(next_permutation(nums.begin(),nums.end()));
        return ans;
    }
};


活动打卡代码 AcWing 862. 三元组排序

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
struct Node{
    int x;
    double y;
    string z;
};
bool cmp(Node a,Node b){
    return a.x < b.x;
}
int main(){
    int n;
    scanf("%d",&n);
    Node nodes[10000];
    for(int i = 0; i < n; i++){
        cin >> nodes[i].x >> nodes[i].y >> nodes[i].z;
    }
    std::sort(nodes,nodes+n,cmp);
    for(int i = 0; i < n; i++){
        printf("%d %.2lf ",nodes[i].x,nodes[i].y);
        cout << nodes[i].z << endl;
    }

    return 0;
}



class Solution {
public:
    int NumberOf1(int n) {
        if(n == 0){
            return 0;
        }
        int cnt = 0;
        for(int i = 0; i <= 31; i++){
            if((n >> i & 1) == 1){
                cnt++;
            }
        }
        return cnt;
    }
};



class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        vector<int> ans;
        if(nums.size() == 0){
            return ans;
        }
        int n = ans.size();
        unordered_set<int> set;
        for(int num : nums){
            int need = target - num;
            if(set.count(need)){
                ans.push_back(need);
                ans.push_back(num);
                return ans;
            }
            set.insert(num);
        }
        return ans;
    }
};


活动打卡代码 AcWing 53. 最小的k个数

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> nums, int k) {
        vector<int> ans;
        if(nums.size() == 0){
            return ans;
        }
        priority_queue<int> max_heap;
        for(auto x : nums){
            max_heap.push(x);
            if(max_heap.size() > k){
                max_heap.pop();
            }
        }
        while(!max_heap.empty()){
            ans.push_back(max_heap.top());
            max_heap.pop();
        }
        std::reverse(ans.begin(),ans.end());
        return ans;
    }
};