难理解的还是前后缀表的问题，这个表存的这些数字的目的是 就是要碰到不匹配的时候向右移位的个数 从而防止一些不必要的查找。 具体这个表里储存的什么内容呢请看下图 因为字符串下标从0开始，所以为了方便操作，我把数组整体往后移了一位 整体后移以后，我没有去掉最后最长的前后缀那个一数（因为方便我找出所有的字符串） 把最开头补上-1 为什么第一个位置是-1，是因为当他为0的时候在kmp中 当len=0时，（len=prefix[len]）之后len=-1，再加1正好是0的下标。 再看这一张图（当匹配失败时的操作）当匹配失败，查询prefix表中当前的值并将它付给len （代码中&&&a...

你玩过华容道的游戏吗？这是个类似的，但更简单的游戏。看下面 3 x 2 的格子 +---+---+---+ | A | * | * | +---+---+---+ | B |  | * | +---+---+---+ 在其中放5张牌，其中A代表关羽，B代表张飞，* 代表士兵。还有一个格子是空着的。你可以把一张牌移动到相邻的空格中去(对角不算相邻)。 游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。 输入： 输入存在多组测试数据，对于每组测试数据： 输入两行6个字符表示当前的局面 输出： 对于每组测试数据输出一个整数表示答案 样例输入： * A **B A B *...

简单记录一下自己的代码，以后方便复习 其实有了这样子的一个模板，题目变式自己改改就可以，比如说加减变成乘除等等。 #pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <math.h> #include <string> #include <list> #include <...

今晚上干了许久的链表 看见指针就头大的我真的是头皮发麻了一晚上 代码中写有注释，虽然不是太详细，但是了指针熟练的同学应该可以看懂 main函数中请自由发挥 #pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <math.h> #include <string> #include <l...

dfs与bfs的很直接的应用就是拓扑排序。 拓扑排序如果用数组来模拟链表进行操作，既解决了稀疏图的空间问题，又解决了用链表进行操作麻烦的问题 但是拓扑排序并不是数字大小之间的排序，而是某些事情之间的顺序有着相互的顺序关系，就好比说你学了c语言基础以后再继续学习更高深的数据结构学完数据结构之后才能够去做一些比较难一些的算法题 第一个题 hdu3342 （基于bfs的拓扑排序） HDU3342 给出一部分人的师徒关系，让我们来判断是否合法，比如说（1是2的师傅，2是1的师傅关系不合法）也就是可以理解为形成了自环，可以拓扑排序的要求是这个图是有向无环图，如果拓扑排序没有矛盾，也就是说所有结点都被遍...

首先说一下定义： 欧拉路：从图中某点出发可以遍历全图，图中的每条边通过且只能通过一次。 欧拉回路：具有欧拉路性质且起点位置与终点位置相同。 主要问题就是一个图中是否存在欧拉路，和打印欧拉路路径。 先说如何判断是否存在欧拉路或者欧拉回路 首先他必须是个连通图 （1）如果是一条无向连通图：如果地图中的点全围偶数点那么他必为欧拉回路； 如果存在两个奇数点，那他只是一个欧拉路，其中的某个奇数点为起点，另一个为终点。 （2）如果是一条有向连通图：那就跟图的出度入度有关系如果一个有向图存在欧拉回路那么每个点的出度与入度和为0。如果只有一个出度入度和为1，一个为-1，那么这个有向连通图则存在欧拉路。 下...

1.割点和割边： 割点：在无向图中，删除某个节点后，图的连通分量数量增加，则称该节点为割点 桥：如果删除某条边后，连通图变得不再连通，则此条边为桥，或者为割边 下面说一种用DFS求割点的算法，即利用了“深度优先搜索生成树”求割点。 如何判断一个点是否为割点呢？ （1）如果这个点为搜索出发的点（根节点）如果他有两个及两个以上的路出发，那么这个根节点即是割点。 （2）如果他不是根节点，那么我们就要判断通过他继续往下搜索是否有路可以返回他的祖先（不能通过他的父节点） 这里主要用了两个数组来实现以上操作，即low[]和num[],low记录了此数组能返回的最早的结点，num即为进入这个递归的顺序，专业...

1.强连通分量： 强连通分量可以理解为边数最少的情况下是一个环。 这里写了一个模板题用的是tarjan算法，当然还有其他算法。 tarjan算法的关键其实还是对于num数组和low数组的使用 然后可以用栈来分离不同的ssc 感觉跟双边连通分量有异曲同工之妙 第一题hdu1296 #pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <cstring> #include <cmath>...

昨天做了蓝桥杯的时候，发现自己对于记忆优化搜索甚是不熟悉，所以今天随便找了几个基础题做做，顺便写下两片题解，顺便用了一下devc++敲的代码，发现没有代码补全真的可以说是灰常难受了。。。 洛谷P3183 [HAOI2016]食物链 ： 题目描述 如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3…am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链 输入格式 第一行两个整数n和m,接下来m行每行两个整数ai...

因为方便看所以转载一篇博客园的的文章，非常不错 原文链接（重要的事情说三遍）： https://www.cnblogs.com/xiaxiaoxu/p/8436795.html https://www.cnblogs.com/xiaxiaoxu/p/8436795.html https://www.cnblogs.com/xiaxiaoxu/p/8436795.html 1、匹配一行文字中的所有开头的字母内容 #coding=utf-8 import re s="i love you not because of who you are, but because of who...

最近实在不知道干些什么，感觉自己除了水题什么都不会做，算了去刷一刷图论的水题吧本来想合起来一起发，想了想太长的话以后看起来也不方便，题目所以今天晚上就先发了dij部分，由上到下由易变难。 1.POJ 2387 Til the Cows Come Home（优先队列优化+邻接表） 2.poj 1502 (最短路) 3.POJ3268-Silver Cow Party-（优先队列优化+邻接表） 4.poj 1511 Invitation Cards（优先队列+dij+链向式前向星存图） 5.Heavy Transportation POJ - 1797（优先队列优化+邻接表） 6.poj2253...

继第一篇的后续，又来刷水题了，写的是SPFA算法，这个算法的复杂度比较玄学，感觉能不用就不用了，但是他的好处就是可以判断负圈。 3月26日： 1.POJ 1847 Tram 题意：在一个交通网络上有N个路口, 每个路口指向多个方向, 默认驶向第一个方向, 驶向其他方向时需要进行一次操作, 求从a到b最小的操作数 直接建图即可，默认的方向权值为0，其他方向权值为1。 #pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #in...

首先大致说一下栈这个数据结构，他是一个先进后出的结构，就好比家中摆盘子一样，洗好的盘子放到最上面，当要用的时候从最上面拿走（当然只是一般情况，你要是每次都从下面抽走盘子我也没办法）。 这样的话我们可以直接用前面学过的线性表来实现，但是链的哪边是top呢？仔细分析一下就会发现如果我们用链的结尾作为top，我们删除它（因为这是一个单链表，指针只指向下一个元素），所以当我们用结尾作为top，删除元素后，找不到上一个元素的地址在哪。 struct Snode{ int date; Snode *next; }; typedef Snode* Stack; 栈的基本操作： 1.创建...

写了几个查并集得题，成功把自己写晕了 之后写下面得题（写不下去了） **poj-2912 poj 文章目录 1.POJ - 1611（模板题） 2.HDU - 1213（模板题） 3.poj2236（稍稍复杂的查并集） 4.HDU - 1272（查并集判断图是否连通） 5.poj-1308(跟上面的题目很像)（只是多加了入读这个条件而已） 6.poj-1456(此题纯属乱入)贪心解决125ms 7.HDU - 3038（带权的查并集） 8.poj-1733（查并集+离散化） 9.poj2492（种类查并集） 10.poj...