标签:算法
单调栈 以这道题为例:P5788。我们考虑维护一个单调栈,里面存的是下标,使里面的下标对应的元素从栈顶到栈底是单调上升的。 我们从 (nrightarrow 1) 枚举 (a_i) 对于每个 (i),如果栈非空,令栈顶的下标为 (j),若 (a_j) 不比 (a_i) 大,那么这个栈顶元素由于值又
割点 定义: 在无向图连通图中,若把点 (x) 删去后整个图就不连通了,则 (x) 为割点(割顶)。 朴素方法: 每次删去一个点,然后判断图是否连通,时间复杂度为 (O(n(n+m)))。 Tarjan 算法: (dfn_x):(x) 被 dfs 到的时间戳 (low_x):在 (x) 及以后被搜
D.The Game of Eating 题意: 一共有m道菜,n个人轮流点,一共点k道。 第i个人对第j道菜的喜爱程度(A_i)公开, 一个人点了菜所有人都可以吃到。 每个人都希望最大化自己的喜爱程度之和,求最终的点菜集合。 分析: 倒着贪心,如果最后一个人最喜欢吃的菜没被选那么他一定会选择这道
持续更新中~ 索引 1 快读快写 1.0 快读快写 2 数据结构 2.0 堆 2.0.0 二叉堆 2.0.1 左偏树 2.1 线段树 2.2 树状数组 2.3 st表 2.4 单调栈 2.5 单调队列 2.6 可持久化数据结构 2.6.0 可持久化数组 2.6.1 可持久
哈希表 作用:将庞大的空间,映射到小的空间,集中数据,一般用取模,取模的数尽量取质数,最大程度减小冲突 操作:一 般是添加和查找元素,删除元素通常有一个标记数组,对元素标记为已删除 离散化相似,离散化是特殊的哈希方式,离散化处理的数据是单调的,相对位置不变 映射会出现冲突,如将两个不同的数映射
Burnside 定理 问题: 给定一个 (n) 个点,(n) 条边的环,有 (m) 种颜色,给每个顶点染色,问有多少种本质不同的染色方案,答案对 (10^9+7) 取模 注意本题的本质不同,定义为:只需要不能通过旋转与别的染色方案相同。 题目初步解读 我们考虑如果不要求本质不同只需要 (n^n)
链表定义 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑是通过链表种的指针链接次序实现的。链表由一系列节点组成,每个节点包括两部分:一个是存储数据元素的数据域,一个是存储下一个节点地址的指针域。单向链表从头节点(也可以没有头节点)开始,指针指向下一个节点的位置,只能由上一个节点指
扫描线是用来求解图形面积并的一个算法。 问题引入 给定 (n) 个长方形,求它们的面积并。下面以两个长方形为例: 对于这个问题,可以有容斥等做法,但是还有个更简单的方法——扫描线。 扫描线 扫描线,顾名思义,就是,拿一条“线”取扫(这里是从下往上扫,其实其它的扫的方式也是可以的): 如图所示,
「观前提醒」 「文章仅供学习和参考,如有问题请在评论区提出」 目录引入基本原理建树区间查询单点修改区间修改 + 懒惰标记例题P3372 【模板】线段树 1 - 洛谷P3373 【模板】线段树 2 - 洛谷小结参考资料 引入 线段树(Segment Tree)是算法竞赛中常用的用来维护区间信息的
P1196 [NOI2002] 银河英雄传说 使用带权并查集维护: 每个战舰所属列。 每个战舰到当前列第一个战舰的距离。 每列的战舰数量。 如何求同列战舰之间相隔的战舰数量? 使用两战舰到当前列头部的距离之差减1即可得到。 如何在并查集合并时维护每个战舰到当前列第一个战舰的距离? 当前点到当
一、什么是数据结构 1、数据结构的起源 1968年,美国高德纳教授,《计算机程序技术艺术》第一卷《基本算法》提出,开创了数据结构和算法的先河。 数据结构是一门研究数据之间关系、操作的学科,而非计算数据方法 数据结构+算法=程序 揭露了程序的本质,沃思凭借这个观点获得图灵奖 2、数据结构中的基本概念
深度优先搜索 一条路走到黑 回溯/剪枝 每一个dfs都对应一个搜索树 解决全排列,搜索所有可能解 宽度优先搜索 一层一层搜索 解决最短路问题 搜索方式 数据结构 空间 特点 DFS stack O(h) 不具有最短性 BFS queue O(2^h) 最短路 树与图的存储 有向图/树 每
功能受限的表结构 1、队列: 只有两个口进出数据,一个专门进入数据,另一个专门出数据,先进先出,FIFO表。 顺序队列: 存储元素的连续内存的首地址 容量 队头位置(出队) 队尾位置(入队) [元素数量](可有可无) 运算:创建、销毁、清空、出队、入队、队空、队满、队头、队尾、元素数量 需要注意的
常用STL: vector 变长数组,倍增的思想 初始化: //初始化 vector<int> a; vector<int> a(n); vector<int> a[n]; vector<int> a(n, 0);//长度为n,值为0 操作:
「观前提醒」 「文章仅供学习和参考,如有问题请在评论区提出」 目录前言定义性质求 LCA倍增算法Trajan 算法树链剖分基本概念基本性质具体实现参考资料 前言 简单的模板整理,只是概括了一下具体的实现方法(说到底是给自己写的),如果看不明白可以去看原视频(讲的很好),链接在参考资料里。 定义
树型结构: 1、树的基本概念: 一种表示层次关系(一对多)的数据结构 有且仅有一个特定节点,该节点没有前趋节点,称为这棵树的根节点 剩余有n个(n>=0)有限个多节点组成互不相交的子集,每个子集都可以是一棵树,都被称为根节点的子树 注意:树中有树,树型结构具有递归性 2、树的表示方式: 倒悬
最短路 单源最短路 求从一个点到其他所有点的最短距离 所有边权是正数 朴素Dijkstra算法 O(n^2)用于稠密图 m >= n 步骤: dist[i]:每个点离起点的距离 S:已经确定最短距离的点 V:没有确定最短距离的点 初始化所有点的距离dist[起点] = 0;dist[
貌似这次很难,还好去吃烧烤了 A - To Be Saikyo (abc313 A) 题目大意 给定(n)个数(a_i),问第一个数要成为唯一的最大的数,应该加多少。 解题思路 找到后面的最大的数(m),答案就是(max(0, m + 1 - a_0))。 神奇的代码#include <
trick大意 我对于这个trick的理解为:支持位运算的高精度 维护一个以 (b)为基数的大数 (N),并支持以下功能: 给定(可能是负)整数 (|x|, |y| leqslant n),将 (x b^y)加到 (N)。 (N geqslant 0)时,给定(k),打印(N)的第(k)位数字(指