突然发现自从上次搞崩了博客之后就很少再写博客了啥的。不过确实没啥好写的啦。
　　一直想着每天写写日记的来着，最终不了了之。
　　我就是这么一个永远静不下心来的人吧。

前言

　　第一次接触差分约束，对着WC2006的课件以及一堆博客看了一个下午总算明白得差不多了。以前听说过这个，一直觉得是很难、很高深的算法，学了之后发现它确实很高深，但不是很难。还挺好懂……我居然看了一下午哎←_←

基本原理

　　以储存边的方式来储存图，通常用在点的数目太多，或两点之间有多条弧的时候。主要用到四个参数，head[u]存储以u为起点的第一条边的存储位置，to[pos]表示第pos条边的终点，nxt[pos]存储与此边同起点的下一条边的位置，w[pos]存储第pos条边的权值。

前置技能

• 前向星
• 图论相关

算法简介

　　求最短路的算法之一，类似于Dijkstra算法，对于每一个点集中的点v，逐步减少起点s到v的最短路长度的估计值，知道达到其最短路径值。同时，Bellman-ford算法还会返回一个bool类型的值如果不存在从s可达到的负权回路就返回true，否则false，这样就能够在存在负权边的情况下解决单源最短路的问题，这点上比Dijkstra算法要优。由于该算法更多的是对边进行操作，因此能更高效地解决稀疏图的最短路问题。算法复杂度Θ(V*E)。

前置技能

• 前向星
• 图论相关

算法简介

　　全称Shortest Path Faster Algorithm，可以解决存在负权边的最短路问题（但无法解决存在负权环的图），复杂度上比Bellman-ford要优。用一个数组dist记录每个节点最短路径的估计值，用前向星存图，设立一个队列保存待更新的点，更新时依次取出队首节点，用该节点估计值来更新与之联通的点v（松弛操作），如果v的最短路估计值有所更新而v不在队列中，则将v加入队尾。重复执行以上操作直到队列中没有元素。期望复杂度Θ(ke)，k为每个顶点入队的次数（一般<=2），e为顶点个数。

题面

【问题描述】

给定一个由N个整数构成的数列{A}，
求出如下描述的两个最长子串：
使得GCD(Ai,Ai+1,…,Aj)=1，其中 (1 ⩽ i ＜ j ⩽ N)，其串长作为参数 α。
满足LCM(Ai,Ai+1,…,Aj)=AiAi+1…Aj，其中 (1 ⩽ i ＜ j ⩽ N)，其串长作为参数 β。

　　stm误删了原先hexo的文件夹，于是生无可恋只能重新搭。
　　就抢救一些算法方面的博客吧，其他的不管了。
　　以后再也不作死了……！