首页 > 其他分享 >2023年蓝桥杯省赛——棋盘

2023年蓝桥杯省赛——棋盘

时间:2024-03-20 17:59:44浏览次数:35  
标签:10 前缀 int 差分 st 蓝桥 数组 2023 省赛

目录

题目链接:10.棋盘 - 蓝桥云课 (lanqiao.cn)

思路

我的直接暴力思路

代码实现

前缀和思路

前缀和:

更多举例

差分数组:

更多举例

前缀和与差分数组的关系如下

代码实现 

总结


题目链接:10.棋盘 - 蓝桥云课 (lanqiao.cn)

思路

我的直接暴力思路

        我的这段Java代码模拟了一个棋盘上的翻转操作问题。初始化一个n x n大小的棋盘,棋盘上的每个位置可以是0(代表白色)或者1(代表黑色)。然后进行m次操作,每次操作指定一个子矩阵,并将其中的颜色进行翻转(0变1,1变0)。

下面详细介绍这段代码的任务流程:

  1. 代码开头导入了必要的IO类,并声明了Main类。

  2. main函数中,首先通过StreamTokenizer类对象st读取输入。

  3. 读取棋盘大小n和操作次数m

  4. 创建了一个n x n的二维数组arrs来表示棋盘,用0初始化,代表初始时所有位置都是白色。

  5. 使用一个for循环进行m次操作,每次读取四个整数,分别代表矩阵的左上角(x1, y1)和右下角(x2, y2)

  6. 调用change方法对指定的子矩阵执行翻转操作。

  7. 在所有操作完成后,使用两个嵌套的for循环遍历并打印出最终棋盘的状态。

change方法用于完成矩阵内颜色的翻转操作:

  1. 它接收棋盘的引用和两个坐标点作为参数,表示需要翻转颜色的矩形区域。

  2. 使用两个嵌套的for循环遍历这个矩形内的每个位置,在Java中数组索引是从0开始的,但题目中给的坐标可能是从1开始的,因此 x1y1x2y2都减去了1来映射到正确的索引。

  3. 对于矩形内的每个位置,如果当前是0(白色),就翻转为1(黑色);如果是1(黑色),就翻转为0(白色)。

  4. 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

相关文章

  • 蓝桥杯- 第14届模拟题第二套
     老规矩,先看外设要求......ADC,LED,LCD,KEY,EEPROM。除了EEPROM之外其它没什么新意,所以我们来看看EEPROM就可以了(其它可以在第一套模拟题中看到) /*****************************************************************************************************************/EE......
  • 专业屏幕录制剪辑工具Camtasia 2023.3.9中文版安装图文教程
    如果你需要制作视频教程、游戏直播或其他视频内容,那么一个好的录屏软件就是必不可少的。CamtasiaStudio是非常好用的录屏软件,它们可以记录计算机屏幕上发生的所有活动,并可捕捉声音。这些软件还提供了一些视频编辑功能,如裁剪、剪辑、加工、添加字幕等等,帮助用户制作出更加专业......
  • 第十三届蓝桥杯省赛B组
    目录试题A:排列字母试题B:寻找整数题解试题C:纸张尺寸试题D:数位排序试题E:蜂巢试题F:消除游戏暴力试题G:全排列的价值题解正解试题H:技能升级试题I:最长不下降子序列试题J:最优清零方案代码题解:滑动窗口试题A:排列字母见https://www.cnblogs.com/lushuang55/p/18069984试题B:寻找整数......
  • 蓝桥杯进阶03——光温显示综合应用
    一、分模块1.led和smg检测单片机上电后,8个LED灯从左到右依次点亮,然后再从左到右依次熄灭,进行LED的检测;8个数码管从左到右,逐个数码管全部段码点亮,然后再从左到右,这个数据管全部段码熄灭,进行数码管的检测。关闭蜂鸣器和继电器等无关设备。voidDisplaysmg(){ unsigned......
  • B3927 [GESP202312 四级]小杨的字典(入门小白版)
    本题包括:1.简单的map使用2.字符串简单处理本题参考洛谷题解: https://www.luogu.com.cn/problem/solution/B3927难度:普及-对于笔者而言:不会用map,在b站和csdn上搜map的使用方法,只能说是杂而乱杂在于:介绍的种类方法多种多样,但是底下的使用方法寥寥无几,与开头的介绍有......
  • 九连冠!禅道再获2023年「常用测试管理工具」第一名
    近期,软件测试网(51Testing)发布了2023年第17届《2023软件测试行业现状调查报告》。 报告数据显示,禅道项目管理软件凭借41.5%的企业使用占比,以压倒性的优势稳居「2023公司常用测试管理工具」榜首。与2022年禅道36.5%的企业使用率相比,2023年禅道的使用率同比增长了5%,呈逐年上升趋势......
  • S2-066漏洞分析与复现(CVE-2023-50164)
    Foreword自struts2官方纰漏S2-066漏洞已经有一段时间,期间断断续续地写,直到最近才完成。羞愧地回顾一下官方通告:2023.12.9发布,编号CVE-2023-50164,主要影响版本是2.5.0-2.5.32以及6.0.0-6.3.0,描述中提到了文件上传漏洞和目录穿越漏洞。开始以为这是个组合漏洞,其实不是,这是一个......
  • 蓝桥杯 2013 国 AC 网络寻路 第四届国赛 洛谷P8605
    [蓝桥杯2013国AC]网络寻路题目描述XXX国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包,为了安全起见,必须恰好被转发两次到达目的地。该包可能在任意一个节点产生,我们需要知道该网络中一共有多少种不同的转发路径。源地址和目标地......
  • 计数组合【2024蓝桥杯0基础】-学习笔记
    文章目录计数原理排列数组合数组合数性质例题分析代码复现例题2状态分析代码复现常见的排列组合问题圆排列代码复现第二类斯特林数感悟计数原理排列数组合数组合数性质例题分析代码复现defksm(a,b,c):ans=1%cwhileb!=0:......
  • 蓝桥杯单片机小蜜蜂学习笔记——矩阵键盘
    笔记仅供学习参考学习视频链接【基础技能07】矩阵键盘的扫描原理与基本应用基本原理(图片来自欧老师的视频)讲一下基本原理吧图片的左半部分是矩阵键盘的布局R1R2R3R4C1C2C3C4都是IO端口(就是电平高低可以人为控制)图片右半部分上面是独立按键下面是矩阵键盘两者的区......