当前位置: 首页 > 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 访问凭证具体步…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...