[COCI2010-2011#6]STEP

news/2024/4/19 21:04:47/

目录

1.题目:

题目描述

输入格式

输出格式

2.思路

1.ans数组的维护

2.L and R 的维护

3.ne数组与pr数组的维护

4.len数组:

 3.代码:

1.有注释版:

2.copy版:

1.题目:

题目描述

给定一个长度为N的字符序列  ,初始时序列中全部都是字符L。

有 q次修改,每次给定一个 x,若为L,则将 a_x修改成R,否则将 a_x修改成L。

对于一个只含字符 L,R的字符串S,若其中不存在连续的L和R,则称 S满足要求。

每次修改后,请输出当前序列 a中最长的满足要求的连续子串的长度。

输入格式

第一行有两个整数,分别表示序列的长度 n 和修改操作的次数 q。

接下来 q 行,每行一个整数,表示本次修改的位置 x。

输出格式

对于每次修改操作,输出一行一个整数表示修改 a 中最长的满足要求的子串的长度。

 一句话解释(不知道大家了解不) :最长01交替字串

2.思路

我们循序渐进,慢慢分析:(码力重点呀!!!)

首先:单点修改,动态维护最长,很明显是线段树

那么:首先,应该有一个数组ans来记录最长的字串。

1.ans数组的维护

继续分析:

区区线段树,必有的操作是建一棵树(此处以区间和为基准)

void build(int l,int r,int k)
{if(l==r){cin>>c[k];return;}int mid=(l+r)>>1;build(l,mid,lk);build(mid+1,r,lk|1);c[k]=c[lk]+c[lk|1];
}//oh,lk与rk是define,后文有

注意一下:

最后一排

c[k]=c[lk]+c[lk|1];

是一个合并的过程

题目描述中提到:能否合并,must 左区间的右端点 != 右区间的左端点

所以拿两个数组: l表示[x,y]左端点是什么 ,r 表示[x,y]右端点是什么。

那么,就可以推如何合并了。

如果ans[root]的左区间的右端点=ans[root]的右区间的左端点,那么不满足要求,代码就是

ans[root]=max(ans[root<<1],ans[root<<1|1])
/*
注意,我这里用的是位运算(个人喜好)
root<<1 就是root*2
root<<1|1 就是root*2+1(因为<<1保证了root二进制的末尾为0,所以或1后就得root+1)
*/

如果ans[root]的右区间的左端点!=ans[root]的左区间的右端点,那么就可以合并。

蒙了吧?我也蒙了

来人!本蒟蒻的树呢?

(图片来源:Graph Editor (csacademy.com))

那么相等怎么合并呢???(更晕的来了)

就是上图中以R为右端点的最长01字串+以L为左端点的最长01字串的和,在ans_{root*2}ans_{root*2+1}的最大值作比较,取最大值。

综合就是:

#define lk k<<1
a[k]=max(a[lk],r[lk]!=l[rk]?max(a[rk],ne[lk]+pr[rk]):a[rk]);//ne数组是后缀,pr数组是前缀。

所以像消消乐一样,只有下面几个问题等我们维护:

  • R 数组的维护
  • L 数组的维护
  • ne 数组的维护
  • pr 数组的维护

所以慢慢看······

2.L and R 的维护

这个简单呀!!!

你 ans[root*2]的左端点 就一定是 ans[root]的左端点

ans[root<<1|1]的右端点 就一定是ans[root]的右段点

(啥?why??)

给张图:

可以理解了吧!

3.ne数组与pr数组的维护

 直接来吧······

如果ne[rook*2]数组没有覆盖van左区间

那很明显,根节点的ne就是左区间的ne,

同样,pr[rook*2+1]数组没有覆盖van右区间

根节点的pr就是右区间的pr。

给张图:

 如果到已经l2已经不能继续了,那么从l1开始的ne 就只能到l2

R也一样。

但如何判断是否能覆盖呢?

所以还要引入len数组。

4.len数组:

很简单,建树时直接赋值即可。

 3.代码:

1.有注释版:

#include<bits/stdc++.h>
using namespace std;#define lk k<<1
#define rk k<<1|1const int N=2e5;
int n,q,x,len[N*4+10],a[N*4+10],l[N*4+10],r[N*4+10],pr[N*4+10],ne[N*4+10];inline int read()//快读 
{int x=0,w=0;char c=0;while(!isdigit(c)) {w|=c=='-';c=getchar();}while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x;
}void change(int k) 
{a[k]=max(a[lk],r[lk]!=l[rk]?max(a[rk],ne[lk]+pr[rk]):a[rk]);//维护总长度 l[k]=l[lk];//维护L r[k]=r[rk];//维护R if(pr[lk]==len[lk]&&r[lk]!=l[rk]) pr[k]=pr[lk]+pr[rk];//维护pr else pr[k]=pr[lk];//维护prif(ne[rk]==len[rk]&&r[lk]!=l[rk]) ne[k]=ne[lk]+ne[rk];//维护neelse ne[k]=ne[rk];//维护ne
}void build(int ll,int rr,int k)//建树 
{len[k]=rr-ll+1;//维护len if(ll==rr) {a[k]=pr[k]=ne[k]=1;return;}int mid=(ll+rr)>>1;build(ll,mid,lk),build(mid+1,rr,rk);change(k);
}void modify(int x,int ll,int rr,int k)//修改 
{if(ll==rr){a[k]=pr[k]=ne[k]=1;l[k]=(l[k]==0?1:0),r[k]=(r[k]==0?1:0);//维护l ,rreturn ;}int mid=(ll+rr)>>1;if(x<=mid) modify(x,ll,mid,lk);else modify(x,mid+1,rr,rk);change(k);
}int main()
{n=read(),q=read();build(1,n,1);while(q--){x=read();modify(x,1,n,1);printf("%d\n",a[1]);}return 0;
}

2.copy版:

#include<bits/stdc++.h>
using namespace std;#define lk k<<1
#define rk k<<1|1const int N=2e5;
int n,q,x,len[N*4+10],a[N*4+10],l[N*4+10],r[N*4+10],pr[N*4+10],ne[N*4+10];inline int read()
{int x=0,w=0;char c=0;while(!isdigit(c)) {w|=c=='-';c=getchar();}while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();return w?-x:x;
}void change(int k) 
{a[k]=max(a[lk],r[lk]!=l[rk]?max(a[rk],ne[lk]+pr[rk]):a[rk]);l[k]=l[lk];r[k]=r[rk];if(pr[lk]==len[lk]&&r[lk]!=l[rk]) pr[k]=pr[lk]+pr[rk];else pr[k]=pr[lk];if(ne[rk]==len[rk]&&r[lk]!=l[rk]) ne[k]=ne[lk]+ne[rk];else ne[k]=ne[rk];
}void build(int ll,int rr,int k)
{len[k]=rr-ll+1;if(ll==rr) {a[k]=pr[k]=ne[k]=1;return;}int mid=(ll+rr)>>1;build(ll,mid,lk),build(mid+1,rr,rk);change(k);
}void modify(int x,int ll,int rr,int k)
{if(ll==rr){a[k]=pr[k]=ne[k]=1;l[k]=(l[k]==0?1:0),r[k]=(r[k]==0?1:0);return ;}int mid=(ll+rr)>>1;if(x<=mid) modify(x,ll,mid,lk);else modify(x,mid+1,rr,rk);change(k);
}int main()
{n=read(),q=read();build(1,n,1);while(q--){x=read();modify(x,1,n,1);printf("%d\n",a[1]);}return 0;
}

(L('ω')┘点赞,关注,下篇博客再见 └('ω')」)


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

相关文章

SringCloud集成Redis工具类

1、pom文件 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency>2、redis工具类 Service(value "redisService") Slf4j public class RedisServi…

ECG分类(一)

前言 看了的博主https://me.csdn.net/weixin_42559479文章跟着动手做的复现&#xff0c;论文题目是An Improved Convolutional Neural Network Based Approach for Automated Heartbeat Classification。&#xff08;我是小白&#xff0c;大佬请绕行&#xff01;&#xff09; …

BCV和BEV是个什么鬼?

前段时间在阅读SeaBIOS&#xff08;即QEMUKVM解决方案中用到的BIOS程序&#xff09;的代码遇到了BCV和BEV这两个缩写词&#xff0c;找了半天才搞明白是什么意思。在这里跟大家分享一下。 BCV: Boot Connection Vector&#xff0c;这是一个指针&#xff0c;该指针指向PCI设备的O…

三极管:NPN和PNP

一&#xff0c;三极管的类型&#xff1a; NPN 和 PNP二&#xff0c;NPN和PNP图示&#xff1a; 三&#xff0c;NPN 1&#xff0c;特征&#xff1a;9013型号、SOT-23封装、小功率、用途&#xff08;开关&#xff09; 2&#xff0c;电路&#xff1a;E终将直接或间接地连接到GND…

Van Emde Boas Trees

## 介绍 ##van Emde Boas trees 支持所有优先级优先级队列的操作&#xff0c;并且巧妙的是它对于SEARCH, INSERT,DELETE,MINIMUM,MAXMUN,SUCCESSOR,和PREDECESSOR这些操作的支持都在最坏复 杂度O(lglgn)之内。不过有些限制的是&#xff0c;所有的Kye值都必须在 0…n−1之间&…

算法导论-van Emde Boas树

van Emde Boas树 van Emde Boas树中文名不知道&#xff0c;所以暂且叫它v树吧。v树是一种数据结构&#xff0c;和二叉树、红黑树类似。一种数据结构被创建出来&#xff0c;肯定有其特别的优点&#xff0c;v树的优点就是实现数据的基本操作的最差的时间复杂度为O(lglgn),在算法导…

基于PMOS的过压保护(OVP)电路仿真

电路来源于工科男孙老师&#xff0c;B站视频链接&#xff1a;点击跳转 本次利用protues对其进行仿真验证&#xff0c;下图是电路模型 1.正常电压输入5V 电路输入5V时&#xff0c;电路正常导通&#xff0c;输入电压等于输出电压。此时输入电压小于稳压管稳压值&#xff0c;稳压…

【算法学习笔记】van Emde Boas树

参考算法导论第20章 van Emde Boas树 文章目录 1. 基本方法1.1 直接寻址1.2 叠加的二叉树结构 Superimposing a binary tree structure1.3 叠加的一棵高度恒定的树 2. 递归结构2.1 原型 *van Emde Boas* 结构2.2 原型 *van Emde Boas* 结构上的操作判断一个值是否在集合中查找…

YAML详解,如何快速生成一个yaml文件并修改,快速部署k8s项目

什么是yaml文件 YAML介绍YAML基本语法yaml文件组成部分常用的字段含义&#xff08;结合k8s)YAML编写方式第一种第二种 yaml文件是资源清单文件&#xff0c;资源编排 YAML介绍 yaml文件是资源清单文件&#xff0c;资源编排。 YAML&#xff1a;是一种标记语言。为了强调这种语言…

算法导论Van Emde Boas树

#include<iostream> #include<math.h> #define NIL 9999 #define MAX 100 using namespace std;struct Van_Emde_Boas {//veb树节点 int u;int min; int max;Van_Emde_Boas *summaryNULL;Van_Emde_Boas *cluster[MAX];};//创建vbn树 void vEB_TREE_CREATE(Van_Emd…

JavaScript原生自动触发事件

在有些情况下&#xff0c;我们需要程序逻辑自动触发元素的事件&#xff0c;例如js提供了click()&#xff0c; form提供了reset(),submit()等方法&#xff01;在jquery中提供了trigger()方法帮助我们自动触发事件&#xff0c;原理是什么呢&#xff1f;接下来让我们一探究竟&…

NPN与PNP的区别

NPN 是用 B→E 的电流&#xff08;IB&#xff09;控制 C→E 的电流&#xff08;IC&#xff09;&#xff0c;E极电位最低&#xff0c;且正常放大时通常C极电位最高&#xff0c;即 VC > VB > VE PNP 是用 E→B 的电流&#xff08;IB&#xff09;控制 E→C 的电流&#xff…

PTE靶机攻略之Windows

26题 这是一道关于Windows权限提升的考题&#xff0c;目标机的IP地址:172.16.12.101&#xff0c;目标的端口范围在27000-28000之间&#xff0c;请利用扫描工具找到开放的端口&#xff0c;开始你的渗透之旅&#xff0c;进入网站后台&#xff0c;请填入key1的值&#xff1a; 解…

van Emde Boas 树 数据结构说解

van Emde Boas 树的定义 直观上看&#xff0c;vEB 树保存了一个有序的集合&#xff0c;并支持以 O(lglgn) 的时间复杂度在 vEB 树上进行最小最大值查询、单值存在性查询、单值前驱后继查询、单值插入维护、单值删除维护的数据结构。为了保证时间复杂度&#xff0c;vEB 树上所有…

运放内部电路分析

1、首先看一个一个运放的内部的简图&#xff0c;下图为741运放的简化图&#xff0c;分为输入级&#xff0c;达林顿放大级&#xff0c;输出级。 输入级&#xff1a; 重要的关系式&#xff1a;ic1ic3ic4&#xff0c;得出&#xff1a;ioic4-ic2 即 ioic1-ic2&#xff0c;又有ic1ic…

内网后渗透,生成免杀后门!!

大家好&#xff0c;初来CSDN请大家多多关注。今天给大家带来的是后内网渗透---免杀木马生成&#xff01;&#xff01; 经过本人的一段时间研究终于研究出了一个过火绒等免杀后门&#xff0c;过程有点复杂&#xff0c;待我细细道来。 一、在自己公网服务器上面装上自己的工具 …

ECG分析:基于深度学习的ECG心律失常分类入门(5)

ECG分析:基于深度学习的ECG心律失常分类入门(5) 数据和模型完成了之后&#xff0c;就是训练和测试了&#xff0c;这里顺带提一下&#xff0c;MITAB的数据是48条记录的&#xff0c;而我们在做ECG分析的时候&#xff0c;都是去掉了四条记录&#xff08;102&#xff0c;104&#…

【模拟IC】带隙基准的非理想因素以及解决办法

一、前言 实际设计带隙基准电路中&#xff0c;存在非理想的因素&#xff0c;导致它不能精准输出电压。本文简要介绍带隙基准客观存在的非理想因素&#xff0c;并介绍减小非理想因素的解决方法。 二、Io和Ic的温度特性 实际的双极型器件中的 Io 是一个与温度有关的工艺参数。 …

VBI简介

VBI是Vertical Blanking Interval的缩写&#xff0c;中文意思是场消隐期&#xff0c;也叫场逆程&#xff0c;而电视节目称为正程信号。 在电视处理中&#xff0c;图像数据垂直扫描完成后&#xff0c;从屏幕底部回到屏幕顶部的时间是没有收到任何的video信息&#xff0c;可以利…