算法

自动机(确定有限状态自动机)

这里的“自动机”指的是”确定有限状态自动机”。而自动机是信息学奥林匹克竞赛、计算机科学中被广泛使用的一个数学模型,其思想在许多字符串算法中都有涉及,学习自动机有助于理解上述算法,但是学习自动机前一定要先了解基础图论的相关知识,这样才更好理解自动机。

反演变换的性质

反演本质上是一种几何变换,常见的几何变换还有平移、旋转、反射……反演变换适用于题目中存在多个圆/直线之间的相切关系的情况。利用反演变换的性质,在反演空间求解问题,可以大幅简化计算。这篇文章主要介绍反演的定义和一些常用性质一、定义设O是平面π上的一个定点,

图的遍历DFS深搜优先搜索及C语言代码实现

1.图的遍历在理解DFS算法之前,我们首先需要对什么是遍历进行了解,遍历的概念就是:从某一个点出发(一般是首或尾),依次将数据结构中的每一个数据访问且只访问一遍。2.DFS简介DFS(Depth-First-Search,深度优先搜索)算法的具体做法是:从某个点一直往深处走,

图的储存方式

图是一个好东西,能够使用图来模拟或解决很多生活问题,同时在各大比赛上都少不了有关于图的问题.图是关系与顶点与边的,那么我们该如何来存入图的信息呢?(1)直接存边我们开一个数组,数组里每个元素是图的一条边。其中存的每一条边都包含这些信息:顶点v与u,边的权值。

排序算法简介

什么是排序?就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,

枚举算法的思想与实例讲解

枚举算法是我们在日常中使用到的最多的一个算法,本篇将会介绍枚举算法的思想与实例讲解,在使用频率上,枚举算法在蓝桥杯比赛里用的次数非常多,所以需要在平时多练习做题,毕竟实践检验真理,毕竟枚举在考试中出现的频率非常高,可谓是得枚举者得天下,下面我们就来讲讲枚举。

树上启发式合并

启发式算法是什么呢?启发式算法是基于人类的经验和直观感觉,对一些算法的优化。最常见的就是并查集的按秩合并了,有带按秩合并的并查集中,合并的代码是这样的:voidmerge(intx,inty){intxx=find(x),yy=find(y);if(size[xx]<size[yy])swap(xx,

记忆化搜索实例讲解

什么是记忆化搜索?记忆化搜索在本质上,还是动态规划,只是实现方式采用了深度优先搜索的形式,但是它不像深度优先搜索那样重复枚举所有情况,而是把已经计算的子问题保存下来,这样就和动态规划的思想不谋而合了。本篇文章会通过最简单的例子对记忆化搜索进行深入讲解,帮助大家学会什么是记忆化搜索。

结合实例解析双向搜索

本篇将会结合实例解析双向搜索。一、双向搜索当给出了起点状态与终点状态时,使用普通的搜索从起点向下搜索,则效率会很低,搜索树会非常庞大;所以,可以使用双向搜索,及从起点与终点同时向中间搜索,搜索到同一个状态时,将从起点与终点搜索的值相加得到最终值的搜索;一般给出“始态”与“终态”时,

动态DP实例讲解

一、简介有一类问题,它可以采用DP解决。但是,如果我们加入区间查询,单点修改甚至区间修改,普通DP望尘莫及。于是,动态DP就应运而生了。二、例题例题一:给定一个长度为n的序列,你需要维护两种操作:①查询一个区间的最大子段和;②单点修改(即将一个位置上的数改成另一个数)Solution首先,