头像

团子12138




离线:1天前


最近来访(26)
用户头像
xyd
用户头像
琴岛森林
用户头像
啦啦啦lalla
用户头像
恶魔波刚
用户头像
夜寐
用户头像
FreeGiveMan
用户头像
无人圣地
用户头像
hopopono
用户头像
A_52
用户头像
老人与海
用户头像
dancebyte
用户头像
果粒橙
用户头像
刘俊凯
用户头像
叫我王中王
用户头像
87牛
用户头像
ls131
用户头像
西瓜撞地球
用户头像
幼儿源卩扛把子
用户头像
Lxj
用户头像
Bessie

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

#include <iostream>
#include <cstring>
#include <algorithm>

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]);
        puts("");
    }

    return 0;
}


活动打卡代码 AcWing 797. 差分

#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()
{
    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);
    }

    // 差分数组的前缀和
    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. 子矩阵的和

#include <iostream>
#include <cstring>
#include <algorithm>

const int N = 1010;
int n, m, q;

int a[N][N], s[N][N];

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 ++ )
            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 <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

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 ++ ) 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 794. 高精度除法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//int r=0;
vector<int> div(vector<int> &A,int B,int &r){//r传入r的地址,便于直接对余数r进行修改
    vector<int> C;
    for(int i=0;i<A.size();i++){//对A从最高位开始处理
        r=r*10+A[i];//将上次的余数*10在加上当前位的数字,便是该位需要除的被除数
        C.push_back(r/B);//所得即为商在这一位的数字
        r=r%B;
    }
    //由于在除法运算中,高位到低位运算,因此C的前导零都在vector的前面而不是尾部,vector只有删除最后一个数字pop_back是常数复杂度,而对于删除第一位没有相应的库函数可以使用,而且删除第一位,其余位也要前移,
    //因此我们将C翻转,这样0就位于数组尾部,可以使用pop函数删除前导0
    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=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位,由于在除法的手算过程中,发现从高位进行处理
    //for(int i=0;i<A.size();i++) cout<<A[i];
    //cout<<B;
    auto C = div(A,B,r);
    for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位
    cout<<endl<<r;//输出余数
    cout<<endl;
    return 0;
}



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

#include <iostream>
#include <vector>

using namespace std;

// 注意前导零
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 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 787. 归并排序

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

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    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];
}





C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    const int INF = 1e8;
    int ans = 0;

    vector<int> dfs(TreeNode* root)
    {
        // 左右子树的初始化, 子节点值,左子树最大值, 右子树最小值, 所以每个子树都要返回最大最小值
        // 如果左子树不存在,如何才能不影响答案?
        // 左子树最小值:当左子树不存在,返回根节点的值;
        // 左子树最大值:当左子树不存在不用判断,当左子树存在设置为一个不会影响判断的值。
        vector<int> left{0, root->val, -INF}; 
        vector<int> right{0, INF, root->val};

        // 左右子树存在,重新求值
        if(root->left) left = dfs(root-> left);
        if(root->right) right = dfs(root -> right);

        // 整棵树是二叉搜索树
        if(left[2] < root->val && root->val < right[1])
        {
            int sum = left[0] + right[0] + root-> val;
            ans = max(ans, sum);
            return {sum, left[1], right[2]};
        }

        // 整棵树不是合法的二叉树搜索树(如果左子树不是二叉搜索树,希望让左边条件恒不成立)
        return {-INF, -INF, INF};
    }


    int maxSumBST(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;+
 *     }
 * }
 */
class Solution {
    private final int INF = 100000000;
    private int ans = 0;

    private int[] dfs(TreeNode root) {
        int[] left = {0, root.val, -INF};
        int[] right = {0, INF, root.val};

        if (root.left != null) left = dfs(root.left);
        if (root.right != null) right = dfs(root.right);

        if (left[2] < root.val && root.val < right[1]) {
            int s = left[0] + right[0] + root.val;
            ans = Math.max(ans, s);
            return new int[]{s, left[1], right[2]};
        }

        return new int[]{-INF, -INF, INF};
    }

    public int maxSumBST(TreeNode root) {
        dfs(root);
        return ans;
    }
}

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self, root):
        left = [0, root.val, -self.INF]
        right = [0, self.INF, root.val]

        if root.left: left = self.dfs(root.left)
        if root.right: right = self.dfs(root.right)

        if left[2] < root.val and root.val < right[1]:
            s = left[0] + right[0] + root.val
            self.ans = max(self.ans, s)
            return [s, left[1], right[2]]
        return [-self.INF, -self.INF, self.INF]

    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.INF = 1e8
        self.ans = 0
        self.dfs(root)
        return self.ans



//这里填你的代码^^
class Solution {
public:
    const int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    int is_leap(int year)
    {
        if(year%4 == 0 && year %100 || year %400 == 0)
        {
            return 1;
        }
        return 0;
    }

    int get_days(int year, int month)
    {
        if(month !=2) return months[month];
        return is_leap(year)+28;
    }

    int get(string date)
    {
        int year, month, day;
        sscanf(date.c_str(), "%d-%d-%d", &year, &month, &day);
        int res = 0;
        for (int i = 1971; i< year; i++)
        {
            res += 365 + is_leap(i);
        }
        for (int i=1; i<month; i++)
        {
            res += get_days(year, i);
        }
        return res + day;
    }

    int daysBetweenDates(string date1, string date2) {
        return abs(get(date1) - get(date2));
    }
};



2^n的意思是,在全排列中有2^n的次数结果是相同的,需要除掉。

class Solution {
public:
    int countOrders(int n) {
        const int MOD  = 1e9+7;
        long long res = 1;
        for ( int i = 1; i<= n*2; i++)
        {
            if(i%2) res = res*i % MOD;
            else res = i/2 *res % MOD;
        }
        return (int) res;
    }
};

Java 代码

class Solution {
    public int countOrders(int n) {
        final int MOD = 1000000007;
        long res = 1;
        for (int i = 1; i <= n * 2; i ++ ) {
            if (i % 2 == 1) res = res * i % MOD;
            else res = i / 2 * res % MOD;
        }
        return (int)res;
    }
}

Python3 代码

class Solution:
    def countOrders(self, n: int) -> int:
        MOD = 1000000007
        res = 1
        for i in range(1, n * 2 + 1):
            if i % 2: res = res * i % MOD
            else: res = i // 2 * res % MOD
        return res

方法二:递推

using LL = long long;

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int countOrders(int n) {
        if (n == 1) {
            return 1;
        }
        int ans = 1;
        for (int i = 2; i <= n; ++i) {
            ans = (LL)ans * (i * 2 - 1) % mod * i % mod;
        }
        return ans;
    }
};