暴力和二维差分都只能过两个点,是java的问题吗...求好哥哥看一下

P3397 地毯

sakura、 @ 2022-04-02 21:47:20

暴力代码如下

import java.util.*;
public class Main {
    static int n, m;
    static int x1, y1, x2, y2;
    static int[][] a = new int[1000][1000];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= m; i++) {
            x1 = sc.nextInt();
            y1 = sc.nextInt();
            x2 = sc.nextInt();
            y2 = sc.nextInt();
            for (int k = x1; k <= x2; k++) {
                for (int m = y1; m <= y2; m++) {
                    a[k][m]++;
                }
            }
        }
        for (int i = 1;i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }

    }
}

以下是二维差分的代码

import java.util.*;
public class erweichafen {
    static int n, m;
    static int x1, y1, x2, y2;
    static int[][] a = new int[1000][1000];
    static int[][] sum = new int[1000][1000];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= m; i++) {
            x1 = sc.nextInt();
            y1 = sc.nextInt();
            x2 = sc.nextInt();
            y2 = sc.nextInt();
            add(x1, y1, x2, y2);
        }
        init_sum();
        for (int i = 1;i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.print(sum[i][j] + " ");
            }
            System.out.println();
        }

    }
    static void add(int x1, int y1, int x2, int y2) {
        a[x1][y1] += 1;
        a[x1][y2 + 1] -= 1;
        a[x2 + 1][y1] -= 1;
        a[x2 + 1][y2 + 1] += 1;
    }//二维差分的区域添加公式
    static void init_sum() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
            }
        }
    }//利用得到的差分数组,初始化二维前缀和数组
}

难道真的是语言问题吗....


by WannaYellow @ 2022-04-04 14:36:11

java输入输出效率有点低吧。。。。


by aoliaolong @ 2022-04-11 17:22:29

使用Java的快速输入与输出 百度有这段代码记一下


|