【董晓算法】竞赛常用知识点之数据结构1

2024-05-16 12:36

本文主要是介绍【董晓算法】竞赛常用知识点之数据结构1,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 前言:

本系列是学习了董晓老师所讲的知识点做的笔记

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)

 动态规划系列(还没学完)

【董晓算法】动态规划之线性DP问题-CSDN博客

【董晓算法】动态规划之背包DP问题(2024.5.11)-CSDN博客

【董晓算法】动态规划之背包DP与树形DP-CSDN博客

字符串系列

【董晓算法】竞赛常用知识之字符串1-CSDN博客

【董晓算法】竞赛常用知识之字符串2-CSDN博客

并查集

P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

fa初始化

每个节点指向它自己

fa[x]存节点x的父节点

  for(int i=1;i<=n;i++) fa[i]=i;

查找:

路径压缩,使树扁平化。 

int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}

合并

把一个集合的根指向另一个集合的根

void unionset(int x,int y){fa[find(x)]=find(y);
}

判断是否在同一集合内

x=find(x),y=find(y);
if(x==y) puts("true")
else puts("false");

按秩合并

把小集合的根指向大集合的根。

void unionset(int x,int y){x=find(x),y=find(y);if(x==y)return;if(siz[x]>siz[y])swap(x,y);fa[x]=y;siz[y]+=siz[x];
}

线段树+懒标记

线段树是基于分治思想的二叉树,用来维护区间信息(区间和,区间最值,区间GCD等),可以在logn的时间内执行区间修改和区间查询。线段树中每个叶子节点存储元素本身非叶子节点存储区间内元素的统计值

递归建树

#define lc p<<1
#define rc p<<1|1
#define N 500005
int n, w[N];
struct Tree{ int l,r,sum
}tr[N*4];
void build(int p,int l,int r){ //建树tr[p={l,r,w[l]};if(l==r) return;int m=l+r>>1;build(lc,l,m);build(rc,m+1,r);tr[p].sum=tr[lc].sum+tr[rc].sum;}

点修改

从根节点进入。递归找到叶子节点[x,x],把该节点的值增加k。然后从下往上更新其祖先节点上的统计值。

void update(int p,int k,intR){if(tr[p].1==x&&tr[p].r==x){tr[p].sum+=k;return;}int m=tr[p].1+tr[p].r>>1;//非叶子则裂开 if(x<=m)update(lc,x,k);if(x>m)update(rc,x,k);tr[p].sum=tr[lc].sum+tr[rc].sum;
}

区间查询

拆分与拼凑的思想。

例如,查询区间[4,9]可以拆分成 [4.5],[6.8〕 和 [9,9],通过合并这三个区间的答案求得查询答案。

int query(int p,int l,int r){ if(l<=tr[p].l && tr[p].r<=r) return tr[p].sum;int m=tr[p].l+tr[p].r>>1;pushdown(p);int sum=0;if(l<=m) sum+=query(lc,l,r);if(r>m) sum+=query(rc,l,r);return sum;
}

区间修改

做懒惰修改,当 [x,y] 完全覆盖节点区间 [a.b]时先修改该区间的 sum 值再打上一个"懒标记"然后立即返回。等下次需要时再下传“懒标记",可以把每次修改和查询的时间都控制到O(logn)

void pushup(int u){ //向上更新tr[u].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int p){ //向下更新if(tr[p].add){tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1),tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1),tr[lc].add+=tr[p].add,tr[rc].add+=tr[p].add,tr[p].add=0;      }
}
void update(int p,int k,intR){if(tr[p].1==x&&tr[p].r==x){//覆盖则修改tr[p].sum+=(tr[p].r-tr[p].l+1)*k;tr[p].add+=k;return;}int m=tr[p].1+tr[p].r>>1;//不覆盖则裂开 pushdown(p);if(x<=m)update(lc,x,k);if(x>m)update(rc,x,k);tr[p].sum=tr[lc].sum+tr[rc].sum;pushup(p);
}

 P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这篇关于【董晓算法】竞赛常用知识点之数据结构1的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/994923

相关文章

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

golang中reflect包的常用方法

《golang中reflect包的常用方法》Go反射reflect包提供类型和值方法,用于获取类型信息、访问字段、调用方法等,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值... 目录reflect包方法总结类型 (Type) 方法值 (Value) 方法reflect包方法总结

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

python常用的正则表达式及作用

《python常用的正则表达式及作用》正则表达式是处理字符串的强大工具,Python通过re模块提供正则表达式支持,本文给大家介绍python常用的正则表达式及作用详解,感兴趣的朋友跟随小编一起看看吧... 目录python常用正则表达式及作用基本匹配模式常用正则表达式示例常用量词边界匹配分组和捕获常用re

gitlab安装及邮箱配置和常用使用方式

《gitlab安装及邮箱配置和常用使用方式》:本文主要介绍gitlab安装及邮箱配置和常用使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1.安装GitLab2.配置GitLab邮件服务3.GitLab的账号注册邮箱验证及其分组4.gitlab分支和标签的

Python常用命令提示符使用方法详解

《Python常用命令提示符使用方法详解》在学习python的过程中,我们需要用到命令提示符(CMD)进行环境的配置,:本文主要介绍Python常用命令提示符使用方法的相关资料,文中通过代码介绍的... 目录一、python环境基础命令【Windows】1、检查Python是否安装2、 查看Python的安

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Java实现本地缓存的常用方案介绍

《Java实现本地缓存的常用方案介绍》本地缓存的代表技术主要有HashMap,GuavaCache,Caffeine和Encahche,这篇文章主要来和大家聊聊java利用这些技术分别实现本地缓存的方... 目录本地缓存实现方式HashMapConcurrentHashMapGuava CacheCaffe

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr