没有合适的资源?快使用搜索试试~ 我知道了~
首页kuangbin模板(2014-5)
kuangbin模板(2014-5)
5星 · 超过95%的资源 需积分: 0 286 下载量 146 浏览量
更新于2023-03-16
评论 2
收藏 1.81MB PDF 举报
kuangbin模板(2014年5月更新的),雷锋不要积分~~~~凑齐50字~~~~~~~~~~~~~~~~~~
资源详情
资源评论
资源推荐
上海大学 ACM 模板 by kuangbin
1 / 173 ACM 模板 kuangbin
字符串处理 ............................................................................................................................... 2
1、KMP 算法 .................................................................................................................... 2
2、扩展 KMP .................................................................................................................... 5
3、Manacher 最长回文子串 ........................................................................................... 6
4、AC 自动机 ................................................................................................................... 7
5、后缀数组 ..................................................................................................................... 9
6、后缀自动机 ............................................................................................................... 13
7、字符串 HASH............................................................................................................. 15
数学......................................................................................................................................... 17
1、素数 ........................................................................................................................... 17
2、素数筛选和合数分解 ............................................................................................... 19
3、扩展欧几里得算法(求 ax+by=gcd 的解以及逆元素) ........................................ 20
4、求逆元 ....................................................................................................................... 20
5、模线性方程组 ........................................................................................................... 20
6、随机素数测试和大数分解(POJ 1811) ..................................................................... 21
7、欧拉函数 ................................................................................................................... 24
8、高斯消元(浮点数) ............................................................................................... 25
9、FFT ............................................................................................................................. 26
10、高斯消元法求方程组的解 ..................................................................................... 29
11、 整数拆分 ............................................................................................................... 34
12、求 A^B 的约数之和对 MOD 取模 .......................................................................... 36
13、莫比乌斯反演 ......................................................................................................... 37
14、Baby-Step Giant-Step .............................................................................................. 39
15、自适应 simpson 积分 ............................................................................................. 40
相关公式 ......................................................................................................................... 40
数据结构 ................................................................................................................................. 42
1、划分树 ....................................................................................................................... 42
2、RMQ .......................................................................................................................... 43
3、树链剖分 ................................................................................................................... 45
4、伸展树(splay tree) ............................................................................................... 50
5、动态树 ....................................................................................................................... 55
6、主席树 ....................................................................................................................... 60
7、Treap.......................................................................................................................... 70
图论......................................................................................................................................... 75
1、最短路 ....................................................................................................................... 75
2、最小生成树 ............................................................................................................... 79
3、次小生成树 ............................................................................................................... 80
4、有向图的强连通分量 ............................................................................................... 81
5、图的割点、桥和双连通分支的基本概念 ............................................................... 84
6、割点与桥 ................................................................................................................... 85
7、边双连通分支 ........................................................................................................... 88
8、点双连通分支 ........................................................................................................... 90
9、最小树形图 ............................................................................................................... 93
10、二分图匹配 ............................................................................................................. 95
11、生成树计数 ............................................................................................................. 98
11、二分图多重匹配 ................................................................................................... 101
12、KM 算法(二分图最大权匹配) ........................................................................ 102
13、最大流 ................................................................................................................... 103
14、最小费用最大流 ................................................................................................... 109
15、2-SAT ...................................................................................................................... 110
16、曼哈顿最小生成树 ............................................................................................... 114
17、一般图匹配带花树 ............................................................................................... 117
18、LCA ........................................................................................................................ 120
19、欧拉路 ................................................................................................................... 126
计算几何 ............................................................................................................................... 133
1、基本函数 ................................................................................................................. 133
上海大学 ACM 模板 by kuangbin
2 / 173 ACM 模板 kuangbin
2、凸包 ......................................................................................................................... 138
3、平面最近点对(HDU 1007) ................................................................................ 139
4、旋转卡壳 ................................................................................................................. 140
5、半平面交 ................................................................................................................. 146
6、三点求圆心坐标(三角形外心) ......................................................................... 149
7、求两圆相交的面积 ................................................................................................. 150
8、Pick 公式 ................................................................................................................. 150
动态规划 ............................................................................................................................... 150
1、最长上升子序列 O(nlogn) ...................................................................................... 150
搜索....................................................................................................................................... 151
1、Dancing Links ........................................................................................................... 151
其他....................................................................................................................................... 156
1、高精度 ..................................................................................................................... 156
2、完全高精度 ............................................................................................................. 158
3、strtok 和 sscanf 结合输入 ...................................................................................... 163
4、解决爆栈,手动加栈 ............................................................................................. 163
5、STL ........................................................................................................................... 163
6、输入输出外挂 ......................................................................................................... 165
7、莫队算法 ................................................................................................................. 166
8、VIM 配置 ................................................................................................................. 172
字符串处理
1、KMP 算法
/*
* next[]的含义:x[i-next[i]...i-1]=x[0...next[i]-1]
* next[i]为满足x[i-z...i-1]=x[0...z-1]的最大z值(就是x的自身匹配)
*/
void kmp_pre(char x[],int m,int next[])
{
int i,j;
j=next[0]=-1;
i=0;
while(i<m)
{
while(-1!=j && x[i]!=x[j])j=next[j];
next[++i]=++j;
}
}
/*
* kmpNext[]的意思:next'[i]=next[next[...[next[i]]]] (直到next'[i]<0或者
x[next'[i]]!=x[i])
* 这样的预处理可以快一些
*/
void preKMP(char x[],int m,int kmpNext[])
{
int i,j;
j=kmpNext[0]=-1;
i=0;
while(i<m)
{
上海大学 ACM 模板 by kuangbin
3 / 173 ACM 模板 kuangbin
while(-1!=j && x[i]!=x[j])j=kmpNext[j];
if(x[++i]==x[++j])kmpNext[i]=kmpNext[j];
else kmpNext[i]=j;
}
}
/*
* 返回x在y中出现的次数,可以重叠
*/
int next[10010];
int KMP_Count(char x[],int m,char y[],int n)
{//x是模式串,y是主串
int i,j;
int ans=0;
//preKMP(x,m,next);
kmp_pre(x,m,next);
i=j=0;
while(i<n)
{
while(-1!=j && y[i]!=x[j])j=next[j];
i++;j++;
if(j>=m)
{
ans++;
j=next[j];
}
}
return ans;
}
经典题目:POJ 3167
/*
* POJ 3167 Cow Patterns
* 模式串可以浮动的模式匹配问题
* 给出模式串的相对大小,需要找出模式串匹配次数和位置
* 比如说模式串:1,4,4,2,3,1 而主串:5,6,2,10,10,7,3,2,9
* 那么2,10,10,7,3,2就是匹配的
*
* 统计比当前数小,和于当前数相等的,然后进行kmp
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=100010;
const int MAXM=25010;
int a[MAXN];
int b[MAXN];
int n,m,s;
int as[MAXN][30];
int bs[MAXM][30];
void init()
{
for(int i=0;i<n;i++)
{
上海大学 ACM 模板 by kuangbin
4 / 173 ACM 模板 kuangbin
if(i==0)
{
for(int j=1;j<=25;j++)as[i][j]=0;
}
else
{
for(int j=1;j<=25;j++)as[i][j]=as[i-1][j];
}
as[i][a[i]]++;
}
for(int i=0;i<m;i++)
{
if(i==0)
{
for(int j=1;j<=25;j++)bs[i][j]=0;
}
else
{
for(int j=1;j<=25;j++)bs[i][j]=bs[i-1][j];
}
bs[i][b[i]]++;
}
}
int next[MAXM];
void kmp_pre()
{
int i,j;
j=next[0]=-1;
i=0;
while(i<m)
{
int t11=0,t12=0,t21=0,t22=0;
for(int k=1;k<b[i];k++)
{
if(i-j>0)t11+=bs[i][k]-bs[i-j-1][k];
else t11+=bs[i][k];
}
if(i-j>0)t12=bs[i][b[i]]-bs[i-j-1][b[i]];
else t12=bs[i][b[i]];
for(int k=1;k<b[j];k++)
{
t21+=bs[j][k];
}
t22=bs[j][b[j]];
if(j==-1 || (t11==t21&&t12==t22))
{
next[++i]=++j;
}
else j=next[j];
}
}
vector<int>ans;
void kmp()
{
ans.clear();
int i,j;
kmp_pre();
上海大学 ACM 模板 by kuangbin
5 / 173 ACM 模板 kuangbin
i=j=0;
while(i<n)
{
int t11=0,t12=0,t21=0,t22=0;
for(int k=1;k<a[i];k++)
{
if(i-j>0)t11+=as[i][k]-as[i-j-1][k];
else t11+=as[i][k];
}
if(i-j>0)t12=as[i][a[i]]-as[i-j-1][a[i]];
else t12=as[i][a[i]];
for(int k=1;k<b[j];k++)
{
t21+=bs[j][k];
}
t22=bs[j][b[j]];
if(j==-1 || (t11==t21&&t12==t22))
{
i++;j++;
if(j>=m)
{
ans.push_back(i-m+1);
j=next[j];
}
}
else j=next[j];
}
}
int main()
{
while(scanf("%d%d%d",&n,&m,&s)==3)
{
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<m;i++)
{
scanf("%d",&b[i]);
}
init();
kmp();
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)
printf("%d\n",ans[i]);
}
return 0;
}
2、扩展 KMP
/*
* 扩展KMP算法
*/
//next[i]:x[i...m-1]与x[0...m-1]的最长公共前缀
剩余172页未读,继续阅读
角落的秋天
- 粉丝: 171
- 资源: 8
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1