浮云世事改, 过月此心明

堆的概览在这篇文章中，将会对c++中的stl容器中的堆进行一个讲解，主要讲解堆的概念，堆的使用，模拟堆，堆排序和优先队列这些内容 堆的概念堆的本质实际上是一个完全二叉树，怎样才算是一个完全二叉树呢？ 以下这些便是完全二叉树 非完全二叉树 堆的堆序性堆分为两种类型,第一种是大根堆，第二种是小根堆 小根堆，顾名思义，就是指在每一棵二叉树中，父节点都要比它的两个子节点要小，而所有点连起来的最上面的祖父节点就是最小的， 大根堆就是与小根堆完全相反的两个事物，在这里就不多做赘述了 堆的储存首先，我们可以按照层序遍历的顺序来给堆里面的元素编号 (层序遍历就是一层层的往下走,类似于宽度优先搜索) 由于堆的层数是与编号是一一对应的,所以我们可以将一个堆通过使用一个一维数组的方式来实现 ​ 用一个父节点的位置找到子节点位置的方式就是通过数学规律来实现的，如这样2*n+1和2*n+2，便是上图中父节点找到子节点的一种方式 ​ 但是在竞赛中为了更加方便，一般情况下是将自顶而下的第一个父节点对应到一维数组中的第二个位置，这样的话，每一个父节点查找子节点的方式就改为了2*n和2*n ...

bellman-ford算法今天，我们来讲讲第二种最短路算法，boolman_ford算法，这个算法可以用来处理两种情况 第一种是含有 边权可能为负数 这种情况 第二种是 给定了步数 的这种情况 接下来给的这道题就是典型的只可以使用boolman_ford算法解决的，如果用spfa算法(另外一种负权类最短路算法)的话会被控时间 题目给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数 请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible 输入格式第一行包含三个整数 n,m,k 接下来m 行，每行包含三个整数x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z 点的编号为 1∼n 输出格式输出一个整数，表示从 1号点到 n号点的最多经过k 条边的最短距离。 如果不存在满足条件的路径，则输出 impossible 数据范围1≤n,k≤5001≤m≤100001≤x,y≤n任意边长的绝对值不超过 10000 输入样例：3 3 1 1 2 1 2 3 1 1 3 3 输出样例：3 算 ...

最短路问题的几种基本形式我们约定俗成这样的惯例，在今后遇到最短路问题的时候，n是格子数，m指的是行数 在学习最短路算法的时候，我们主要学习的是图论中的代码的实现，而不是侧重于对代码的证明 小细节稀疏图用堆优化，稠密图用朴素算法，负权边多用spfa 边数分析的情况下，边数很多时，稠密图用邻接矩阵，稀疏图用邻接表来存 最短路只考虑有向图的应用，无向图是一种特殊的有向图 有向图的意思是指两个点是有指向性的，就比如说有两个点a,b，a点指向b点，这就是指向性 而无向图的意思就是指a和b之间是没有指向性的，那我们就可以人为的进行指向性判断，我们让它们两个互相指向，这样的话不就相当于没有指向性了吗?(嘿嘿(●ˇ∀ˇ●)) 朴素dijkstra算法现在我们来介绍一下最短路问题中的第一种单源最短路算法，它的典型例题是这样的 1.例题给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1 1.1.输入格式第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在 ...

归并排序看前须知首先，归并排序和快速排序一样，在算法竞赛中可以直接使用c++中的algorithm来使用就行，但是在面试啊，笔试啊等一些可能要手写代码的地方上面，学习这个排序的思想和模板还是很好的。这个归并排序算法主要运用了二分的思想，对于一个有穷无序数组进行每回分成两半的方式来进行。 崩坏3小剧场正如我听过的一句话，如符华小姐所说，我们先制作一个馒头，第一天吃一半，第二天吃第一天的一半，第三天吃第二天的一半，这样下去就可以永远吃不完我们的馒头了hhh 题目概要给定你一个长度为 n的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。 输入格式 输入共两行，第一行包含整数 n。 第二行包含 n 个整数（所有整数均在 1∼10^9,1∼10^9 范围内, 表示整个数列。） 输出格式 输出共一行，包含 n 个整数，表示排好序的数列。 算法实现void merge_sort(int q[], int l, int r) { if (l >= r)return; int mid = l + r >> 1;& ...

快速排序给定你一个长度为 n的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 前摘提要首先我先来介绍一下快速排序算法，它被誉为最快排序算法，可以快到nlogn级别，而且在c++中已经有了相关的函数sort(),所以在算法竞赛中它的模板其实也没有那么重要(毕竟算法竞赛是要赶时间的嘛，太慢了题都搞不定)，但是这里还是要介绍一下这个算法的思想。 算法思想void quick_sort(int q[], int l, int r) { if (l >= r) return; int x = q[l]; int i = l - 1, j = r + 1; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + ...

bfs中的八数码问题例题在一个 3×33×3 的网格中，1∼8 1∼8 这 88 个数字和一个 x 恰好不重不漏地分布在这 3×3 3×3 的网格中。 例如： 在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。 我们的目的是通过交换，使得网格变为如下排列（称为正确排列）： 例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。 交换过程如下: 现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。 分析看完了题目，这让我想起，我们之前可能玩过一种拼图的游戏，在玩游戏的过程中我们会得到一张比较好看的图片，但是它缺了一个口！然后呢，别人将这个图片给打乱了，就像9宫格这样打乱，让我们一个一个对着这个口移动回去。 在移动的过程中我们会发现，我们不是计算机，不可以很快的判断出我们要移动几步，因此我们会先按照我们的感觉，对x这个缺口的上下左右依次进行移动，看看移动之后是否会更快地把这个拼图给拼回去。但是我们在拼图的时候也可能会出现重复的情况，比如我们移动了若干步，最后我们还是回到了起点，这样的话，我们之前移动的那些步 ...

主要是拿来测试的hh

八皇后问题n−n−皇后问题是指将nn 个皇后放在 n×n``n×n 的国际象棋棋盘上, 使得皇后不能相互攻击到, 即任意两个皇后都不能处于同一行, 同一列或同一斜线上 这道题目有两种分析情况，我先来分析第一种。 设变量#include<iostream> using namespace std; const int N = 20; int n; bool col[N], dg[N], udg[N]; char g[N][N]; 首先，我们要知道皇后在每一行，每一列，每一斜列都不可以遇到一样的皇后，那么我们不妨创立三种变量来表示竖向的，左斜方向的，右斜方向的三个bool数组来分析，同时我们要创立一盘棋，用char变量来表示 摆棋这样我们就可以把变量创建出来了，第二步就是摆上一盘棋 int main() { cin >> n; int i, j; for (i = 0; i < n; i++) for (j = 0; j < n; j++) g[i][j] = '.'; ...

简介这是我的第一篇hexo博客文章。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick StartCreate a new post$ hexo new "My New Post" More info: Writing Run server$ hexo server More info: Server Generate static files$ hexo generate More info: Generating Deploy to remote sites$ hexo deploy More info: Deployment