蓝桥杯 之 前缀和与查分
文章目录
- 题目
- 求和
- 棋盘
- 挖矿
- 前缀和有利于快速求解 区间的和、异或值 、乘积等情况
- 差分是前缀和的反操作
前缀和
- 一维前缀和:
# 原始的数组num,下标从1到n
n = len(num)
pre = [0]*(n+1)
for i in range(n):pre[i+1] = pre[i] + num[i]
# 如果需要求解num[l] 到num[r] 的区间和
ans = pre[r] - pre[l-1]
- 二维前缀和
# 原本的数组是n*m形状的pre = [[0]*(m+1) for _ in range(n+1)]for i in range(n):for j in range(m):pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + num[i][j]
前缀和的应用:
-
当你想在一个区间进行统一的加上一个数或者减去一个数的时候,一个个操作会很慢,并且涉及多次操作的时候更新很麻烦,但是我们可以结合这个差分和前缀和进行快速求解
-
一维:
# 在区间l到r之间同时都加上a,那么我们只需在num[l] + a,在num[r+1] -a
# 然后求解前缀和即可,就可以得到每个位置的最后的值
- 二维:
# 1<=x1<=x2<=y1<=y2<=n
# 在x1,y1 到 x2,y2 之间都加上一个数
num[x1][y1] += a
num[x2+1]y2+1] +=a
num[x1][y2+1] -=a
num[x2+1][y1] -=a
差分:
- 一维差分:
# 1<=l<=r<=n ,那么区间l到r之间的和值为
ans = pre[r] - pre[l-1]
- 二维查分:
#
ans = pre[x2][y2] - pre[x2][y1] - pre[x1][y2] + pre[x1][y1]
题目
求和
求和
思路分析:
- 首先直接暴力是肯定不行的,所以得考虑转换?发现可以提取相同的元素,然后使用这个前缀和进行优化即可
import os
import sys# 请在此输入您的代码# 提取公因式,你会发现 ans = a1*(a2+···an) + a2*(a3+···an) + an-1*(an)n = int(input())
num = list(map(int,input().split()))pre = [0]*(n+1)
for i in range(n):pre[i+1] = pre[i] + num[i]ans = 0
for i in range(n-1):ans += num[i]*(pre[n]-pre[i+1])
print(ans)
棋盘
棋盘
思路分析:
- 这个题目得使用到这个二维的前缀和与查分进行优化
import os
import sys# 请在此输入您的代码# 其实和这个,异或操作是类似的
# 0表示白色,1表示黑色n,m = map(int,input().split())num = [[0]*(n+1) for _ in range(n+1)]for _ in range(m):x1,y1,x2,y2 = map(int,input().split())x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1num[x1][y1] += 1num[x2+1][y2+1] +=1num[x1][y2+1] -=1num[x2+1][y1] -=1# 求解二维前缀和
dp = [[0]*(n+1) for _ in range(n+1)]for i in range(n):for j in range(n):dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j] + num[i][j])%2for i in range(1, n + 1):row = "".join(str(dp[i][j]) for j in range(1, n + 1))print(row)
挖矿
挖矿
思路分析:
- 首先明确一个问题,在坐标轴上移动,最多只能转向一次:证明,设你转向多次之后到达左端点是
l
,到达右端点的坐标是r
,如果你直接一开始不转向,直接到达左端点l
,然后再直接向后转向右边,那么到达的距离是肯定比r
大的
import os
import sys# 请在此输入您的代码
n,m = map(int,input().split())
num = list(map(int,input().split()))
# 开的空间
l ,r = [0]*(m + 1),[0]*(m + 1)iszero = 0for i in num:if i > 0 and i <= m:r[i] += 1if i < 0 and abs(i) <= m:l[abs(i)] += 1if i == 0:iszero = 1# 计算出其中的左和右可以到达的位置所能得到的矿
for i in range(1,m+1):r[i] += r[i-1]l[i] += l[i-1]
ans = 0# 枚举可以到达的端点,注意左边和右边
for j in range(1,m//2 + 1):ans = max(ans,r[j] + l[m-2*j],l[j] + r[m-2*j])print(ans+iszero)
相关文章:

蓝桥杯 之 前缀和与查分
文章目录 题目求和棋盘挖矿 前缀和有利于快速求解 区间的和、异或值 、乘积等情况差分是前缀和的反操作 前缀和 一维前缀和: # 原始的数组num,下标从1到n n len(num) pre [0]*(n1) for i in range(n):pre[i1] pre[i] num[i] # 如果需要求解num[l] 到num[r] 的区…...
GB28181开发--ZLMediaKit+WVP+Jessibuca
一、核心组件功能 1、ZLMediaKit 定位:基于 C++11 的高性能流媒体服务框架,支持 RTSP/RTMP/HLS/HTTP-FLV 等协议互转,具备低延迟(最低 100ms)、高并发(单机 10W 级连接)特性,适用于商用级流媒体服务器部署。 特性:跨平台(Linux/Windows/ARM 等)、支持 …...
Ubuntu20.04 在离线机器上安装 NVIDIA Container Toolkit
步骤 1.下载4个安装包 Index of /nvidia-docker/libnvidia-container/stable/ nvidia-container-toolkit-base_1.13.5-1_amd64.deb libnvidia-container1_1.13.5-1_amd64.deb libnvidia-container-tools_1.13.5-1_amd64.deb nvidia-container-toolkit_1.13.5-1_amd64.deb 步…...
如何快速上手RabbitMQ 笔记250304
如何快速上手RabbitMQ 要快速上手 RabbitMQ,可以按照以下步骤进行,从安装到基本使用逐步掌握核心概念和操作: 1. 理解核心概念 Producer(生产者):发送消息的程序。Consumer(消费者)…...
无人机端部署 AI 模型,实现实时数据处理和决策
在无人机端部署 AI 模型,实现实时数据处理和决策,是提升无人机智能化水平的关键技术之一。通过将 AI 模型部署到无人机上,可以实现实时目标检测、路径规划、避障等功能。以下是实现这一目标的详细方案和代码示例。 一、实现方案 1. 硬件选择…...

CentOS 7中安装Dify
Dify 是一个开源的 LLM 应用开发平台。其直观的界面结合了 AI 工作流、RAG 管道、Agent、模型管理、可观测性功能等,让您可以快速从原型到生产。尤其是我们本地部署DeepSeek等大模型时,会需要用到Dify来帮我们快捷的开发和应用。 大家可以参考学习它的中…...

CoDrivingLLM
CoDrivingLLM 思路 1.输入和输出 输入 算法的输入包括车辆当前时刻的状态 S t S_t St ,这个状态包含了车辆的位置、速度、行驶方向等信息;以及参与协同驾驶的联网自动驾驶汽车列表C,用于确定需要进行决策的车辆集合。 输出 输出为车辆…...

Centos7升级openssl和openssh最新版
1、事前准备 下载openssl3.4.1和openssh9.9p2压缩包上传到服务器 https://cdn.openbsd.org/pub/OpenBSD/OpenSSH/portable// Release OpenSSL 3.4.1 openssl/openssl GitHub 2、查看centos7、ssh以及openssl的版本信息 # 查看CentOS系统版本信息 cat /etc/redhat-release …...

相控阵扫盲
下图展示天线增益 在仰角为0度的情况下随着方位角的变化而变化。需要注意到的是在天线视轴方向上的高增益主瓣上还有几个低增益旁瓣 阵列因子乘以新的阵元方向图会形成指向性更强的波速...
nginx 配置 301跳转
HTTP 跳转到 HTTPS 将所有 HTTP 请求(80 端口)跳转到 HTTPS(443 端口): server {listen 80;server_name example.com;# 跳转到 HTTPSreturn 301 https://$host$request_uri; }server {listen 443 ssl;server_name exa…...

开发环境搭建-03.后端环境搭建-使用Git进行版本控制
一.Git进行版本控制 我们对项目开发就会产生很多代码,我们需要有效的将这些代码管理起来,因此我们真正开发代码前需要把我们的Git环境搭建好。通过Git来管理我们项目的版本,进而实现版本控制。 首先我们使用Git创建本地仓库,然后…...

vivado 充分利用 IP 核
充分利用 IP 核 使用预先验证的 IP 核能够大幅减少设计和验证工作量,从而加速产品上市进程。如需了解更多有利用 IP 的信息,请参 阅以下资源: • 《 Vivado Design Suite 用户指南:采用 IP 进行设计》 (UG896) [ 参照 1…...
外盘农产品期货数据:历史高频分钟回测的分享下载20250305
外盘农产品期货数据:历史高频分钟回测的分享下载20250305 在国际期货市场中,历史分钟高频数据的作用不可小觑。这些数据以分钟为时间尺度,详细记录了期货合约的价格变动和交易量信息,为投资者提供了全面、深入的市场分析视角。通…...

计算机毕设-基于springboot的网上商城系统的设计与实现(附源码+lw+ppt+开题报告)
博主介绍:✌多个项目实战经验、多个大型网购商城开发经验、在某机构指导学员上千名、专注于本行业领域✌ 技术范围:Java实战项目、Python实战项目、微信小程序/安卓实战项目、爬虫大数据实战项目、Nodejs实战项目、PHP实战项目、.NET实战项目、Golang实战…...

用DeepSeek-R1-Distill-data-110k蒸馏中文数据集 微调Qwen2.5-7B-Instruct!
下载模型与数据 模型下载: huggingface: Qwen/Qwen2.5-7B-Instruct HF MirrorWe’re on a journey to advance and democratize artificial intelligence through open source and open science.https://hf-mirror.com/Qwen/Qwen2.5-7B-Instruct 魔搭&a…...

【C++设计模式】第四篇:建造者模式(Builder)
注意:复现代码时,确保 VS2022 使用 C17/20 标准以支持现代特性。 分步骤构造复杂对象,实现灵活装配 1. 模式定义与用途 核心目标:将复杂对象的构建过程分离,使得同样的构建步骤可以创建不同的表示形式。 常见场景&am…...

【杂谈】信创电脑华为w515(统信系统)登录锁定及忘记密码处理
华为w515麒麟芯片版,还有非麒麟芯片版本,是一款信创电脑,一般安装的UOS系统。 准备一个空U盘,先下载镜像文件及启动盘制作工具,连接如下: 百度网盘 请输入提取码 http://livecd.uostools.com/img/apps/l…...

VBA信息获取与处理第五节:如何在单个工作表中查找某个给定值
《VBA信息获取与处理》教程(版权10178984)是我推出第六套教程,目前已经是第一版修订了。这套教程定位于最高级,是学完初级,中级后的教程。这部教程给大家讲解的内容有:跨应用程序信息获得、随机信息的利用、电子邮件的发送、VBA互…...
版本控制器Git和gdb
一.版本控制器Git 1.版本控制简单来讲可以对每一份代码版本进行复制保存,保证每一版代码都可查 2.仓库的本质也是一个文件夹 3.git既是一个客户端,也是一个服务器,是一个版本控制器。而gitee和GitHub都是基于git的网站或平台 4.git的基本…...

关于tresos Studio(EB)的MCAL配置之GPT
概念 GPT,全称General Purpose Timer,就是个通用定时器,取的名字奇怪了点。定时器是一定要的,要么提供给BSW去使用,要么提供给OS去使用。 配置 General GptDeinitApi控制接口Gpt_DeInit是否启用 GptEnableDisable…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...

华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...

【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...

【PX4飞控】mavros gps相关话题分析,经纬度海拔获取方法,卫星数锁定状态获取方法
使用 ROS1-Noetic 和 mavros v1.20.1, 携带经纬度海拔的话题主要有三个: /mavros/global_position/raw/fix/mavros/gpsstatus/gps1/raw/mavros/global_position/global 查看 mavros 源码,来分析他们的发布过程。发现前两个话题都对应了同一…...