月度归档: 2021年10月

11 篇文章

thumbnail
P3956 [NOIP2017 普及组] 棋盘 题解
题目传送门 题解 题目理解与强调 题目给出一个$m \times m$的一个棋盘,每个格子有三种颜色状态:红色、黄色、无色。每次从$(1,1)$开始走,可以走上下左右四个方向,最终走到$(m,m)$。 当从一个格子走向另一个格子时,如果两个格子的颜色相同,那么不需要花费金币;如果不同,则需要花费$1$个金币。另外, 可以花费$2$个金币让下一个无色…
thumbnail
P6037 Ryoku 的探索 题解
题目传送门 题解 题目理解与强调 题目给出的是一个$n$个点$n$条边的无向连通图,$n$个点$n$条边可以看出这是一个基环树,树上每个点都有两种权值,分别表示美观度和长度,我们从一个点出发的时候,要找美观度最大的一条边走,如果那个点已经被走过了,就不走了,换向另一条边,过程类似于DFS。 思路分析 既然是在一棵基环树上遍历每个点,走过这$n$个点…
thumbnail
CF1084C The Fair Nut and String 题解
题目传送门 题解 题目理解与强调: 这道题目含有一条只包含小写字母的字符串。要求能够找到多少个 子序列 满足形式 $ a,b,\ldots,a,b $ 思路分析: 这道题是一道计数题。 很简单地,我们可以得出结论:题目的答案与字符串$ s $中的'$ a,b,\ldots,a,b $'的数量与位置有关,当我们读取到'$ a $'时,首先要…
thumbnail
字典树(Tire)
字典树(Tire)简介 字典树,英文名 trie。顾名思义,就是一个像字典一样的树。 先放一张图: 可以发现,这颗字典树用边来表示字符,而从根结点到树上某一结点的路径就代表了一个字符串。举个例子, $ 1 \rightarrow 4 \rightarrow 8 \rightarrow 12 $表示的就是字符串 caa。 字典树(Trie)的建立 原…
thumbnail
P1205 [USACO1.2] 方块转换 Transformations 题解
传送门 题意理解与强调 读入一个 $n \times n$ 的矩阵。注意字符串的读入方式! 转 $90\degree$:图案按顺时针转 $90\degree$。转 $180\degree180°$:图案按顺时针转 $180\degree$。转 $270\degree$:图案按顺时针转 $270\degree$。反射:图案在水平方向翻转(以中央铅垂线…
thumbnail
线段树
线段树简介 主要作用: 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。 时间复杂度: 每一次查询、修改:$$ O(log N) $$ 基本形态: 若用 $ tree[ ] $ 表示树, $ x $ 表示线段树上的节点, $ tree[x] $ 表示节点所表示的…
thumbnail
强联通分量
强联通分量简介 定义 在有向图$G$中,如果两个顶点$u,v$间有一条从$u$到$v$的有向路径,同时还有一条从$v$到$u$的有向路径,即:两个点可以互相到达,则称两个顶点强连通。如果有向图$G$的每两个顶点都强连通,称$G$是一个强连通图。有向非强连通图的极大强连通子图,称为强连通分量。 强联通分量算法 Tarjan算法 主要作用 缩点求无向图…
thumbnail
ST表(稀疏表)
ST表简介 主要作用 ST 表是用于解决 可重复贡献问题 的数据结构。 可重复贡献问题:是指对于运算$ opt $,满足$ x $ $ opt $ $ x $ = $ x $,则对应的区间询问就是一个可重复贡献问题。例如,最大值有$ max(x,x) $,gcd有$ \gcd(x,x)=x $,所以RMQ和区间GCD就是一个可重…
thumbnail
拓扑排序解决DP无后效性问题
在一个图中进行DP,对于部分题目来说随意一个顺序会破坏DP的无后效性原则,例如题目”洛谷:P3387 【模板】缩点“中,需要找出DAG中的一条路径,且这条路径上的点权和最大。我们需要从枚举的第一个点开始,记录$ dp[i] $,表示从第一个点到当前节点的最大点权和,每次向下枚举一个点,都需要保证我们要枚举的这个点的入度为$0$,即保证它不会再被其他…
thumbnail
P1265 公路修建 题解
题目传送门 题解 题目理解与强调 这道题目翻译过来即为:一个图中有 $ n $ 个点,使用 $ n-1 $ 条边将这 $ n $ 个点连接起来,形成一棵树,在选用这 $ n-1 $条边时,要求每次每个点找到与它最近的点连接,直到所有节点连接到一起,其他的连边要求: 如果两个点申请相互连边,则让它们只连一条边;如果三个或以上的点连成环。则三条边中最短…