暴力和二维差分都只能过两个点,是java的问题吗...求好哥哥看一下
  • 板块P3397 地毯
  • 楼主sakura、
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/4/2 21:47
  • 上次更新2023/10/28 04:49:22
查看原帖
暴力和二维差分都只能过两个点,是java的问题吗...求好哥哥看一下
150750
sakura、楼主2022/4/2 21:47

暴力代码如下

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];
			}
		}
	}//利用得到的差分数组,初始化二维前缀和数组
}

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

2022/4/2 21:47
加载中...