题目传送门 题解 题目理解与强调 题目给出一个$m \times m$的一个棋盘，每个格子有三种颜色状态：红色、黄色、无色。每次从$(1,1)$开始走，可以走上下左右四个方向，最终走到$(m,m)$。 当从一个格子走向另一个格子时，如果两个格子的颜色相同，那么不需要花费金币；如果不同，则需要花费$1$个金币。另外， 可以花费$2$个金币让下一个无色…

题目传送门 题解 题目理解与强调 题目给出的是一个$n$个点$n$条边的无向连通图，$n$个点$n$条边可以看出这是一个基环树，树上每个点都有两种权值，分别表示美观度和长度，我们从一个点出发的时候，要找美观度最大的一条边走，如果那个点已经被走过了，就不走了，换向另一条边，过程类似于DFS。 思路分析 既然是在一棵基环树上遍历每个点，走过这$n$个点…

题目传送门 题解 题目理解与强调： 这道题目含有一条只包含小写字母的字符串。要求能够找到多少个 子序列 满足形式 $ a,b,\ldots,a,b $ 思路分析： 这道题是一道计数题。 很简单地，我们可以得出结论：题目的答案与字符串$ s $中的'$ a,b,\ldots,a,b $'的数量与位置有关，当我们读取到'$ a $'时，首先要…

字典树（Tire）简介 字典树，英文名 trie。顾名思义，就是一个像字典一样的树。 先放一张图： 可以发现，这颗字典树用边来表示字符，而从根结点到树上某一结点的路径就代表了一个字符串。举个例子， $ 1 \rightarrow 4 \rightarrow 8 \rightarrow 12 $表示的就是字符串 caa。 字典树（Trie）的建立 原…

传送门 题意理解与强调 读入一个 $n \times n$ 的矩阵。注意字符串的读入方式！ 转 $90\degree$：图案按顺时针转 $90\degree$。转 $180\degree180°$：图案按顺时针转 $180\degree$。转 $270\degree$：图案按顺时针转 $270\degree$。反射：图案在水平方向翻转（以中央铅垂线…

线段树简介 主要作用： 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 时间复杂度： 每一次查询、修改：$$ O(log N) $$ 基本形态： 若用 $ tree[ ] $ 表示树， $ x $ 表示线段树上的节点， $ tree[x] $ 表示节点所表示的…

强联通分量简介 定义 在有向图$G$中，如果两个顶点$u,v$间有一条从$u$到$v$的有向路径，同时还有一条从$v$到$u$的有向路径，即：两个点可以互相到达，则称两个顶点强连通。如果有向图$G$的每两个顶点都强连通，称$G$是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量。 强联通分量算法 Tarjan算法 主要作用 缩点求无向图…

ST表简介 主要作用 ST 表是用于解决 可重复贡献问题 的数据结构。 可重复贡献问题：是指对于运算$ opt $，满足$ x $ $ opt $ $ x $ = $ x $，则对应的区间询问就是一个可重复贡献问题。例如，最大值有$ max(x,x) $，gcd有$ \gcd(x,x)=x $，所以RMQ和区间GCD就是一个可重…

在一个图中进行DP，对于部分题目来说随意一个顺序会破坏DP的无后效性原则，例如题目”洛谷：P3387 【模板】缩点“中，需要找出DAG中的一条路径，且这条路径上的点权和最大。我们需要从枚举的第一个点开始，记录$ dp[i] $，表示从第一个点到当前节点的最大点权和，每次向下枚举一个点，都需要保证我们要枚举的这个点的入度为$0$，即保证它不会再被其他…

题目传送门 题解 题目理解与强调 这道题目翻译过来即为：一个图中有 $ n $ 个点，使用 $ n-1 $ 条边将这 $ n $ 个点连接起来，形成一棵树，在选用这 $ n-1 $条边时，要求每次每个点找到与它最近的点连接，直到所有节点连接到一起，其他的连边要求： 如果两个点申请相互连边，则让它们只连一条边；如果三个或以上的点连成环。则三条边中最短…