当前位置: 首页 > news >正文

蓝桥杯 之 前缀和与查分

文章目录

  • 题目
    • 求和
    • 棋盘
    • 挖矿

  • 前缀和有利于快速求解 区间的和、异或值 、乘积等情况
  • 差分是前缀和的反操作

前缀和

  • 一维前缀和:
# 原始的数组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)

相关文章:

蓝桥杯 之 前缀和与查分

文章目录 题目求和棋盘挖矿 前缀和有利于快速求解 区间的和、异或值 、乘积等情况差分是前缀和的反操作 前缀和 一维前缀和&#xff1a; # 原始的数组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&#xff0c;可以按照以下步骤进行&#xff0c;从安装到基本使用逐步掌握核心概念和操作&#xff1a; 1. 理解核心概念 Producer&#xff08;生产者&#xff09;&#xff1a;发送消息的程序。Consumer&#xff08;消费者&#xff09…...

无人机端部署 AI 模型,实现实时数据处理和决策

在无人机端部署 AI 模型&#xff0c;实现实时数据处理和决策&#xff0c;是提升无人机智能化水平的关键技术之一。通过将 AI 模型部署到无人机上&#xff0c;可以实现实时目标检测、路径规划、避障等功能。以下是实现这一目标的详细方案和代码示例。 一、实现方案 1. 硬件选择…...

CentOS 7中安装Dify

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

CoDrivingLLM

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

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 请求&#xff08;80 端口&#xff09;跳转到 HTTPS&#xff08;443 端口&#xff09;&#xff1a; server {listen 80;server_name example.com;# 跳转到 HTTPSreturn 301 https://$host$request_uri; }server {listen 443 ssl;server_name exa…...

开发环境搭建-03.后端环境搭建-使用Git进行版本控制

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

vivado 充分利用 IP 核

充分利用 IP 核 使用预先验证的 IP 核能够大幅减少设计和验证工作量&#xff0c;从而加速产品上市进程。如需了解更多有利用 IP 的信息&#xff0c;请参 阅以下资源&#xff1a; • 《 Vivado Design Suite 用户指南&#xff1a;采用 IP 进行设计》 (UG896) [ 参照 1…...

外盘农产品期货数据:历史高频分钟回测的分享下载20250305

外盘农产品期货数据&#xff1a;历史高频分钟回测的分享下载20250305 在国际期货市场中&#xff0c;历史分钟高频数据的作用不可小觑。这些数据以分钟为时间尺度&#xff0c;详细记录了期货合约的价格变动和交易量信息&#xff0c;为投资者提供了全面、深入的市场分析视角。通…...

计算机毕设-基于springboot的网上商城系统的设计与实现(附源码+lw+ppt+开题报告)

博主介绍&#xff1a;✌多个项目实战经验、多个大型网购商城开发经验、在某机构指导学员上千名、专注于本行业领域✌ 技术范围&#xff1a;Java实战项目、Python实战项目、微信小程序/安卓实战项目、爬虫大数据实战项目、Nodejs实战项目、PHP实战项目、.NET实战项目、Golang实战…...

用DeepSeek-R1-Distill-data-110k蒸馏中文数据集 微调Qwen2.5-7B-Instruct!

下载模型与数据 模型下载&#xff1a; huggingface&#xff1a; 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)

注意&#xff1a;复现代码时&#xff0c;确保 VS2022 使用 C17/20 标准以支持现代特性。 分步骤构造复杂对象&#xff0c;实现灵活装配 1. 模式定义与用途 核心目标&#xff1a;将复杂对象的构建过程分离&#xff0c;使得同样的构建步骤可以创建不同的表示形式。 常见场景&am…...

【杂谈】信创电脑华为w515(统信系统)登录锁定及忘记密码处理

华为w515麒麟芯片版&#xff0c;还有非麒麟芯片版本&#xff0c;是一款信创电脑&#xff0c;一般安装的UOS系统。 准备一个空U盘&#xff0c;先下载镜像文件及启动盘制作工具&#xff0c;连接如下&#xff1a; 百度网盘 请输入提取码 http://livecd.uostools.com/img/apps/l…...

VBA信息获取与处理第五节:如何在单个工作表中查找某个给定值

《VBA信息获取与处理》教程(版权10178984)是我推出第六套教程&#xff0c;目前已经是第一版修订了。这套教程定位于最高级&#xff0c;是学完初级&#xff0c;中级后的教程。这部教程给大家讲解的内容有&#xff1a;跨应用程序信息获得、随机信息的利用、电子邮件的发送、VBA互…...

版本控制器Git和gdb

一.版本控制器Git 1.版本控制简单来讲可以对每一份代码版本进行复制保存&#xff0c;保证每一版代码都可查 2.仓库的本质也是一个文件夹 3.git既是一个客户端&#xff0c;也是一个服务器&#xff0c;是一个版本控制器。而gitee和GitHub都是基于git的网站或平台 4.git的基本…...

关于tresos Studio(EB)的MCAL配置之GPT

概念 GPT&#xff0c;全称General Purpose Timer&#xff0c;就是个通用定时器&#xff0c;取的名字奇怪了点。定时器是一定要的&#xff0c;要么提供给BSW去使用&#xff0c;要么提供给OS去使用。 配置 General GptDeinitApi控制接口Gpt_DeInit是否启用 GptEnableDisable…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...