头像

想吃鱼的猫酱




离线:1天前


最近来访(20)
用户头像
Sings
用户头像
_Zhou_Bo_
用户头像
hncsxzx
用户头像
风吹雪
用户头像
哇啦啦
用户头像
专注等于效率翻倍
用户头像
湖文码神
用户头像
童话镇
用户头像
Zeref
用户头像
takanasi
用户头像
zyfStars

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

package com.atguigu.java.different;

import java.util.Scanner;

public class twoDimension {
    public static int[][] b = new int[1010][1010];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        int[][] a = new int[n+1][m+1];
        //给a数组赋值
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        //构建差分数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                insert(i,j,i,j,a[i][j]);
            }
        }

        while(q-- > 0){
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            int c = sc.nextInt();
            insert(x1,y1,x2,y2,c);
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //求前缀和
                a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }

    }

    public static 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;
    }


}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



import java.util.Scanner;

public class Main {
    public static int[] b = new int[100010];
    public static int[] a = new int[100010];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }

        //构建差分数组 该处用1做下标其实有一部分原因是因为减去差分数组的前一个数的值,不处理下标会越界
        for (int i = 1; i <= n; i++) {
            //其实这一步相当于改变差分数组某个位置的值,b[n]该位置减去c(c其实是b[n-1],而b里面是0,
            // 也就是-b[n-1]),
            // 再加上a[n] 其实就是a[n]-a[n-1]=当前位置的差分值
            insert(i,i,a[i]);
        }

        //指定位置改变差分数组某个地方的值,然后间接改变前缀和数组的值
        while(m-- > 0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            int c = sc.nextInt();
            insert(l,r,c);
        }

        for (int i = 1; i <= n; i++) {
            a[i] = a[i-1] + b[i];
            System.out.print(a[i] + " ");
        }



    }

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


活动打卡代码 AcWing 797. 差分

import java.util.Scanner;

public class Main {
    public static int[] b = new int[100010];
    public static int[] a = new int[100010];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }

        //构建差分数组 该处用1做下标其实有一部分原因是因为减去差分数组的前一个数的值,不处理下标会越界
        for (int i = 1; i <= n; i++) {
            //其实这一步相当于改变差分数组某个位置的值,b[n]该位置减去c(c其实是b[n-1],而b里面是0,
            // 也就是-b[n-1]),
            // 再加上a[n] 其实就是a[n]-a[n-1]=当前位置的差分值
            insert(i,i,a[i]);
        }

        //指定位置改变差分数组某个地方的值,然后间接改变前缀和数组的值
        while(m-- > 0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            int c = sc.nextInt();
            insert(l,r,c);
        }

        for (int i = 1; i <= n; i++) {
            a[i] = a[i-1] + b[i];
            System.out.print(a[i] + " ");
        }



    }

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

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n+1][m+1];
        int[][] sum = new int[n+1][m+1];
        int q = sc.nextInt();

        //i对应有几行,m代表几列
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m ; j++) {
                //计算二维数组对应下标的前缀和
                //值得一提的点是这个其实外层都i有空的一列数组,正好方便这个二维数组构成最小的递归
                sum[i][j] = sum[i-1][j]  + sum[i][j-1] - sum[i-1][j-1] + arr[i][j];
            }
        }

        while(q-- > 0 ){
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            //极其关键的一步
            int reuslt = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
            System.out.println(reuslt);
        }


    }
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = 100010;
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[N];
        int[] sum = new int[N];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            //计算各个位置的前缀和
            sum[i]  = sum[i-1] + arr[i];
        }
        while(m-- != 0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            //用概率论离散型随机变量来理解,即点表示概率区间
            int result = sum[r] - sum[l-1];
            System.out.println(result);
        }
    }
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = 100010;
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[N];
        int[] sum = new int[N];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            //计算各个位置的前缀和
            sum[i]  = sum[i-1] + arr[i];
        }
        while(m-- != 0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            //用概率论离散型随机变量来理解,即点表示概率区间
            int result = sum[r] - sum[l-1];
            System.out.println(result);
        }
    }
}


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

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        int b = sc.nextInt();
        List<Integer> A = new ArrayList<>(a.length());
        for (int i = a.length() - 1;i >= 0;i--) {
            A.add(a.charAt(i) - '0');
        }
        List<Integer> C = div(A,b);
        for (int i = C.size() - 2;i >= 0;i--) {
            System.out.print(C.get(i));
        }
        System.out.println();
        System.out.println(C.get(C.size() - 1));
    }

    public static List<Integer> div(List<Integer> A,int b){
        List<Integer> C  = new ArrayList<>();
        //代表除完的余数
        int r = 0;
        //处理获得除数
        for (int i = A.size() - 1; i >= 0; i--) {
            r = r * 10 + A.get(i);
            C.add(r / b);
            r = r % b;
        }
        //反转数组
        Collections.reverse(C);
        //去掉前导零
        while(C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);
        //将余数加入到C集合里面
        C.add(r);

        return C;
    }
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        int b = sc.nextInt();
        List<Integer> A = new ArrayList<>(a.length());
        for (int i = a.length() - 1;i >= 0;i--) {
            A.add(a.charAt(i) - '0');
        }
        List<Integer> C = div(A,b);
        for (int i = C.size() - 2;i >= 0;i--) {
            System.out.print(C.get(i));
        }
        System.out.println();
        System.out.println(C.get(C.size() - 1));
    }

    public static List<Integer> div(List<Integer> A,int b){
        List<Integer> C  = new ArrayList<>();
        //代表除完的余数
        int r = 0;
        //处理获得除数
        for (int i = A.size() - 1; i >= 0; i--) {
            r = r * 10 + A.get(i);
            C.add(r / b);
            r = r % b;
        }
        //反转数组
        Collections.reverse(C);
        //去掉前导零
        while(C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);
        //将余数加入到C集合里面
        C.add(r);

        return C;
    }
}


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

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //高精度乘以低精度
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        int b = sc.nextInt();
        List<Integer> A = new ArrayList<>(a.length());
        for (int i = a.length() - 1;i >= 0;i--) {
            A.add(a.charAt(i) - '0');
        }

        List<Integer> C = mul(A,b);
        for (int i = C.size() - 1;i >= 0;i-- ) {
            System.out.print(C.get(i));
        }
    }

    public static List<Integer> mul(List<Integer> A,int b){
        List<Integer> C = new ArrayList<>();
        int t = 0;
        //该处用于处理超出a位数的进位值)
        for (int i = 0; i < A.size()|| t != 0; i++){
            //在a数组未乘完前进行进位计算,后续只需进行进位处理即可
            if (i < A.size())  t += A.get(i) * b;
            C.add(t%10);
            t /= 10;
        }
        while (C.size() > 1 && C.get(C.size()-1) == 0) C.remove(C.size()-1);
        return C;
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~




import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //高精度乘以低精度
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        int b = sc.nextInt();
        List<Integer> A = new ArrayList<>(a.length());
        for (int i = a.length() - 1;i >= 0;i--) {
            A.add(a.charAt(i) - '0');
        }

        List<Integer> C = mul(A,b);
        for (int i = C.size() - 1;i >= 0;i-- ) {
            System.out.print(C.get(i));
        }
    }

    public static List<Integer> mul(List<Integer> A,int b){
        List<Integer> C = new ArrayList<>();
        int t = 0;
        //该处用于处理超出a位数的进位值)
        for (int i = 0; i < A.size()|| t != 0; i++){
            //在a数组未乘完前进行进位计算,后续只需进行进位处理即可
            if (i < A.size())  t += A.get(i) * b;
            C.add(t%10);
            t /= 10;
        }
        while (C.size() > 1 && C.get(C.size()-1) == 0) C.remove(C.size()-1);
        return C;
    }
}