Educational Codeforces Round 170 (Rated for Div. 2) D 题解
to sum of:前三题都是究极水题,补补D题吧,dp太钛肽弱了..
Problem - D - Codeforces--Attribute Checks
思路:首先得坚定地确定m^2,然后剩下的复杂度思考怎么优化..
key:每一个0只考虑影响到下一个0之间的数字!! 定义dp[i][j]为,在有i个能力点时.点了j个智力,那么点了i-j个力量. 在每一个0到下一个0之间的数字,可以用桶+差分来维护,这样可以o(1)查询在j智力情况下可以增加多少答案
看起来是n的循环里面嵌套了m的循环,但是m不是每次都执行的,只会执行m次,并且最坏的一次是m^2的。所以复杂度是加起来的,不是乘起来的,一下不留意可能算错时间复杂度..
int n,m;
int arr[2000006];
int bucket1[5005]; //用差分来优化o(1),区间修改的操作,如果用树状数组的话就是o(logn)的
int bucket2[5005]; key:每次只考虑两个0之间的检查!!这样不会算重算漏!!
int dp[5005][5005]; //定义dp[i][j]为,在有i个能力点时.点了j个智力,那么点了i-j个力量.
...坚定地确定m^2,然后剩下的复杂度思考怎么优化..
key:每一个0只考虑影响到下一个0之间的数字!!
可以优化成滚动数组,懒得搞了.
void solve(){ //D o(m^2+n) or o(m^2logn+n)cin>>n>>m;for(int i=1;i<=n;i++) cin>>arr[i];int cntp=0,ans=0;int bk1=0,bk2=0;for(int i=1;i<=n+1;i++){ //到n+1是要处理最近一个0.即在末尾添加一个虚0.if(arr[i]==0){ //只会执行m次if(cntp==0){ cntp++; continue; } //否则cntp-1会越界!!for(int j=1;j<=cntp;j++) bucket1[j]+=bucket1[j-1],bucket2[j]+=bucket2[j-1];for(int j=0;j<=cntp;j++){ //o(m^2)bk1=bucket1[j],bucket1[j]=0; //两个0之间,bk2=bucket2[cntp-j],bucket2[cntp-j]=0;dp[cntp][j]=dp[cntp-1][max(0ll,j-1)]+bk1+bk2; //本次点智力if(j<=cntp-1) dp[cntp][j]=max(dp[cntp][j],dp[cntp-1][j]+bk1+bk2); //本次点力量}cntp++;}if(arr[i]>0&&arr[i]<=cntp) bucket1[arr[i]]++;if(arr[i]<0&&-arr[i]<=cntp) bucket2[-arr[i]]++;}for(int j=0;j<=cntp-1;j++) ans=max(ans,dp[cntp-1][j]); //最后一个0是虚的.cout<<ans;
}
相关文章:
Educational Codeforces Round 170 (Rated for Div. 2) D 题解
to sum of:前三题都是究极水题,补补D题吧,dp太钛肽弱了.. Problem - D - Codeforces--Attribute Checks 思路:首先得坚定地确定m^2,然后剩下的复杂度思考怎么优化.. key:每一个0只考虑影响到下一个0之间的数字!! 定义dp[i][j]为,在有i个能力点时.点了…...
NeRS: Neural Reflectance Surfaces for Sparse-view 3D Reconstruction in the Wild
阅读记录: 1. 2.优点1:我们的方法仅依赖于近似的相机位姿估计和粗略的类别级形状模板。 3.我们的关键见解是,我们可以强制执行基于表面的 3D 表示,而不是允许广泛用于体积表示的无约束密度。重要的是,这允许依赖于视…...
【Linux】su 命令的运行原理以及su切换用户默认继承环境配置
一、su 命令的运行原理 原理解释: su(switch user)命令用于在Linux和Unix系统中切换用户身份。 当你执行 su 命令时,系统会创建一个新的进程,通常是一个新的 shell 实例。这个新进程会以目标用户的身份运行&#…...
libtorch环境配置
环境配置 建议在linux上配置对应环境 可以在autoDL上租一个服务器来搭建,带有pytorch的环境 https://www.autodl.com/home 我自己的win电脑上安装了pytorch,但是配置时会报错,于是到ubuntu上配置 电脑上装有pytorch的就不需要再下载libtorc…...
【C语言】define宏定义与const修饰限定
两者都是将字符替换为相应的数值。 区别在于: #define宏定义纸进行字符串替换,无类型检查 const修饰符限定变量为只读变量 #include <stdio.h> #define PI 3.14159 //符号常量 /* 功能:宏定义与const修饰符限定 时间:20…...
基于深度学习的基于视觉的机器人导航
基于深度学习的视觉机器人导航是一种通过深度学习算法结合视觉感知系统(如摄像头、LiDAR等)实现机器人在复杂环境中的自主导航的技术。这种方法使机器人能够像人类一样使用视觉信息感知环境、规划路径,并避开障碍物。与传统的导航方法相比&am…...
苍穹外卖学习笔记(二十三)
拒单 OrderController /*** 拒单*/PutMapping("/rejection")ApiOperation("拒单")public Result rejection(RequestBody OrdersRejectionDTO ordersRejectionDTO) throws Exception {orderService.rejection(ordersRejectionDTO);return Result.success(…...
vLLM 推理引擎性能分析基准测试
文章目录 分析步骤案例案例描述测试数据集 原始数据〇轮测试(enable-64)一轮测试(enable-128)二轮测试(enable-256)三轮测试(enable-512)四轮测试(enable-2048࿰…...
图像增强论文精读笔记-Kindling the Darkness: A Practical Low-light Image Enhancer(KinD)
1. 论文基本信息 论文标题:Kindling the Darkness: A Practical Low-light Image Enhancer 作者:Yonghua Zhang等 发表时间和期刊:2019;ACM MM 论文链接:https://arxiv.org/abs/1905.04161 2. 研究背景和动机 现有…...
HALCON数据结构之字符串
1.1 String字符串的基本操作 *将数字转换为字符串或修改字符串 *tuple_string (T, Format, String) //HALCON语句 *String: T $ Format //赋值操作*Format string 由以下四个部分组成: *<flags><field width>.<precision><conversion 字符&g…...
string模拟优化和vector使用
1.简单介绍编码 utf_8变长编码,常用英文字母使用1个字节,对于其它语言可能2到14,大部分编码是utf_8,char_16是编码为utf_16, char_32是编码为utf_32, wchar_t是宽字符的, utf_16是大小为俩个字节&a…...
Go-知识依赖GOPATH
Go-知识依赖GOPATH 1. 介绍2. GOROOT 是什么3. GOPATH 是什么4. 依赖查找5. GOPATH 的缺点1. 介绍 早期Go语言单纯地使用GOPATH管理依赖,但是GOPATH不方便管理依赖的多个版本,后来增加了vendor,允许把项目依赖 连同项目源码一同管理。Go 1.11 引入了全新的依赖管理工具 Go …...
PyTorch 中 reshape 函数用法示例
PyTorch 中 reshape 函数用法示例 在 PyTorch 中,reshape 函数用于改变张量的形状,而不改变其中的数据。下面是一些关于 reshape 函数的常见用法示例。 基本语法 torch.reshape(input, shape) # input: 要重塑的张量。 # shape: 目标形状࿰…...
安全光幕的工作原理及应用场景
安全光幕是一种利用光电传感技术来检测和响应危险情况的先进设备。其工作原理基于红外线传感器,通过发射红外光束并接收反射或透射光束来形成一道无形的屏障。以下是对安全光幕工作原理和应用场景的介绍: 工作原理 发射器与接收器:安全光幕通…...
《深度学习》OpenCV LBPH算法人脸识别 原理及案例解析
目录 一、LBPH算法 1、概念 2、实现步骤 3、方法 1)步骤1 • 缩放 • 旋转和平移 2)步骤2 二、案例实现 1、完整代码 1)图像内容: 2)运行结果: 一、LBPH算法 1、概念 在OpenCV中,L…...
数据结构之顺序表——动态顺序表(C语言版)
静态顺序表我们已经实现完毕了,下来我们实现一下动态顺序表 静态链接:数据结构之顺序表——动态顺序表(C语言版) 首先来了解一下两个顺序表的差别 一、内存管理的灵活性 动态分配与释放:动态顺序表能够在运行时根据需要动态地分配和释放内存…...
Python 网络爬虫入门与实战
目录 1 引言 2 网络爬虫基础知识 2.1 什么是网络爬虫 2.2 爬虫的工作原理 2.3 爬虫的应用场景 3 Python 爬虫环境搭建 3.1 安装 Python 3.2 安装必要的库 4 使用 Requests 库进行基本爬虫 4.1 发送 GET 请求 4.2 发送 POST 请求 4.3 处理响应 5 使用 BeautifulSoup…...
成都睿明智科技有限公司电商服务可靠不?
在这个短视频风起云涌的时代,抖音不仅成为了人们娱乐消遣的首选平台,更是众多商家竞相追逐的电商新蓝海。成都睿明智科技有限公司,作为抖音电商服务领域的佼佼者,正以其独到的洞察力和专业的服务,助力无数品牌在这片沃…...
fmql之Linux Uart
正点原子第48章。 串口收发测试 正点原子教程 RS232和RS485的串口收发测试是一样的。 // 设置串口波特率为115200 stty -F /dev/ttyPS1 ispeed 115200 ospeed 115200 cs8// 发送字符串 echo "www.openedv.com" >/dev/ttyPS1// 接收数据 cat /dev/ttyPS1 fmql测…...
【火山引擎】调用火山大模型的方法 | SDK安装 | 配置 | 客户端初始化 | 设置
豆包 (Doubao) 是字节跳动研发的大规模预训练语言模型。 目录 1 安装 2 配置访问凭证 3 客户端初始化 4 设置地域和访问域名 5 设置超时/重试次数 1 安装 通过pip安装PYTHON SDK。 pip install volcengine-python-sdk[ark] 2 配置访问凭证 获取 API Key 访问凭证具体步…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
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 …...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...
