蓝桥杯练习题——差分

1.空调

在这里插入图片描述

思路

1.区间同时加减 1,可以转换成一个差分数组两个端点的操作
2.用 p 减去 t 数组,得到要消除的数组 a,对 a 求差分数组
3.差分数组一正一负为一个操作,因为是把这个原数组区间加上了 1,单独的正负为一个操作
4.总共需要的操作就是差分数组里 max(正数和, 负数和)

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], t[N], a[N];
int n;int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &p[i]);for(int i = 1; i <= n; i++){scanf("%d", &t[i]);p[i] -= t[i];}int pos = 0, neg = 0;for(int i = 1; i <= n; i++){a[i] = p[i] - p[i - 1];if(a[i] > 0) pos += a[i];else neg -= a[i];}printf("%d", max(pos, neg));return 0;
}

2.差分

在这里插入图片描述

思路

模板题

// 模板1
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);b[i] = a[i] - a[i - 1];}int l, r, c;while(m--){scanf("%d%d%d", &l, &r, &c);b[l] += c;b[r + 1] -= c;}for(int i = 1; i <= n; i++){a[i] = a[i - 1] + b[i];printf("%d ", a[i]);}return 0;
}// 模板2
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m;int insert(int l, int r, int c){a[l] += c;a[r + 1] -= c;
}int main(){scanf("%d%d", &n, &m);int x;for(int i = 1; i <= n; i++){scanf("%d", &x);insert(i, i, x);}int l, r, c;while(m--){scanf("%d%d%d", &l, &r, &c);insert(l, r, c);}for(int i = 1; i <= n; i++){a[i] += a[i - 1];printf("%d ", a[i]);}return 0;
}

3.差分矩阵

在这里插入图片描述

思路

模板题

// 模板1
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
int n, m, q;int main(){scanf("%d%d%d", &n, &m, &q);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &a[i][j]);b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];}}int x1, y1, x2, y2, c;while(q--){scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];printf("%d ", a[i][j]);}printf("\n");}return 0;
}// 模板2
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N][N];
int n, m, q;int insert(int x1, int y1, int x2, int y2, int c){a[x1][y1] += c;a[x2 + 1][y1] -= c;a[x1][y2 + 1] -= c;a[x2 + 1][y2 + 1] += c;
}int main(){scanf("%d%d%d", &n, &m, &q);int x;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d", &x);insert(i, j, i, j, x);}}int x1, y1, x2, y2, c;while(q--){scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);insert(x1, y1, x2, y2, c);}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];printf("%d ", a[i][j]);}printf("\n");}return 0;
}

4.棋盘

在这里插入图片描述

思路

取反就是把这个区域都加上 1,每个位置如果和为偶数,那就是没变,和为奇数就是反了

#include<iostream>
using namespace std;
const int N = 2e3 + 10;
int a[N][N], b[N][N];
int n, m;int main(){scanf("%d%d", &n, &m);int x1, y1, x2, y2;while(m--){scanf("%d%d%d%d", &x1, &y1, &x2, &y2);b[x1][y1]++;b[x2 + 1][y1]--;b[x1][y2 + 1]--;b[x2 + 1][y2 + 1]++;}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){a[i][j] = (a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j]) & 1;printf("%d", a[i][j]);}printf("\n");}return 0;
}

5.重新排序

在这里插入图片描述

思路

用差分统计每个位置被加了多少次,加的越多的位置选择越大的数

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;
long long res1, res2;int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);scanf("%d", &m);int l, r;while(m--){scanf("%d%d", &l, &r);b[l]++;b[r + 1]--;}for(int i = 1; i <= n; i++) b[i] += b[i - 1];for(int i = 1; i <= n; i++) res1 += 1ll * a[i] * b[i];sort(a + 1, a + n + 1);sort(b + 1, b + n + 1);for(int i = 1; i <= n; i++) res2 += 1ll * a[i] * b[i];printf("%lld", res2 - res1);return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python把excel内容保存为图片(非统计图而是纯原表格数据)

一、引入 excel2img 库&#xff0c;没有的话使用 pip install excel2img进行安装 二、采用如下方法进行图片生成 excel文件名为&#xff1a;111.xlsx excel表格里面的sheet名称列表为 [Sheet1, Sheet2] 最终保存为以sheet名称.png的图片 支持跨表格合并项 import excel2i…

《手把手教你》系列技巧篇(十五)-java+ selenium自动化测试-元素定位大法之By xpath中卷(详细教程)

1.简介 按宏哥计划&#xff0c;本文继续介绍WebDriver关于元素定位大法&#xff0c;这篇介绍定位倒数二个方法&#xff1a;By xpath。xpath 的定位方法&#xff0c; 非常强大。 使用这种方法几乎可以定位到页面上的任意元素。 2.什么是xpath&#xff1f; xpath 是XML Path的…

Win11系统实现adb命令向安卓子系统安装APP

Win11系统实现通过adb命令向安卓子系统安装已下载好的apk包。 要实现以上目标&#xff0c;我们需要用到一个Android SDK 的组件Android SDK Platform-Tools &#xff01;这个组件呢其实是被包含在 Android Studio中的&#xff0c;如果你对安卓开发有所了解对此应该不会陌生&…

超全面!Linux学习资料大合集,21套从入门到进阶,看这篇就够了

本文将为那些渴望学习Linux&#xff0c;但又缺乏相应资料和方向的朋友&#xff0c;提供21套Linux优质资料&#xff0c;包含入门到进阶&#xff0c;希望能对大家有所帮助。 此合集内容及其丰富&#xff0c;涉及方面颇多&#xff0c;不仅适合Linux入门学习的朋友&#xff0c;运维…

Linux(CentOS)学习

一、认识Linux 1、如何修改Linux时区 2、配置固定IP 3、重启网络服务 3、小技巧快捷键 4、环境变量设置 5、Linux文件的上传和下载 6、压缩和解压 二、基础命令 1、目录命令 (1、)查看目录内容&#xff08;ls&#xff09; 1、ls //查看当前目录内容 2、- a //显示隐藏内容 3…

Web自动化测试平台开发---Automated_platform

一、项目简介 历时一个假期&#xff0c;Automated_platform 第一版完工&#xff0c;是一款基于po模式的自动化测试平台,采用后端技术为DjangoceleryRabbitMQmysql 配置mysql数据库&#xff0c;进行数据迁移后&#xff0c;运行项目后&#xff0c;即可成功访问http://127.0.0.1:8…

【王道操作系统】ch1计算机系统概述-05操作系统引导

文章目录 【王道操作系统】ch1计算机系统概述-05操作系统引导01 什么是操作系统引导02 磁盘里边有哪些相关数据&#xff08;1&#xff09;主引导记录&#xff08;MBR&#xff09;&#xff08;2&#xff09;活动分区&#xff08;一般是C盘&#xff09; 03 操作系统引导的过程 【…

中间件-Nginx加固(控制超时时间限制客户端下载速度并发连接数)

中间件-Nginx加固&#xff08;控制超时时间&限制客户端下载速度&并发连接数&#xff09; 1.1 Nginx 控制超时时间配置1.2 Nginx 限制客户端下载速度&并发连接数 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 1.1 Nginx 控制超…

Arduino应用开发——使用GUI-Guider制作LVGL UI并导入ESP32运行

Arduino应用开发——使用GUI-Guider制作LVGL UI并导入ESP32运行 目录 Arduino应用开发——使用GUI-Guider制作LVGL UI并导入ESP32运行前言1 使用GUI-Guider设计UI1.1 创建工程1.2 设计UI 2 ESP工程导入UI2.1 移植LVGL2.2 移植UI文件2.3 调用UI文件2.4 烧录测试 结束语 前言 GU…

Spring 日志

在Java程序中的日志&#xff0c;想必我们已经不陌生了吧&#xff01;对于控制台System.out.println();输出的每个程序都可以看作成日志&#xff01; 但是&#xff0c;相比于真正意义上的日志还是有很大区别的&#xff01; 上述每个红框框所标注的都是真正日志的组成数据&#…

redis运维

1.备份redis配置文件 cp /etc/redis.conf /etc/redis.conf.bak 2.将redis中不要的注释和空行删除 sed -i /^#/d; /^$/d /etc/redis.conf 3.redis配置文件 bing 0.0.0.0 &#xff1a;绑定本机所有网卡 daemonize yes&#xff1a;设置后台运行 requirepass redispwd…

【本科组冠名奖】2023年第八届数维杯数学建模挑战赛获奖感言

美国大学生数学建模竞赛已结束过半&#xff0c;现在又迎来了2024年第九届数维杯国赛&#xff0c;准备参加今年数维杯国赛的同学&#xff0c;今天我们一起看看去年优秀的选手都有什么获奖感言吧~希望能帮到更多热爱数学建模的同学。据说文末在看点赞的大佬都会直冲国奖呢&#x…

C++ //练习 10.31 修改前一题的程序,使其只打印不重复的元素。你的程序应使用unique_copy(参见10.4.1节,第359页)。

C Primer&#xff08;第5版&#xff09; 练习 10.31 练习 10.31 修改前一题的程序&#xff0c;使其只打印不重复的元素。你的程序应使用unique_copy&#xff08;参见10.4.1节&#xff0c;第359页&#xff09;。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09…

STM32 (1)

1.基本信息 stm32是由ST公司生产的一种32位微控制器&#xff08;单片机&#xff09;。 1.1 各种型号 stm32是32位单片机的总称&#xff0c;有多种不同的系列。 32即用32个比特位表示一个地址&#xff0c;寻址范围&#xff1a;0x00000000 --0xffffffff (4GB) 1.2 存储密度 …

设计模式(十五)状态模式

请直接看原文:设计模式系列 ------------------------------------------------------------------------------------------------------------------------------- 前言 建议在阅读本文前先阅读设计模式&#xff08;十一&#xff09;策略模式这篇文章&#xff0c;虽说状态…

阿里云2核4G服务器租用价格85元一年,30元3个月

阿里云2核4G服务器多少钱一年&#xff1f;2核4G服务器1个月费用多少&#xff1f;2核4G服务器30元3个月、85元一年&#xff0c;轻量应用服务器2核4G4M带宽165元一年&#xff0c;本文阿里云服务器网整理的2核4G参加活动的主机是ECS经济型e实例和u1云服务器&#xff0c;阿里云服务…

javaWebssh水利综合信息管理系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计

一、源码特点 java ssh水利综合信息管理系统是一套完善的web设计系统&#xff08;系统采用ssh框架进行设计开发&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCA…

Qt 简约美观的加载动画 第九季

这次和大家分享6个非常清爽的加载动画. &#x1f60a; 效果如下 &#x1f60a; 一共三个文件 , 可以直接编译运行的呢 //main.cpp #include "LoadingAnimWidget.h" #include <QApplication> #include <QGridLayout> int main(int argc, char *argv[]) …

【javascript】快速入门javascript

本文前言及说明 适合学过一门语言有一定基础的人看。 省略最初学习编程时的各种编程重复的基础知识。 javascript简介 编程语言&#xff08;主前端&#xff09; 用途&#xff1a;主web前后端&#xff0c;游戏&#xff0c;干别人网站 优点&#xff1a;速度快&#xff0c;浏…

用BIO实现tomcat

一、前言 本课程的难度较高&#xff0c;需要将Servlet原理和IO课程全部学完。 二、当前项目使用方式 (1).自定义servlet 自定义servlet需要实现WebServlet并且实现name和urlMapping 重启进行访问 http://localhost:8090/myServlet (2).自定义html 重启进行访问 http://loc…