namespace Manacher{char str[maxn<<1];int radius[maxn<<1];int len;void bindString(char *s,int lenS){for(RG i=0;i<lenS;++i){str[i<<1]='#';str[i<<1|1]=s[i];radius[i<<1]=radius[i<<1|1]=0;}str[lenS<<1]='#';radius[lenS<<1]=0;len=lenS<<1|1;}int manacher(char *s,int lenS){bindString(s,lenS);//处理字符串int R=-1,C=-1;//R-最右回文右边界 C-最右回文右边界R的对称中心int Res=0;for(RG i=0;i<len;++i){radius[i]=(R...
算法简述 SPFA算法其实是bellman-ford算法的队列优化形式，不再是简简单单的进行n-1次松弛，而是使用队列，能使路径变短（dist[y] > dist[x] + 1）且不在队列里的节点才入队进行松弛。 SPFA算法与Dijkstra算法的堆优化实现形式差不多，都是使用邻接表的方式。 代码#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #define maxn 1000002 #define maxm 2000002 #define inf 0x3f3f3f3f using namespace st...
地址：https://ac.nowcoder.com/acm/contest/5338/B 解析：dfs超时了....其实对于每个可到达点来讲，它的来源是左和下，所以有：dp[i][j]=(dp[i+1][j]+dp[i][j-1]) 题目给出了快速读入模板：template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<0||c>9)if(c==-)flag=-1;res=c-0; while((c=getchar())>=0&&c<=9)res=res*10+c-0;res*=flag; } 完整代码：#include<iostream...
有一个序列\(a[1..n]\)，求最短的\(f[1..len]\)，使得： \(\forall i>len,\sum_{j=1}^{len} f[j]*a[i-j]=a[i]\) 假设已经求出了\(a[1..i-1]\)的最短递推式\(f\) 设\(?=a[i]-\sum_{j=1}^{len} f[j]*a[i-j]\) 当\(?=0\)时，显然\(f\)可以作为\(a[1..i]\)的递推式，continue 当\(?≠0\)时，我们想要找到一个递推式\(g\)，使得\(g\)代入\(i\)是1，\(g\)代入\(1..i-1\)是0，这样： 新的\(f=f+g*?\) 考虑之前有一次失配，递推式\(h0\)在\...
链表 单链表 一般做题中，采用数组模拟链表的方式，效率高 #include <iostream> using namespace std; const int N = 100010;//head表示头结点 //value[i]存放i的值 //ne[i]存放i的next指针 //idx表示当前已经用到了多少节点 int head, value[N], ne[N], idx;//初始化 void init(){head = -1;idx = 0; }//将x插入到头结点 void appendHead(int x){value[++idx] = x;ne[idx] = head;head = idx; } //在第k个节点后，插入x void ins...
Vector的常见用法详解Vector 翻译为向量，是长度可根据需要而自动改变的数组头文件 #include<vector> using namespace std;vector定义 单独一个vector：相当于一维数组name[SIZE] vector<typename> name;vector<int> name; // 基本类型 vector<double> name; vector<char> name; vector<node> name; // 结构体类型 vector<vector<int>> name; // STL容器， 这种的vector数组是两个维度都可变的vector数组：一维长度已经固定为...
题目链接：https://www.luogu.com.cn/problem/P3805#submit 题意：给定长为n的字符串，求最大回文子串的长度。(n<=1.1e7） 思路：manacher板子，时间复杂度O(n)。 AC code：/** manacher板子--求最大回文串的长度* O(n)*/ #include<cstdio> #include<algorithm> #include<cstring> using namespace std;const int maxn=11000005; int n,ans,p[maxn<<1]; char ss[maxn],s[maxn<<1];void init(){s[0]=~,s[1]=|;for(int i=0;i<n;++i)s...
https://www.luogu.com.cn/problem/P3805 #include <bits/stdc++.h> using namespace std; const int maxn = 1e7 + 1e6 + 5; char s[maxn * 2], str[maxn * 2]; int Len[maxn * 2], len; void getstr() {//重定义字符串int k = 0;str[k++] = @;//开头加个特殊字符防止越界for (int i = 0; i < len; i++) {str[k++] = #;str[k++] = s[i];}str[k++] = #;len = k;str[k] = 0;//字符串尾设置为0，防止越界 } int manacher() {int mx ...
KMP算法——六步搞定KMP 1.什么是KMP KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位大佬共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 模板匹配算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，提高时间效率。（空间换时间） 2.KMP与朴素模板匹配（Brute-Force） 暴力法Brute-Force 这个就是超级简单的逐一遍历比较。。。。 给定字串S,T, 将T与S的第一个长度与T一样的字串...
#include<stdio.h> #include<time.h> #include <stdlib.h>const int maxx=1e2+1; int a[maxx];void swap(int *x,int *y) {int z=*x;*x=*y;*y=z; } void init()//生成100个随机数,范围是0-99 {for(int i=0;i<100;i++) a[i]=rand()%100; } void zjcrsort()//直接插入排序 {int b[maxx];for(int i=0;i<100;i++) b[i]=a[i];//按照a数组去初始化b数组int cnt1=0,cnt2=0;//比较次数和移动次数for(int i=1;i<100;i++){int j=i;int temp=b...
交换函数template<typename SORTVALUE>void commonswap(SORTVALUE &exchange1, SORTVALUE &exchange2) {SORTVALUE value(exchange2);exchange2 = exchange1;exchange1 = value;}冒泡排序template<typename SORTVALUE>void BubbleSort(SORTVALUE sortBegin, SORTVALUE sortEnd){for (int i = 0; i < sortEnd - sortBegin - 1; ++i){for (int j = 0; j < sortEnd - sortBegin - 1 - i; ++j){if ((*(sortBegin + j) > *(sortBegin + j...
尺取算法 入门+模板+例题 博客推荐 尺取法原理及模板 https://blog.csdn.net/doubleguy/article/details/81265327 一些入门例题 https://blog.csdn.net/lxt_Lucia/article/details/81091597 模板 这里根据题目POJ 3061来具体实现。 题意是说给你一个有数字组成的序列，找出最短的子串（注意：子串是连续的，子序列可以不连续）,使得这个子串的和大于等于S,求子串的长度。 思路：使用尺取法来解决。 #include<cmath> #include<cstdi...
Manacher 算法 回文串专用算法manacher 人名，该算法的发明者。palindrome名词：回文。博客推荐 https://www.cnblogs.com/lykkk/p/10460087.html，比较简洁，代码清晰。 https://www.cnblogs.com/cloudplankroader/p/10988844.html， 一些细节的东西比较讲解比较细。 模板 //预处理函数，使得处理后的字符串长度为奇数，并且有一些比较好的性质 int init(char* s, char* ss) {int len=strlen(s);ss[0]='@'; ss[1]='#';int j=2;for(...
拓展KMP算法入门 博客推荐 扩展KMP算法, 图很形象，代码写的也很清晰，下面的模板就是出自该博客文章。 拓展KMP是求母串S长度为n和子串T长度为m,求S的每一个后缀子串与T的前缀子串匹配的最长长度。 代码实现 //求解模式串T的next数组，这个函数和下面的函数几乎相同 void getnext(string &T, int m, int[] next) {int a = 0, p = 0;next[0] = m; //T字符串自身和自身匹配for(int i=1; i<m; i++){if(i >= p || i + next[i - a] >= p...
1.快速排序（Acwing 785.快速排序） void quick_sort(int a[],int l,int r) {if(l>=r)return;int i=l-1,j=r+1,x=l+r>>1;//'+'的优先级高于'>>'移位运算符while(i<j){do i++;while(a[i]<x);do j--;while(a[j]>x);if(i<j) swap(a[i],a[j]);}quick_sort(q,l,j);quick_sort(q,j+1,r); }解析： 1.首先设立一个X将数组分开成两个数组； 2.设立两个指针i和j分别从首尾两端向彼此靠近，将小于X的数据都放在X的左边，大于X的数据放在X的右边...