没有合适的资源?快使用搜索试试~ 我知道了~
Alone_L模板1
需积分: 0 0 下载量 93 浏览量
2022-08-04
00:20:08
上传
评论
收藏 385KB PDF 举报
温馨提示
试读
11页
Alone_L模板1
资源详情
资源评论
资源推荐
后缀数组模板(sa 数组从 1 到 N,rank 数组从 0 到 N-1,
height 数组从 2 到 N)。
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], wb[nMax], wv[nMax], wd[nMax];
int cmp(int *r, int a, int b, int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int *r, int n, int m) // 倍增
算法 r 为待匹配数组 n 为总长度 m 为字符范围
{
int i, j, p, *x = wa, *y = wb, *t;
for(i = 0; i < m; i ++) wd[i] = 0;
for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
for(i = 1; i < m; i ++) wd[i] += wd[i-1];
for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] =
i;
for(j = 1, p = 1; p < n; j *= 2, m = p)
{
for(p = 0, i = n-j; i < n; i ++) y[p ++]
= i;
for(i = 0; i < n; i ++) if(sa[i] >= j) y[p
++] = sa[i] - j;
for(i = 0; i < n; i ++) wv[i] = x[y[i]];
for(i = 0; i < m; i ++) wd[i] = 0;
for(i = 0; i < n; i ++) wd[wv[i]] ++;
for(i = 1; i < m; i ++) wd[i] += wd[i-1];
for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]]
= y[i];
for(t = x, x = y, y = t, p = 1, x[sa[0]]
= 0, i = 1; i < n; i ++)
{
x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ?
p - 1: p ++;
}
}
}
void calHeight(int *r, int n) // 求
height 数组。
{
int i, j, k = 0;
for(i = 1; i <= n; i ++) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i ++]] = k)
{
for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k]
== r[j+k]; k ++);
}
}
da( , n+1 , , )
Cal( , n )
RMQ 版本的后缀数组
int wa[maxn],wb[maxn],wv[maxn],Ws[maxn];
int cmp(int *r,int a,int b,int l)
{
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(const char *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0; i<m; i++) Ws[i]=0;
for(i=0; i<n; i++) Ws[x[i]=r[i]]++;
for(i=1; i<m; i++) Ws[i]+=Ws[i-1];
for(i=n-1; i>=0; i--) sa[--Ws[x[i]]]=i;
for(j=1,p=1; p<n; j*=2,m=p)
{
for(p=0,i=n-j; i<n; i++) y[p++]=i;
for(i=0; i<n; i++) if(sa[i]>=j)
y[p++]=sa[i]-j;
for(i=0; i<n; i++) wv[i]=x[y[i]];
for(i=0; i<m; i++) Ws[i]=0;
for(i=0; i<n; i++) Ws[wv[i]]++;
for(i=1; i<m; i++) Ws[i]+=Ws[i-1];
for(i=n-1; i>=0; i--)
sa[--Ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n;
i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
int sa[maxn],Rank[maxn],height[maxn];
//求 height 数组
void calheight(const char *r,int *sa,int n)
{
int i,j,k=0;
for(i=1; i<=n; i++) Rank[sa[i]]=i;
for(i=0; i<n; height[Rank[i++]]=k)
for(k?k--:0,j=sa[Rank[i]-1];
r[i+k]==r[j+k]; k++);
return;
}
int dp[maxn][20];
void Rmq_Init(int n)
{
int m=floor(log(n+0.0)/log(2.0));
for(int i=1; i<=n; i++) dp[i][0]=height[i];
for(int i=1; i<=m; i++)
{
for(int j=n; j; j--)
{
dp[j][i]=dp[j][i-1];
if(j+(1<<(i-1))<=n)
dp[j][i]=min(dp[j][i],dp[j+(1<<(i-1))][i-1]);
}
}
}
int Rmq_Query(int l,int r)
{
int a=Rank[l],b=Rank[r];
if(a>b) swap(a,b);
a++;
int m=floor(log(b-a+1.0)/log(2.0));
return min(dp[a][m],dp[b-(1<<m)+1][m]);
}
Rmq_Init( n );
Rmq_Query( l , r ) 区间最小值
Spfa(与差分约束)
//poj 3169
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "iostream"
#include "cmath"
#include "queue"
using namespace std;
int N,ML,MD;
struct NODE
{
int to,len,next;
}edge[200005];
int head[1005],vis[1005],dist[1005],in[1005];
void spfa()
{
int i,k;
for(i=0;i<=N;i++)
dist[i]=999999999,vis[i]=0,in[i]=0;
queue<int> Q;
while(!Q.empty()) Q.pop();
Q.push(1);
dist[1]=0;
in[1]++;
while(!Q.empty())
{
k=Q.front();
Q.pop();
vis[k]=0;
for(i=head[k];i!=-1;i=edge[i].next)
{
if(dist[edge[i].to] > edge[i].len +
dist[k])
{
dist[edge[i].to] = edge[i].len +
dist[k];
if(!vis[edge[i].to])
{
vis[edge[i].to]=1;
Q.push(edge[i].to);
in[edge[i].to]++;
if(in[edge[i].to] > N)
{
dist[N]=-1;
return;
}
}
}
}
}
if(dist[N] >= 999999999) dist[N]=-2;
}
-1 代表有负环,无解。-2 代表无限远~
//求最大距离 a - b < c
//求最小距离 a - b > c
KMP 函数
void get_p(int n) //得到预数组,KMP 主体和这结
构差不多,依题意改一下相关数组即可
{
int i,j=-1;
p[0]=-1;
for(i=1;i<n;i++)
{
while(j>-1 && temp[i]!=temp[j+1]) j=p[j];
if(temp[i] == temp[j+1]) j++;
p[i]=j;
}
}
球上两点距离公式
double calc(NODE a,NODE b) // x 为经度,y 为纬
度(都用弧度表示)
{
double
ans=(D/2)*acos(sin(a.x)*sin(b.x)+cos(a.x)*cos(b
.x)*cos(a.y-b.y));
return ans;
}
普通网络流
const int maxnode = 1000 + 5;
const int maxedge = 1000 + 5;
const int oo = 1000000000;
int node, src, dest, nedge;
int head[maxnode], point[maxedge], next1[maxedge],
flow[maxedge], capa[maxedge];//point[x]==y 表示第
x 条边连接 y,head,next 为邻接表,flow[x]表示 x 边
的动态值,capa[x]表示 x 边的初始值
int dist[maxnode], Q[maxnode],
work[maxnode];//dist[i]表示 i 点的等级
void init(int _node, int _src, int _dest){//初始
化,node 表示点的个数,src 表示起点,dest 表示终点
node = _node;
src = _src;
dest = _dest;
for (int i = 0; i < node; i++) head[i] = -1;
nedge = 0;
}
void addedge(int u, int v, int c1, int c2){//增
加一条 u 到 v 流量为 c1,v 到 u 流量为 c2 的两条边
point[nedge] = v, capa[nedge] = c1, flow[nedge]
= 0, next1[nedge] = head[u], head[u] = (nedge++);
point[nedge] = u, capa[nedge] = c2, flow[nedge]
= 0, next1[nedge] = head[v], head[v] = (nedge++);
}
bool dinic_bfs(){
memset(dist, 255, sizeof (dist));
dist[src] = 0;
int sizeQ = 0;
Q[sizeQ++] = src;
for (int cl = 0; cl < sizeQ; cl++)
for (int k = Q[cl], i = head[k]; i >= 0;
i = next1[i])
if (flow[i] < capa[i] && dist[point[i]]
< 0){
dist[point[i]] = dist[k] + 1;
Q[sizeQ++] = point[i];
}
return dist[dest] >= 0;
}
int dinic_dfs(int x, int exp){
if (x == dest) return exp;
for (int &i = work[x]; i >= 0; i = next1[i]){
int v = point[i], tmp;
if (flow[i] < capa[i] && dist[v] == dist[x]
+ 1 && (tmp = dinic_dfs(v, min(exp, capa[i] -
flow[i]))) > 0){
flow[i] += tmp;
flow[i^1] -= tmp;
return tmp;
}
}
return 0;
}
int dinic_flow(){
int result = 0;
while (dinic_bfs()){
for (int i = 0; i < node; i++) work[i] =
head[i];
while (1){
int delta = dinic_dfs(src, oo);
if (delta == 0) break;
result += delta;
}
}
return result;
}
//建图前,运行一遍 init();
//加边时,运行 addedge(a,b,c,0),表示点 a 到 b 流量
为 c 的边建成(注意点序号要从 0 开始)
//求解最大流运行 dinic_flow(),返回值即为答案
费用流
const int N = 1010;//点
const int M = 2 * 10010;//边
const int inf = 1000000000;
struct Node{//边,点 f 到点 t,流量为 c,费用为 w
int f, t, c, w;
}e[M];
int next1[M], point[N], dis[N], q[N], pre[N],
ne;//ne 为已添加的边数,next,point 为邻接表,dis
为花费,pre 为父亲节点
bool u[N];
void init(){
memset(point, -1, sizeof(point));
ne = 0;
}
剩余10页未读,继续阅读
武藏美-伊雯
- 粉丝: 22
- 资源: 352
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0