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

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:前三题都是究极水题&#xff0c;补补D题吧&#xff0c;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

阅读记录&#xff1a; 1. 2.优点1&#xff1a;我们的方法仅依赖于近似的相机位姿估计和粗略的类别级形状模板。 3.我们的关键见解是&#xff0c;我们可以强制执行基于表面的 3D 表示&#xff0c;而不是允许广泛用于体积表示的无约束密度。重要的是&#xff0c;这允许依赖于视…...

【Linux】su 命令的运行原理以及su切换用户默认继承环境配置

一、su 命令的运行原理 原理解释&#xff1a; su&#xff08;switch user&#xff09;命令用于在Linux和Unix系统中切换用户身份。 当你执行 su 命令时&#xff0c;系统会创建一个新的进程&#xff0c;通常是一个新的 shell 实例。这个新进程会以目标用户的身份运行&#…...

libtorch环境配置

环境配置 建议在linux上配置对应环境 可以在autoDL上租一个服务器来搭建&#xff0c;带有pytorch的环境 https://www.autodl.com/home 我自己的win电脑上安装了pytorch&#xff0c;但是配置时会报错&#xff0c;于是到ubuntu上配置 电脑上装有pytorch的就不需要再下载libtorc…...

【C语言】define宏定义与const修饰限定

两者都是将字符替换为相应的数值。 区别在于&#xff1a; #define宏定义纸进行字符串替换&#xff0c;无类型检查 const修饰符限定变量为只读变量 #include <stdio.h> #define PI 3.14159 //符号常量 /* 功能&#xff1a;宏定义与const修饰符限定 时间&#xff1a;20…...

基于深度学习的基于视觉的机器人导航

基于深度学习的视觉机器人导航是一种通过深度学习算法结合视觉感知系统&#xff08;如摄像头、LiDAR等&#xff09;实现机器人在复杂环境中的自主导航的技术。这种方法使机器人能够像人类一样使用视觉信息感知环境、规划路径&#xff0c;并避开障碍物。与传统的导航方法相比&am…...

苍穹外卖学习笔记(二十三)

拒单 OrderController /*** 拒单*/PutMapping("/rejection")ApiOperation("拒单")public Result rejection(RequestBody OrdersRejectionDTO ordersRejectionDTO) throws Exception {orderService.rejection(ordersRejectionDTO);return Result.success(…...

vLLM 推理引擎性能分析基准测试

文章目录 分析步骤案例案例描述测试数据集 原始数据〇轮测试&#xff08;enable-64&#xff09;一轮测试&#xff08;enable-128&#xff09;二轮测试&#xff08;enable-256&#xff09;三轮测试&#xff08;enable-512&#xff09;四轮测试&#xff08;enable-2048&#xff0…...

图像增强论文精读笔记-Kindling the Darkness: A Practical Low-light Image Enhancer(KinD)

1. 论文基本信息 论文标题&#xff1a;Kindling the Darkness: A Practical Low-light Image Enhancer 作者&#xff1a;Yonghua Zhang等 发表时间和期刊&#xff1a;2019&#xff1b;ACM MM 论文链接&#xff1a;https://arxiv.org/abs/1905.04161 2. 研究背景和动机 现有…...

HALCON数据结构之字符串

1.1 String字符串的基本操作 *将数字转换为字符串或修改字符串 *tuple_string (T, Format, String) //HALCON语句 *String: T $ Format //赋值操作*Format string 由以下四个部分组成&#xff1a; *<flags><field width>.<precision><conversion 字符&g…...

string模拟优化和vector使用

1.简单介绍编码 utf_8变长编码&#xff0c;常用英文字母使用1个字节&#xff0c;对于其它语言可能2到14&#xff0c;大部分编码是utf_8&#xff0c;char_16是编码为utf_16, char_32是编码为utf_32&#xff0c; wchar_t是宽字符的&#xff0c; 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 中&#xff0c;reshape 函数用于改变张量的形状&#xff0c;而不改变其中的数据。下面是一些关于 reshape 函数的常见用法示例。 基本语法 torch.reshape(input, shape) # input: 要重塑的张量。 # shape: 目标形状&#xff0…...

安全光幕的工作原理及应用场景

安全光幕是一种利用光电传感技术来检测和响应危险情况的先进设备。其工作原理基于红外线传感器&#xff0c;通过发射红外光束并接收反射或透射光束来形成一道无形的屏障。以下是对安全光幕工作原理和应用场景的介绍&#xff1a; 工作原理 发射器与接收器&#xff1a;安全光幕通…...

《深度学习》OpenCV LBPH算法人脸识别 原理及案例解析

目录 一、LBPH算法 1、概念 2、实现步骤 3、方法 1&#xff09;步骤1 • 缩放 • 旋转和平移 2&#xff09;步骤2 二、案例实现 1、完整代码 1&#xff09;图像内容&#xff1a; 2&#xff09;运行结果&#xff1a; 一、LBPH算法 1、概念 在OpenCV中&#xff0c;L…...

数据结构之顺序表——动态顺序表(C语言版)

静态顺序表我们已经实现完毕了&#xff0c;下来我们实现一下动态顺序表 静态链接&#xff1a;数据结构之顺序表——动态顺序表(C语言版) 首先来了解一下两个顺序表的差别 一、内存管理的灵活性 动态分配与释放&#xff1a;动态顺序表能够在运行时根据需要动态地分配和释放内存…...

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…...

成都睿明智科技有限公司电商服务可靠不?

在这个短视频风起云涌的时代&#xff0c;抖音不仅成为了人们娱乐消遣的首选平台&#xff0c;更是众多商家竞相追逐的电商新蓝海。成都睿明智科技有限公司&#xff0c;作为抖音电商服务领域的佼佼者&#xff0c;正以其独到的洞察力和专业的服务&#xff0c;助力无数品牌在这片沃…...

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 访问凭证具体步…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...