(构造)(两个相邻特殊点之间的不定长度段维护) Dango

news/2024/2/21 10:53:03

C - Dango (atcoder.jp)

#include <iostream>
#include <string>
using namespace std;int main() {int N;cin >> N;string S;cin >> S;S = S + '-';
//    末尾+‘-’int ans = -1;int j = -1;for (int i = 0; i <= N; i++) {if (S[i] == '-') {
//        	结尾int l = i - j - 1;
//            求不包含两个端点的段长度.
//            如果没有前导-,那长度应该是0到i-1这一段.
//            前导-等价于是在-1位置所以不用分类讨论求解.
//            两个-之间的距离if (l > 0 && (j >= 0 || i < N)) {ans = max(ans, l);
//                N位置的-是手动加上来判断辅助前导-判断的,所以要判一下其中一个-有意义.
//					如果整个串只有一个-存在,l = 0,此时是不应该更新ans的,所以要判断一下
//                找到过l且j和i其中一个-是有意义的。}j = i;
//            记录遇到的前一个-//通过末尾加-,变成需要特判结尾-的求两个--之间的长度问题.
//同类题,外卖店优先级.
//记录两份订单之间的状态}}cout << ans << endl;return 0;
}
//Exactly one of the first character and the last character is -, and the other 
//L characters are o.
//忽略了题意-oo也是有意义的.
//看到要求后就应该在脑海里想符合条件的形式再开始做判断.

套路:

1)求两点之间不包括自身的段长度

r - l - 1

2)维护两个相邻特殊点之间的不定长度段信息

前提:

题目给的一段字符串,或者给出几个可以放在时间轴上的点,要维护点之间的信息。
或者是求以一个特殊点为开头,或一个特殊点为结尾的段的信息。

情景:

原文:
1)- Dango
For a positive integer L, a level-L dango string is a string that satisfies the following conditions.
- It is a string of length L+1 consisting of o and -.
- Exactly one of the first character and the last character is -, and the other L characters are o.
- You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.
简述
一个dango字符串需要满足头和尾字符是有一个是-,一个是o,寻找包含最多o的dango字符串


2)外卖店优先级给定 T 时刻以内的 M 条订单信息,请你计算 T 时刻时有多少外卖店在优先缓存中。

应对:如何找到这个段?

可能要的前置构造
以一个特殊点为开头,或一个特殊点为结尾的段的信息同时需要维护时,可以通过构造来在字符串,时间轴上加上一个边界,来维护以一个特殊点为开头的情况,然后操作时要加一个判断来处理这个边界的情况


特殊点
构造后,变为求两端是-的子串的最大o长度,
要求o的长度,所以-就是特殊点,用一个变量记录上一次遇到的-,循环时遇到了-就
可以与上一次遇到的-之间形成一个段,根据题意进行不同的操作维护信息。

核心代码:

if (S[i] == '-') {int len = i - l - 1;...l = i;
}

如果还有更多信息
至于外卖店优先级,由于题目里一个段内还要维护多个id的信息,所以要用一个数组来储存两个特殊点信息。

#两个相邻特殊点之间的不定长度段
#构造


http://www.ppmy.cn/news/57704.html

相关文章

从苏宁电器到卡巴斯基(第二部)第31篇:我当高校教师的这几年 VII

目录 必须要开始做前端开发了 我感觉,三本学生并不比985硕士研究生差 必须要开始做前端开发了 我一开始与X高校签约,签的是《任务工作岗位劳动合同》,合同期限是一年,具体内容是“学院网络安全维护及信息化开发”工作。但由于学校人手不足,因此我也是需要承担授课以及带…

CSS布局基础(定位)

定位 定位定位方式定位偏移其他知识点z-index父相子绝固定定位贴着版心绝对定位到父盒子中央绝对定位和固定定位浮动效果原生浮动和定位产生的浮动的区别 定位 如字面意思&#xff0c;定位的作用就是将元素&#xff0c;移动到指定的地方. 浮动一般用于横向排列块级元素&#x…

功能齐全的 DIY ESP32 智能手表设计之PCB介绍

相关设计资料下载ESP32 智能手表带心率、指南针设计资料(包含Arduino源码+原理图+Gerber+3D文件).zip 目录 ESP32智能手表PCB 3D 视图效果 主板不同组件的标记

Graph Theory(图论)

一、图的定义 图是通过一组边相互连接的顶点的集合。 In this graph, V { A , B , C , D , E } E { AB , AC , BD , CD , DE } 二、图的类型 2.1 Finite Graph A graph consisting of finite number of vertices and edges is called as a finite graph. Null Graph Tri…

云服务器部署python项目

前言&#xff1a;相信看到这篇文章的小伙伴都或多或少有一些编程基础&#xff0c;懂得一些linux的基本命令了吧&#xff0c;本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python&#xff1a;一种编程语言&…

现代CMake高级教程 - 第 6 章:输出与变量

双笙子佯谬老师的【公开课】现代CMake高级教程课程笔记 第 6 章&#xff1a;输出与变量 在运行 cmake -B build 时&#xff0c;打印字符串&#xff08;用于调试&#xff09; message("Hello world!")❯ cmake --build buildHello world! -- Configuring done -- G…

基于jQuery------购物车案例

目录 基于jQuery------购物车案例 案例&#xff1a;购物车案例模块-增减商品数量分析 案例&#xff1a;购物车案例模块-修改商品小计分析 案例&#xff1a;购物车案例模块-计算总计和总额 案例&#xff1a;购物车案例模块-删除商品模块 案例&#xff1a;购物车案例模块-选…

移动宽带安装说明一(刘欣)

2023年&#xff0c;五一假期给老家和父母家安装了2次宽带&#xff0c;记录一下吧。 一、移动光改覆盖率已经很高了 从当初的铁通“FTTB”覆盖小区,网线入户的带宽只能达到100M&#xff0c;提升到现在大面积的光改完成&#xff0c;普遍是光猫&#xff08;光纤MODEL&#xff09…

什么是API接口?

API是指应用程序接口&#xff0c;是一种连接不同软件应用程序的桥梁&#xff0c;以实现相互通信和数据交换的手段。随着互联网技术的发展&#xff0c;API接口越来越广泛地应用于各种企业业务中。本文将从API接口的基本概念、作用、优缺点等多个角度进行探讨。 一、基本概念 A…

easyexcel读取excel合并单元格数据

普通的excel列表&#xff0c;easyexcel读取是没有什么问题的。但是&#xff0c;如果有合并单元格&#xff0c;那么它读取的时候&#xff0c;能获取数据&#xff0c;但是数据是不完整的。如下所示的单元格数据&#xff1a; 我们通过简单的异步读取&#xff0c;最后查看数据内容&…

无惧黑暗强光,纯视觉导航也能全天候作业

对于一台激光导航扫地机器人而言&#xff0c;全天候作业并非难事&#xff0c;那么纯视觉导航扫地机器人能做到吗&#xff1f; 无论对于人&#xff0c;还是机器人&#xff0c;光线环境的变化对“眼睛”的影响都是致命的。由于视觉传感器对于光线十分敏感&#xff0c;在家庭场景…

高度可定制可用于商用目的全流程供应链系统(全部源码)

一、开源项目简介 高度可定制零售供应链中台基础系统&#xff0c;集成零售管理, 电子商务, 供应链管理, 财务管理, 车队管理, 仓库管理, 人员管理, 产品管理, 订单管理, 会员管理, 连锁店管理, 加盟管理, 前端React/Ant Design, 后端Java Spring自有开源框架&#xff0c;全面支…

【五一创作】值得一看的JVM垃圾收集器

垃圾收集器 一、常见的垃圾收集器&#xff1f; 常见的垃圾收集器如下&#xff1a; 新生代收集器&#xff1a;Serial、 ParNew、Parallel Scavenge老年代收集器&#xff1a;Serial Old、Parallel Old、CMS老年代和新生代收集器&#xff1a;Garbage First &#xff08;G1) 二…

【前端面经】JS-对象的可枚举性

JavaScript中的对象是非常重要的数据类型&#xff0c;它们作为编程中的基础构建块&#xff0c;可以被用来表示各种数据结构。对象是由属性构成的&#xff0c;每个属性都包含一个名字和一个值。属性值可以是基本类型或其他对象。在JavaScript中&#xff0c;对象属性有许多特性&a…

Nacos 服务网格⽣态

博主介绍&#xff1a;✌全网粉丝4W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战、定制、远程&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面…

【拓扑排序】课程表系列

文章目录 课程表&#xff08;环检测算法&#xff09;1. DFS2. BFS 课程表 II&#xff08;拓扑序列&#xff09;1. DFS2. BFS 课程表 IV&#xff08;记忆化搜索&#xff09;1. DFS2. BFS 课程表&#xff08;环检测算法&#xff09; 1. DFS 先修课程之间的关系可以用有向图表示&…

TIM-输出比较(PWM)——STM32

TIM-输出比较——STM32 Oc (Output Compare) 输出比较 输出比较可以通过比较CNT与CCR寄存器值的关系&#xff0c;来对输出电平进行置1、置0或翻转的操作&#xff0c;用于输出一定频率和占空比的PWM波形 每个高级定时器和通用定时器都拥有4个输出比较通道高级定时器的前3个通道…

Vue电商项目--防抖节流应用

演示卡顿现象 正常&#xff1a;事件触发非常频繁&#xff0c;而且每一次的触发&#xff0c;回调函数都要去执行&#xff08;如果时间很短&#xff0c;而回调函数内部有计算&#xff0c;那么很容易出现浏览器卡顿&#xff09; 正常情况下&#xff08;用户慢慢的操作&#xff0…

【Python】【进阶篇】22、Django模板加载与响应

目录 22、Django模板加载与响应1. 什么是模板1) 模板的配置2) 修改settings配置文件 2. 模板的加载与响应方式3. render方法详解 22、Django模板加载与响应 在前文章节《Django模板系统》中&#xff0c;我们对 Django 的模板系统有了初步的认识&#xff0c;在本章我们将重点讲…

死信队列

死信队列 死信的概念 先从概念解释上搞清楚这个定义&#xff0c;死信&#xff0c;顾名思义就是无法被消费的消息&#xff0c;字面意思可以这样理解&#xff0c;一般来说&#xff0c;producer 将消息投递到 broker 或者直接到queue 里了&#xff0c;consumer 从 queue 取出消息…
最新文章