<mark>走进AC自动机</mark> AC自动机，听这名字就很高大上的亚子，起初还以为就是“AC自动机”。。。。。。开始真正的走进AC自动机了 简单介绍： AC自动机即为：多模匹配问题（像：经典的KMP算法就是单一模式匹配），于是要学会AC自动机，我们必须知道什么是Trie，也就是字典树。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。 于是就了解字典树是个啥东西 字典树 看图秒懂，有树的基本知识，就能明白字典...

<mark>最短路径问题（Dijkstra算法、Floyd算法）</mark> 将近一天的时间（其实中间大部分看手机去了）终于把最短路径这个经典问题算搞懂了吧 一、Dijkstra算法 简单介绍: Dijkstra算法（即迪杰斯特拉算法）时间复杂度(O(n^2))主要就是解决从单一源点到其他各点的最短路径问题； 基本思路: 设置两个顶点的集合：S和T（S+T=V）（也就是说S和T集合的元素个数的和为：总结点个数），集合S存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断地从集合T中...

凸包（Graham扫描法构建） <mark>PS</mark>:我的妈呀，心态爆炸，好像也不太难，看各种模板看的云里雾里的，真的还是自己动手敲来的好，几乎没多久就懂的差不多了。。。。 一个本该寒假就该掌握的知识，居然熬了我几个小时。。。。。。。 这一次还是很好的了解了凸包，以前看群里学长们说，觉得好高大上，好难的样子，仔细了解后发现其实也没有想象中的那么恐怖 凸包基本概念： 这就是一个简单的凸包： 其实凸包求法有很多种：比如<mark>卷包裹法</mark>（时间复杂度O(n*n)）、<mark>Graham扫描...

<mark>行逻辑链接的矩阵乘法（稀疏矩阵）</mark> 针对稀疏矩阵的乘法，如果按照普通矩阵的乘法进行计算时，时间复杂度必定很大，于是为了尽量降低时间复杂度同时方便运算： 可以设定一个累加器：temp[]数组，用来存放当前行中Cij的值，当前行所以元素全部算出之后，再存放到C.data中 同时参考稀疏矩阵快速转置的思想：稀疏矩阵普通转置与快速转置的链接 设置两个数组num[]与rpot[] 快速矩阵转置利用两个数组： copt[n+1]：表示每列的第一个非零元素在三元组表的位置 num[n+1]：表示每列的非零元素的个数 其中： ...

素数筛（埃氏筛+欧拉筛） 居然是一道模板题，院赛时就只知道暴力打表，发现毫无规律，然后暴力预处理，结果肯定TLE。。。。。，学长讲题解时，发现原来是数论中的： 素数筛： 于是赛后去学习了下素数筛，主要有两种方法 一、埃氏筛；二、欧拉筛 一、埃氏筛 思想：对于不超过n的每个非负整数p，删除是p的整数倍的数，当处理完这些数之后，还没被删除的数就是素数。 代码如下： #include<bits/stdc++.h> #define maxn 100 using namespace std; int vis[maxn+10]; //判断是不是素数 int ...

无向图判环（DFS与并查集） ps：一道本校院赛题，最后一小时应该开这道题的，导致到比赛结束这道题都看都没看 XP的校园漫步 题目描述 众所周知，XP学长即将毕业了，所以他觉得在校园里来一次漫步，在学校中有N个标志性的建筑，XP学长并不喜欢走小路，因此他会随机的选择某条大路从某个建筑走到另一个建筑，XP学长当然想要走遍校园内的所有建筑，但他会随机的选择某一条路去漫步，当然XP学长走完某一条路，绝对不会走这一条路，也就是说，如果XP学长当前所在建筑为v，他选择走v->u的某一条大路e，到达u建筑后，他在之后的漫步里不会再选择这条路，但是这仍然可能导致他到达某个建...

稀疏矩阵的普通转置与快速转置 相关介绍 稀疏矩阵即：由于矩阵大小较大，而大部分元素都是零，非零元素极少，于是稀疏矩阵采用三元组表存储 三元组的表示： typedef struct { int x; //非零元素行 int y; //非零元素列 int v; //非零元素本身的值 }node; //即非零元素所对应的三元组 typedef struct { int nu; //矩阵的行 int mu; //矩阵的列 int tu; //矩阵非零元素的个数 node data[2000]; }matrix; //整个矩阵的所有三元组所组成的结构 例题 ...

C++STL中的全排列函数 C++STL中的全排列函数为两个：next_permutation和prev_permutation 其中：next_permutation实现升序，而prev_permutation实现降序 下面以123的全排列为例： #include<cstdio> #include<iostream> #include<algorithm> using namespace std; int main() { int s[3]={1,2,3}; /**下面为next_permutation的用法*/ do { printf(&q...