自己对Dijstra算法的理解是：首先输入保存点，边的权值（注意无向图和有向图在保存时的区别）。将表示从起点st到顶点 i 的距离的d[ i ]数组的每一个值初始化为INF，令d[st] = 0。 遍历d[ ]数组的下标 i （即顶点 i）这个操作是通过优先队列来实现的，然后遍历以顶点 i 为起点的边，更新d[ i ]的最小值。最后直接访问d[en]，即可得到最短距离。通过模板题来熟悉一下这个算法吧，最短路之HDU2544 1 #include <iostream>2 #include <c...
Manacher算法能够在O(N)的时间复杂度内得到一个字符串以任意位置为中心的回文子串。其算法的基本原理就是利用已知回文串的左半部分来推导右半部分。例题：HDU 3068 1 #include<stdio.h>2 #include<string.h>3 #include<iostream>4usingnamespace std;5constint N=110005;6char s[N],cpy[N<<1];7int rad[N<<1];8void manacher(char *s,int len,int rad[])9{ 10for(int i=1,j=0,k;i<len;i+=k) 11 { 12while(s[i-j-1]==s[i+j+1]) ...
算法基础课相关代码模板活动链接 —— 算法基础课快速排序算法模板 —— 模板题 AcWing 785. 快速排序 void quick_sort(int q[], int l, int r) {if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + 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 + 1, r);}归并排序算法模板 —— 模板题 AcWing 787. 归并排序void m...
/*INPUT6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6OUTPUT15*/ #include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> usingnamespace std; constint N=1e5; struct node {int u,v,w;booloperator<(const node &C)const{return w<C.w;//表示以w从小到大排序 } }t[N]; int n,m; int p[1001]; int cha(int x) {//return x==p[x]?p[x]:cha(p[x]);if(x!=p[x]){p[x]=cha(p[x]);/...
a*x+b*y=gcd(a,b)，该方程一定有解（原因暂时留坑，以后来填），扩展欧基里德算法就是用来求x，y的。 具体求法，因为a*x+b*y=gcd(a,b)，而gcd(a,b)=gcd(b,a%b)，所以有b*x1+(a%b)*y1=gcd(a,b)，而a%b=a-(a/b)*b，代入之后得：a*y1+(x1-(a/b)*y1)*b=gcd(a,b)，即x=y1,y=x1-(a/b)*y1，这样用递归就可以实现了。 扩展欧基里德算法的模板：1void ex_gcd(int a,int b,int &x,int &y,int &d){ 2if(!b) x=1,y=0,d=a; 3else{ex_gcd(b...
[算法模板]FFT-快速傅里叶变换感谢ZYW聚聚为我们讲解FFT~思路我懒，思路和证明部分直接贴链接：rvalueLSJ-FFT与NTT基础代码主要思想是利用了单位根特殊的性质（n次单位根后一半幂跟前一半幂取值相等）。只是因为式子中奇数次幂还要提出来个\(\omega_n^k\)，这个东西只要取个反就好了（即对称性：\(\omega_n^k=-\omega_n^{k+\frac{n}{2}}\)）。FFT递归：#include <cstdio> #include <cmath> using namespace std; const int maxn=2e...
1/* 2 algorithm : High-Precision FFT3 4*/ 5 #include <cstdio>6 #include <cstring>7 #include <cmath>8 #include <algorithm>9#define N 20000510#define pi acos(-1.0) // PI值 11usingnamespace std;12struct complex13{14double r,i;15 complex(double real=0.0,double image=0.0){16 r=real; i=image;17 }18// 以下为三种虚数运算的定义 19 complex operator + (const complex o){20return compl...
ps：数组下标从0开始哦！①求逆序对版int tmp[MAX],rec[MAX]; int sum;//求逆序对个数 void merge(int low,int mid,int high) {int i=low,j=mid+1,k=low;while(i<=mid&&j<=high){if(rec[i]>rec[j]) {tmp[k++]=rec[j++];sum+=mid-i+1;}else tmp[k++]=rec[i++];}while(i<=mid) tmp[k++]=rec[i++];while(j<=high) tmp[k++]=rec[j++];for(i=low;i<=high;i++) rec[i]=tmp[i]; } void mergesort(int low,int high) {if(low<high){int mi...
实现功能：求出二维平面内一对散点的凸包（详见Codevs 1298）很神奇的算法——先将各个点按坐标排序，然后像我们所知的那样一路左转，求出半边的凸包，然后反过来求另一半的凸包我以前正是因为总抱着想一步到位的想法，所以每次都跪得很惨（HansBug：事实上这次是我这辈子第一次A掉凸包题）然后别的没了，就是凸包的基本思想（顺便输出凸包周长C和面积S，好评如潮哦） 1type arr=array[0..100005] of longint;2var 3 i,j,k,l,m,n...
floyd算法是求所有点之间的最短路的，复杂度O（n3）代码简单是最大特色 1 #include<stdio.h>2 #include<string.h>3 4constint maxn=105;5constint INF=0x3f3f3f3f;6int ma[maxn][maxn],n;7 8 inline int min(int a,int b){return a<b?a:b;}9 inline int max(int a,int b){return a>b?a:b;} 10111213 memset(g,0x3f,sizeof(g)); 14for(int k=1;k<=n;++k){ 15for(int i=1;i<=n;++i){ 16for(int j=1;j<=n;++j){ 17 g[i][j...
题目传送门题目描述给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.字符串长度为n输入输出格式输入格式： 一行小写英文字符a,b,c...y,z组成的字符串S 输出格式： 一个整数表示答案 输入输出样例输入样例#1：aaa输出样例#1：3说明字符串长度len <= 11000000 分析：manacher算法模板，算法分析就不具体讲了，five20大佬讲的挺好的，可以参照一下他的博客。 Code： 1//It is made by HolseLee on...
并查集是由一个数组pre[]，和两个函数构成的，一个函数为find()函数，用于寻找前导点的，第二个函数是combine()用于合并路线的 1int findx(int x)2{3int a;4 a=x;5while(pre[a]!=a)///循环方法查找任意一个城市的前导点 6 {7 a=pre[a];8 }9/*if(pre[x]!=x)///递归方法查找任意一个城市的前导点 10 { 11 pre[x]=findx(pre[x]); 12 }*/13int i=x,j; 14while(i!=a) 15 { 16 j=pre[i];///记...
这两天学习了最大流，下面是ISAP算法模板：const int inf = 0x3fffffff; template <int N, int M> struct Isap {int top;int d[N], pre[N], cur[N], gap[N];struct Vertex{int head;} V[N];struct Edge{int v, next;int c, f;} E[M];void init(){memset(V, -1, sizeof(V));top = 0;}void add_edge(int u, int v, int c){E[top].v = v;E[top].c = c;E[top].f = 0;E[top].next = V[u].head;V[u].head = top++;}void add(int u,int v,...
1/* 2INPUT3 4 57 1261 2 2471 3 881 4 1592 5 6 103 5 7 113 6 3 124 7 4 135 7 9 146 5 2 156 7 3 166 4 5 177 2 3 18195 201 2 213 6 221 7 234 4 243 7 252627OUTPUT 28291 to 2 need 17 303 to 6 need 3 311 to 7 need 14 324 to 4 need 0 333 to 7 need 6 3435*/36 #include <stdio.h> 37 #include <stdlib.h> 38 #include <string.h> 39 #include <algorithm> 40usingnamespace std; 41constint inf=0x3f3f3f3f; 42int n,m,...
题目链接：https://www.luogu.org/problemnew/show/P1494题目描述作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你的任务便...