3180: 蓝桥杯2023年第十四届省赛真题-棋盘 前缀和矩阵,差分解法

解题思路:

差分矩阵模板题,了解差分矩阵前需要依次了解 前缀和  ->  一维差分 ->  前缀和矩阵  ->  差分矩阵 

前缀和  给定一个数组,构造 前缀和数组,求区间 [l,r]的和,只需要 sum[r] - sum[l-1];即可

一维差分是 前缀和的逆运用, 多用于将区间[l,r]内的所有数加上某一个值(可以是负值)

二维前缀和是一维前缀和的拓展, 用于求原始矩阵 的子矩阵的和,

二维差分是二维前缀和的逆运用,用于求 子矩阵 内所有数的同一增量的修改后的 矩阵

注意事项:

    本题 要借助 前缀和 和 差分的思路构造前缀积的概念,本题的白子可以设为1,黑子设为 -1,本题涉及的增量只有一个-1,即白子1,乘-1得-1变成黑子,同理黑子-1乘-1得1变成白子,本题在一个子矩阵内所有棋子反转颜色 ,符合 前缀积的概念,因此可以使用差分思路

参考代码:

package com.蓝桥真题._14届;


import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

/**
 * ClassName: F棋盘
 * Package:  com.蓝桥真题._14届
 * Describe:

3 3
1 1 2 2
2 2 3 3
1 1 3 3

ans:
001
010
100
 * @Create 2023/04/10 10:49
 */
public class F棋盘 {
    static int n,m;static int[][] map;
    public static void main(String[] args) throws Exception {
        n = nextInt(); m = nextInt(); map = new int[n + 4][n + 4];
        for(int [] row : map) Arrays.fill(row,1);
        //show();

        for(int i = 0; i < m; i++){ insert(nextInt(),nextInt(),nextInt(),nextInt(),-1); }
        //pw.println("---------------------"); show();

        for(int i =1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                map[i][j] *= map[i - 1][j] * map[i][j-1] / map[i - 1][j - 1];
                pw.print(map[i][j] == 1 ? 0 : 1);
            }
            pw.println();
        }

        pw.flush();
    }
    static void insert(int x1,int y1,int x2,int y2,int q){
        map[x1][y1] *= q;
        map[x2 + 1 ][y1] /= q;
        map[x1][y2 +1 ] /= q;
        map[x2 + 1][y2 + 1] *= q;
    }

    static void show(){
        for(int[] row : map){
            for(int col : row)pw.printf("%3d",col);
            pw.println();
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
}