目录
题目链接:10.棋盘 - 蓝桥云课 (lanqiao.cn)
题目链接:10.棋盘 - 蓝桥云课 (lanqiao.cn)
思路
我的直接暴力思路
我的这段Java代码模拟了一个棋盘上的翻转操作问题。初始化一个n x n
大小的棋盘,棋盘上的每个位置可以是0(代表白色)或者1(代表黑色)。然后进行m
次操作,每次操作指定一个子矩阵,并将其中的颜色进行翻转(0变1,1变0)。
下面详细介绍这段代码的任务流程:
-
代码开头导入了必要的IO类,并声明了
Main
类。 -
在
main
函数中,首先通过StreamTokenizer
类对象st
读取输入。 -
读取棋盘大小
n
和操作次数m
。 -
创建了一个
n x n
的二维数组arrs
来表示棋盘,用0初始化,代表初始时所有位置都是白色。 -
使用一个for循环进行
m
次操作,每次读取四个整数,分别代表矩阵的左上角(x1, y1)
和右下角(x2, y2)
。 -
调用
change
方法对指定的子矩阵执行翻转操作。 -
在所有操作完成后,使用两个嵌套的for循环遍历并打印出最终棋盘的状态。
change
方法用于完成矩阵内颜色的翻转操作:
-
它接收棋盘的引用和两个坐标点作为参数,表示需要翻转颜色的矩形区域。
-
使用两个嵌套的for循环遍历这个矩形内的每个位置,在Java中数组索引是从0开始的,但题目中给的坐标可能是从1开始的,因此
x1
,y1
,x2
,y2
都减去了1来映射到正确的索引。 -
对于矩形内的每个位置,如果当前是0(白色),就翻转为1(黑色);如果是1(黑色),就翻转为0(白色)。
-
arrs
数组在change
方法结束后会反映所有翻转操作后的状态。
最后,主函数中打印出arrs
数组的内容显示最终棋盘状态。
总之,这段代码通过读取操作然后不断翻转棋盘上的子矩阵内的颜色,最终输出操作过后的棋盘状态。
最后也是成功的AC了
代码实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) throws IOException{
// StreamTokenizer st = new StreamTokenizer(new BufferedReader(new
// InputStreamReader(System.in)));
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
// 棋盘大小
int n = (int)st.nval;
st.nextToken();
// 操作次数
int m = (int)st.nval;
// 初始化好就全部是 0
int[][] arrs = new int[n][n];
for (int i = 0; i < m; i++) {
st.nextToken();
int x1 = (int)st.nval;
st.nextToken();
int y1 = (int)st.nval;
st.nextToken();
int x2 = (int)st.nval;
st.nextToken();
int y2 = (int)st.nval;
change(arrs, x1, y1, x2, y2);
}
for (int i = 0; i < n; i++) {
int[] line = arrs[i];
for (int j = 0; j < n; j++) {
System.out.print(line[j]);
}
System.out.println();
}
}
public static void change(int[][] arrs, int x1,int y1,int x2,int y2) {
// 白色0 黑色1
for (int i = x1 - 1; i <= x2 - 1; i++) {
for (int j = y1 - 1; j <= y2 - 1; j++) {
arrs[i][j] = arrs[i][j] == 0 ? 1 : 0;
}
}
}
}
这里注意了,你cv代码到测试的地方的时候记得把你导入的包也cv进去
前缀和思路
先来了解一下什么叫做前缀和和差分数组
前缀和:
前缀和主要用于处理区间和类型的问题。具体而言,对于给定的一个序列或数组,我们可以预处理出一个前缀和数组,其中每个元素表示原序列中从第一个元素到当前位置的元素之和。举个简单的例子,比如我们有一个数组[1,2,3,4,5],那么其对应的前缀和数组就是[1,3,6,10,15]。你可以看到,前缀和数组中的每个值都是原数组中从第一项到当前项的和。有了这个前缀和数组,我们就可以在常数时间内求出原数组中任意一个子序列的和,而不需要每次都去遍历子序列中的所有元素。
更多举例
假设我们有一个数字数组[2, 3, -1, 5, 7],然后有很多的查询请求,每个请求需要得知在某个范围内(例如从索引i到j)的数字之和。我们明显可以通过累加索引 i 到 j 的每个数字来得出答案,但是需要花费的时间与区间长度有关。如果有频繁的请求,那么这种直接累加的方法效率就会变得低下。
但是如果我们提前计算出前缀和数组,例如对于上述数组[2, 3, -1, 5, 7],其前缀和数组为[2, 5, 4, 9, 16],此时如果要查询从索引i到索引j的所有数之和,只需要计算前缀和数组在索引j的值减去前缀和数组在索引i的值。
差分数组:
差分数组是前缀和的逆运算,用于记录相邻两元素的差值。对于一个给定的序列或数组,差分数组中的每个元素都等于原序列中对应位置的元素与其前一个元素的差值。举个例子,比如我们有一个数组[1,2,4,7,11,16],那么其对应的差分数组就是[1,1,2,3,4,5]。所以如果我们已知原序列的差分数组,我们就可以通过前缀和操作还原出原序列。
这两者的关系是互逆的,也就是说,原序列通过前缀和操作可以得到前缀和数组,前缀和数组通过差分操作又可以还原出原序列。反之亦然,原序列通过差分操作可以得到差分数组,差分数组通过前缀和操作又可以还原出原序列。
在一些复杂的问题中,我们可能需要同时使用这两种技巧,将问题简化成更易处理的形式。
更多举例
差分数组是针对数组内部元素变化的一种处理方式。比如我们有一个操作,需要对数组中的一个区间内的所有元素都同时加上或减去某一个数,这种操作用传统的方式需要遍历整个区间,并且对区间内的每个元素做相应的操作,但是利用差分数组的话,只需要修改区间两端的元素即可。
举个例子,我们有一个数组 [10, 20, 30, 40, 50],相应的差分数组为 [10, 10, 10, 10, 10],现在我们需要对第2至第4个元素每个都加10,如果直接操作原数组,则需要对索引为2、3、4的元素分别加10。但如果我们操作差分数组,则只需要对索引为2的元素加10,索引为5的元素减10,完成后差分数组变为[10, 20, 10, 10, 0],再通过前缀和我们可以得到修改后的原数组为[10, 30, 40, 50, 50]。
前缀和与差分数组的关系如下
代码实现
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.StreamTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// 创建 BufferedReader 和 StreamTokenizer 对象进行输入处理
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer st = new StreamTokenizer(reader);
// 读取并存储棋盘的大小n和操作次数m
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int m = (int) st.nval;
// 创建大小为 (n+2)x(n+2)的差分数组
int[][] board = new int[n + 2][n + 2];
// 读取操作,并对差分数组进行更新
for (int i = 0; i < m; i++) {
st.nextToken();
int x1 = (int) st.nval;
st.nextToken();
int y1 = (int) st.nval;
st.nextToken();
int x2 = (int) st.nval;
st.nextToken();
int y2 = (int) st.nval;
// 控制四个边界的差分,这样只有在[x1, y1, x2, y2]内的元素才会受影响
board[x1][y1]++;
board[x2+1][y2+1]++;
board[x1][y2+1]--;
board[x2+1][y1]--;
}
// 计算二维前缀和,先按每一行从左到右计算前缀和
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
board[i][j] += board[i][j-1];
}
}
// 然后再按每一列从上到下计算前缀和
for(int j=1;j<=n;j++) {
for (int i = 1; i <= n; i++) {
board[i][j] += board[i-1][j];
}
}
// 输出结果矩阵,当前位置有奇数次操作时,值为1,偶数次为0
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
System.out.print(board[i][j]%2); // 只关心是否为奇数次翻转,因此取模2
}
System.out.println(); // 每输出一行后,添加一个换行符
}
}
}
学的有点崩溃了老铁。
总结
新的知识点,学吧我就。
标签:10,前缀,int,差分,st,蓝桥,数组,2023,省赛 From: https://blog.csdn.net/DDDDWJDDDD/article/details/136834449