棋盘(来源:第十四届蓝桥杯省赛JavaA/C/研究生组 , 第十四届蓝桥杯省赛PythonC组)

小蓝拥有 n×n大小的棋盘,一开始棋盘上全都是白子。

小蓝进行了 m 次操作,每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色,黑色棋子变为白色)。

请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式

输入的第一行包含两个整数 n,m,用一个空格分隔,表示棋盘大小与操作数。

接下来 m 行每行包含四个整数 x1,y1,x2,y2,相邻整数之间使用一个空格分隔,表示将在 x1 至 x2行和 y1 至 y2 列中的棋子颜色取反。

输出格式

输出 n行,每行 n 个 0 或 1 表示该位置棋子的颜色。

如果是白色则输出 0,否则输出 1。

数据范围

对于 30% 的评测用例,1≤n,m≤500;
对于所有评测用例,1≤n,m≤20001,1≤x1≤x2≤n,1≤y1≤y2≤n。

输入样例:
3 3
1 1 2 2
2 2 3 3
1 1 3 3
输出样例:
001
010
100

思路:题目本身不难,暴力做法会TLE如下:   

差分矩阵(Difference Matrix)是一种用于高效处理区间更新操作的方法。它的主要思路是通过对原始数组进行预处理,构建一个与原数组相同大小的矩阵,其中每个元素表示与原数组相邻元素的差值。这样,对原数组的区间进行更新时,只需要在差分矩阵的两个位置进行修改,而不必逐个更新原数组的所有元素。
原理:
假设原数组为 A,差分数组为 D,数组长度为 n。

1.构建差分数组 D:

  • D[i] = A[i] - A[i-1],对于 i 从 1 到 n-1。
  • D[0] = A[0]。

这样,差分数组 D 中的每个元素表示原数组相邻元素之间的差值。
2.区间更新操作:

  • 对于原数组 A 的区间 [l, r] 进行增加或减少的操作,只需更新差分数组 D 中的两个位置,即 D[l] 和 D[r+1]。
  • D[l] 增加(或减少)的值,表示从原数组 A 的第 l 个元素开始,后续所有元素都增加(或减少)这个值。
  • D[r+1] 减少(或增加)的值,表示从原数组 A 的第 r+1 个元素开始,后续所有元素都减少(或增加)这个值。
  • 对差分数组进行前缀和操作,得到更新后的原数组。

3.例子:

  • 假设原数组 A = [1, 2, 3, 4, 5]。

构建差分数组 D:

  • D = [1, 1, 1, 1, 1]

对原数组的区间 [2, 4] 进行增加 2 的操作:

  • 更新差分数组 D:D[2] += 2,D[5] -= 2。
  • 更新后的差分数组 D:[1, 3, 1, 1, -1]。

4.对差分数组进行前缀和操作:

  • D[0] = 1
  • D[1] = 1 + D[0] = 2
  • D[2] = 1 + D[1] = 3
  • D[3] = 1 + D[2] = 4
  • D[4] = -1 + D[3] = 3

得到更新后的原数组 A:[1, 3, 4, 5, 3]。

TLE代码: 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=2010;
int a[N][N];
int n,m,x1,x2,y1,y2;

int main(){
    cin>>n>>m;
    memset(a,0,sizeof a);
    while(m--)
    {
        cin>>x1>>y1>>x2>>y2;
        for(int i=x1;i<=x2;i++)
            for(int j=y1;j<=y2;j++)
                a[i][j]++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<a[i][j]%2;
        }
        cout<<endl;
    }
}

差分矩阵代码:

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=2010;
int s[N][N];
int n,m,x1,x2,y1,y2;

int main(){
    cin>>n>>m;
    memset(s,0,sizeof s);
    while(m--)
    {
        cin>>x1>>y1>>x2>>y2;
            s[x1][y1]++;
            s[x1][y2+1]--;
            s[x2+1][y1]--;
            s[x2+1][y2+1]++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            cout<<(s[i][j]&1);
        }
        cout<<endl;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/353713.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Qt扩展-QXlsx读写Excel配置使用

QXlsx读写Excel配置使用 一、概述1. 功能概述2. 其他维护 二、安装1. 下载源码2. 配置项目3. 测试代码4. 运行结果 一、概述 项目介绍&#xff1a;https://qtexcel.github.io/QXlsx/Example.html GitHub&#xff1a;https://github.com/QtExcel/QXlsx/tree/master QXlsx 是一个…

【算法】闇の連鎖(树上差分,LCA)

题目 传说中的暗之连锁被人们称为 Dark。 Dark 是人类内心的黑暗的产物&#xff0c;古今中外的勇者们都试图打倒它。 经过研究&#xff0c;你发现 Dark 呈现无向图的结构&#xff0c;图中有 N 个节点和两类边&#xff0c;一类边被称为主要边&#xff0c;而另一类被称为附加边…

C++设计模式介绍:优雅编程的艺术

物以类聚 人以群分 文章目录 简介为什么有设计模式&#xff1f; 设计模式七大原则单一职责原则&#xff08;Single Responsibility Principle - SRP&#xff09;开放封闭原则&#xff08;Open/Closed Principle - OCP&#xff09;里氏替换原则&#xff08;Liskov Substitution …

【C++修行之道】STL(初识list、stack)

目录 一、list 1.1list的定义和结构 以下是一个示例&#xff0c;展示如何使用list容器: 1.2list的常用函数 1.3list代码示例 二、stack 2.1stack的定义和结构 stack的常用定义 2.2常用函数 2.3stack代码示例 一、list 1.1list的定义和结构 list的使用频率不高&#…

常见的核函数

在机器学习中&#xff0c;特别是在支持向量机&#xff08;SVM&#xff09;和其他基于核的方法中&#xff0c;核函数是一种用来计算数据点在高维空间中相对位置的方法。核函数能够使得算法在不显式地映射数据到高维空间的情况下&#xff0c;仍然能够处理线性不可分的数据。常见的…

RPC教程 6.负载均衡

1.负载均衡策略 假设有多个服务实例&#xff0c;而每个实例都提供相同的功能&#xff0c;为了提高整个系统的吞吐量&#xff0c;每个实例部署在不同的机器上。客户端可以选择任意一个实例进行调用&#xff0c;获取想要的结果。那如何选择呢&#xff1f;取决于负载均衡的策略。…

【WPF.NET开发】WPF中的双向功能

本文内容 FlowDirectionFlowDocumentSpan 元素非文本元素的 FlowDirection数字替换 与其他任何开发平台不同&#xff0c;WPF 具有许多支持双向内容快速开发的功能&#xff0c;例如&#xff0c;同一文档中混合了从左到右和从右到左的数据。 同时&#xff0c;WPF 也为需要双向功…

JVM基础知识汇总篇

☆* o(≧▽≦)o *☆嗨~我是小奥&#x1f379; &#x1f4c4;&#x1f4c4;&#x1f4c4;个人博客&#xff1a;小奥的博客 &#x1f4c4;&#x1f4c4;&#x1f4c4;CSDN&#xff1a;个人CSDN &#x1f4d9;&#x1f4d9;&#x1f4d9;Github&#xff1a;传送门 &#x1f4c5;&a…

企业计算机中了360后缀勒索病毒怎么办,360后缀勒索病毒解密流程

企业计算机服务器在生产运营过程中发挥着巨大作用&#xff0c;为企业带来极大便利&#xff0c;存储着企业的重要核心数据&#xff0c;但同时也成为众多勒索病毒攻击的目标。近期&#xff0c;云天数据恢复中心接到很多企业的求助&#xff0c;企业的计算机服务器遭到了360后缀勒索…

多文件开发

当所有的类都写在main.m这个源文件之中、将不利于后期的维护和团队开发 推荐的方式 把1个类写在1个模块之中&#xff0c;而1个模块至少包含两个文件 h头文件 1.写的类声明因为要用到Foundation框架中的类NS0 bject所以在这个头文件中要引入 Foundationa 2.框架的头文件 3.然后…

qemu搭建arm64 linux kernel环境

一、环境准备 ubuntu 22.04 内核源码&#xff1a;linux-6.6.1 &#xff08;直接上最新版&#xff09; 下载链接&#xff1a;The Linux Kernel Archives 交叉编译工具链&#xff1a; sudo apt-get install gcc-12-aarch64-linux-gnu 具体能用的版本gcc-XX-arch64-linux-gnu…

python_ACM模式《剑指offer刷题》链表2

题目&#xff1a; 例如 面试tips&#xff1a; 询问有无时间复杂度或空间复杂度的限制。 思路&#xff1a; 本题的本质就是复杂链表的深拷贝 1. 暴力解法 → 第一次遍历原链表时构建一个复制了next的新链表&#xff0c;第二次遍历原链表&#xff0c;对每个原链表的节点的ran…

幻兽帕鲁服务器多少钱?4核16G支持32人在线吗?

4核16G服务器是幻兽帕鲁Palworld推荐的配置&#xff0c;阿里云和腾讯云均推出针对幻兽帕鲁的4核16G服务器&#xff0c;阿里云4核16G幻兽帕鲁专属服务器32元1个月、66元3个月&#xff0c;腾讯云4核16G14M服务器66元1个月、277元3个月、1584元一年。云服务器吧yunfuwuqiba.com分享…

一、MongoDB、express的安装和基本使用

数据库【Sqlite3、MongoDB、Mysql】简介&小记 Sqlite3&#xff1a; SQLite3是一个轻量级的数据库系统&#xff0c;它被设计成嵌入式数据库。这意味着它是一个包含在应用程序中的数据库&#xff0c;而不是独立运行的系统服务。适用场景&#xff1a;如小型工具、游戏、本地…

node.js Redis SETNX命令实现分布式锁解决超卖/定时任务重复执行问题

Redis SETNX 命令背后的原理探究 当然&#xff0c;让我们通过一个简单的例子&#xff0c;使用 Redis CLI&#xff08;命令行界面&#xff09;来模拟获取锁和释放锁的过程。 在此示例中 获取锁: # 首先&#xff0c;设置锁密钥的唯一值和过期时间(秒) 127.0.0.1:6379> SET …

ChatGPT 官方中文页面上线

根据页面显示&#xff0c;OpenAI 现已推出 ChatGPT 的多语言功能 Alpha 版测试&#xff0c;允许用户选择不同语言的界面进行交互。 如下图所示&#xff0c;ChatGPT 会检测系统当前所使用的语言&#xff0c;并提示用户进行语言切换。 用户也可通过设置页面选择其他语言。目前&a…

企业转型:虚拟化对云计算的影响

虚拟化被认为是IT行业最优秀的技术之一。虚拟化提供的灵活性和效率&#xff0c;有助于企业根据不断变化的需求扩展其IT基础设施。虚拟化是云基础设施的基础&#xff0c;允许按需动态分配和管理计算资源。这种适应性对于满足现代企业的多样化需求至关重要&#xff0c;因为现代企…

深度学习之处理多维特征的输入

我们首先来看一个糖尿病的数据集&#xff1a; 在数据集中&#xff0c;我们称每一行叫做sample&#xff0c;表示一个样本&#xff0c;称每一列是feature&#xff0c;也就是特征在数据库里面这就是一个关系表&#xff0c;每一行叫做记录&#xff0c;每一列叫做字段。 每一个样本都…

山西电力市场日前价格预测【2024-01-29】

日前价格预测 预测说明&#xff1a; 如上图所示&#xff0c;预测明日&#xff08;2024-01-29&#xff09;山西电力市场全天平均日前电价为279.99元/MWh。其中&#xff0c;最高日前电价为397.38元/MWh&#xff0c;预计出现在07:45。最低日前电价为0.00元/MWh&#xff0c;预计出…

【计算机专业学习委员必备自动化催作业通知】

文章目录 前言一、前期准备zfile部署mysql服务搭建 二、编写python脚本python代码 三、总结 前言 大家好&#xff01;我是一名计算机专业的菜鸟&#xff0c;作为这个专业的学习委员&#xff0c;我觉得收电子版作业是一件非常麻烦的事情&#xff0c;作业实验科目也比较多&#…