https://www.luogu.org/problemnew/show/P3805 就是一个马拉车算法的模板，这个算法总的来说不是很难，网上的博客都讲的挺好的，特此在这里写一个模板。#include<bits/stdc++.h> using namespace std; const int N=11000000+10; char s[N],snew[N*2]; int p[N*2]; int init() {int len=strlen(s);snew[0]='$';snew[1]='#';int j=2;for(int i=0;i<len;i++){snew[j++]=s[i];snew[j++]='#';}snew[j]='\0';return j; } int Manacher() ...
Cipolla LL ksm(LL k,LL n) {LL s=1;for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;return s; }namespace number {LL D;struct Z{LL x,y;Z(LL _x=0,LL _y=0){x=_x,y=_y;}};Z operator +(const Z &x,const Z &y) {return Z((x.x+y.x)%mo,(x.y+y.y)%mo);}Z operator -(const Z &x,const Z &y) {return Z((x.x-y.x+mo)%mo,(x.y-y.y+mo)%mo);}Z operator *(const Z &x,const Z &y) {return Z((x.x*y.x%mo+D*x.y%mo*y.y%mo+mo)%mo,(x.y*y.x%...
先给出题面：https://vjudge.net/problem/UVA-558 题意描述：给你含n个点以及m条边的图，让你判断在这个图中是否存在负权回路。 首先，我们来介绍什么是SPEA算法SPFA算法是求解单源最短路径问题的一种算法，由理查德贝尔曼（Richard Bellman） 和 莱斯特福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路...
1 #include<iostream>2 #include<cstdio>3 #include<cmath>4 #include<cstring>5 #include<cstdio>6 using namespace std;7 const int maxn = 1000000 + 10 ;8 char A[maxn],B[maxn];9 int p[maxn]; 10 int n,m; 11 void kmp() 12 { 13 int j(0); 14 for(int i=0;i<n;i++) 15 { 16 while(j>0 && B[j+1]!=A[i+1] ) j = p[j]; 17 if(B[j+1]==A[i+1]) j++; 18 if(j==m) 19 { 20 ...
模板—算法——动态点分治 Code:#include <cstdio> #include <algorithm> using namespace std; #define N 100010 int head[N],to[N<<1],val[N<<1],nxt[N<<1]; int mx[N],size[N],n,all,idx,root,fa[N]; bool vis[N]; void add(int a,int b,int c){nxt[++idx]=head[a],to[idx]=b,val[idx]=c,head[a]=idx;} void getroot(int p,int from) {mx[p]=0,size[p]=1;for(int i=head[p];i;i=nxt[i])if(to[i]!=from&&(!vis[to[i]])) getroot(...
题面 传送门 前置芝士 \(MTT\)，多项式多点求值 题解 这题法老当初好像讲过……而且他还说这种题目如果模数已经给定可以直接分段打表艹过去 以下是题解 我们设 \[F(x)=\prod_{i=0}^{s-1}(x+i)\] 分治\(FFT\)即可求出 然后我们用多点求值求出\(x=1,s+1,2s+1,...,s^2-s+1\)时的答案 这样的话可以计算出\((s^2)!\)，剩下没计算的部分直接暴力就是了 如果我们取\(s=\sqrt{n}\)，复杂度大概就是\(O(s\log^2s)\) 以下是吐槽 啊……模数任...
题意 题目链接 Sol 自己yy着写了一下Boruvka算法。 算法思想很简单，就是每次贪心的用两个联通块之间最小的边去合并。 复杂度\(O(n \log n)\)，然鹅没有Kruskal跑的快，但是好像在一类生成树问题上很有用 #include<bits/stdc++.h> #define Pair pair<int, int> #define fi first #define se second #define pb push_back #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1...
spfa 题目描述 给定n个点，m条边，计算从第x点到第y点的最短路径 输入格式 第一行为n和m，表示有n个点和m条边 接下来m行每行有a，b，c，表示从a到b间的长度为c 接下来1行x和y，表示计算从x到y间最短路的长度 输出格式 一个整数，表示x到y间最短路的长度，若不存在则输出-1 输入样例4 5 1 2 1 2 4 5 2 3 1 3 4 1 3 4 5 2 4 输出样例2 模板 1 #include<stdio.h>2 #include<string.h>3 #include<queue>4 using namespace std;5 ...
upd: 单向连边 \(a \rightarrow b\) ，显然应该在每一轮搜索中标记 \(b\) 集合的点。我误标记了 \(a\) ，这样就没有任何 \(a\) 类节点可以更改匹配了，完蛋。bool hungary(int p, int id){for (int i = Fs[p]; i; i = Nx[i]) {int t = Vs[i];if (Mk[t] == id)continue;Mk[t] = id;if (!Lnk[t] || hungary(Lnk[t], id)) {Lnk[t] = p;return 1;}}return 0;}int main(){ans = 0;for (i = 1; i <= n; ++i)ans += hungary(i);printf("%d...
玄学的pollard-rho 算法思想先咕着 #include<cstdio> #include<time.h> #include<cstdlib> #define re register #define in inline #define int long long in int ksm(int a,int b,int yyb) {int ans=1;while(b){if(b&1) ans=ans*a%yyb;a=a*a%yyb;b>>=1;}return ans; } in int gcd(int a,int b) {while(b^=a^=b^=a%=b);return a; } in int pr(int n) {re int x0=rand()%(n-1)+1,x1=x0,r,c=rand()%(n-1)+1,s=1;//设x0为环的起点, x1...
题目描述 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度 输入输出格式 输入格式： 一行小写英文字符a,b,c...y,z组成的字符串S 输出格式： 一个整数表示答案 #include<bits/stdc++.h> using namespace std; const int maxn=55000000+100; char s[maxn]; char str[maxn<<1]; int p[maxn<<1]; int n; void init() {str[0]=str[1]='#';for(int i=0;i<n;i++)str[i*2+2]=s[i],str[i*2+3]='#';n=n*2+2;str[n]=...
Java数据读入 读入一个整数： Scanner sc = new Scanner (System.in); int n = sc.nextInt(); 读入一个字符串 Scanner sc = new Scanner (System.in); String s=sc.next(); 读入一个浮点数 Scanner sc = new Scanner (System.in); double t = sc.nextDouble(); 读入一行 Scanner sc = new Scanner (System.in); String s = sc.nextLine(); 判断是否有下一个输入sc.hasNext()或sc.hasNextInt()或sc.hasNextDouble()或sc.h...
KM算法详解+模板 大佬讲的太好了！！！太好了！！！ http://www.cnblogs.com/wenruo/p/5264235.html KM算法用来求二分图最大权完美匹配。 本文配合该博文服用更佳：趣写算法系列之--匈牙利算法 本文没有给出KM算法的原理，只是模拟了一遍算法的过程。另，博主水平较差，发现问题欢迎指出，谢谢！！！！ 现在有N男N女，有些男生和女生之间互相有好感，我们将其好感程度定义为好感度，我们希望把他们两两配对，并且最后希望好感...
Description求关于\(x\)的同余方程 \(ax \equiv 1 \pmod {b}\) 的最小正整数解。 Input一行，包含两个正整数 \(a,b\)用一个空格隔开。 Output一个正整数 \(x_0\)即最小正整数解。输入数据保证一定有解。 Solution #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long a,b,x,y; void exgcd(long long a,long long b,long long &x,long long &y) {if (b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);l...
https://www.luogu.org/problemnew/show/P3805 回文串长度的奇偶性造成了对称轴的位置可能在某字符上，也可能在两个字符之间的空隙处 那么manacher对此的优化是在每两个字符中间插入另一个字符，如#。 用一个辅助数组r表示每个点能够扩展出的回文长度 我们先设置一个辅助变量maxright，表示已经触及到的最右边的字符 另外还要设置一个辅助变量mid，表示包含maxright的回文串的对称轴所在的位置 当i在maxright左边且在mid右边时： 设...