基本实现：
int stack[100005],tot=0;
int top(){
if(!tot)return 0;//栈空
return stack[tot];
}
void pop(){
if(!tot)return;//非法
--tot;
return ;
}
void push(int x){
stack[++tot]=x;
return ;
}
bool empty(){
return tot>0;
}
int size(){
return tot;
}
表达式计算：
后缀表达式计算：
1.建立一个栈，逐步扫描1~n
1)如果遇到一个数，入栈
2)如果遇到运算符，就取出栈顶两个数进行计算，完事后结果放回栈顶
2.完成后栈顶即为答案
中缀表达式转后缀：
(1)如果遇到一个数，输出该数
(2)如果遇到左括号，入栈
(3)如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后将左括号出栈
(4)如果遇到运算符，只要*栈顶符号优先级不低于新符号*，就不断取出栈顶并输出
2.依次取出并输出栈内剩余符号即可
单调栈
思想：借助栈的先进后出结构完成单调性处理
详细的说:在一个栈中单调递减(递增)地存储一列决策，借助单调性及时处理掉不可能的决策
例题：直方图中最大的矩形
首先：如果前面的矩形高度单调递增，答案就是以每一个矩形的高度作为最终高度并延申至边界，对每一个高度取最大值即可
那么如果下一个进入决策序列的矩形比上一个矩形要矮，那么在决策序列中所以比该矩形更高的矩形高出它的那一部分的高度就没有了用处(即它就是以它的高度为答案的矩形的最大高度)
那么既然没用，那就删了ing
维护一个单调递增的矩形高度序列（宽度累加）我们设
a
i
a_i
ai表示第i个矩形高度，设
a
k
a_k
ak表示下一个矩形，设
s
t
a
c
k
stack
stack表示我们的单调栈(内存高度和宽度)
步骤
1.若
a
k
>
s
t
a
c
k
.
t
o
p
.
h
i
g
h
a_k>stack.top.high
ak>stack.top.high直接将
a
k
a_k
ak入栈，宽度为1
2.否则不断弹出栈顶累计宽度乘上栈顶高度更新答案，直到栈顶小于
a
k
a_k
ak
3.将一个宽度为累计宽度+1(
a
k
a_k
ak的宽度)，高度为
a
k
a_k
ak的矩形入栈
最后就得到了答案
思想的关键在于及时地排除不可能的决策/选项等，保持决策集合的单调性(秩序性)和高度有效性
C o d e Code Code:
while(cin>>n&&n){
ans=0; p=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
a[n+1]=0;
for(int i=1;i<=n+1;i++){
if(a[i]>s[p]) s[++p]=a[i],w[p]=1;
else{
int width=0;
while(s[p]>a[i]){
width+=w[p];
ans=max(ans,(long long)width*s[p]);
p--;
}
s[++p]=a[i],w[p]=width+1;
}
}
cout<
队列
一种先进先出的数据结构，C++的queue就是一个队列
基本实现：
int head,tail=1,a[100005];
void push(int val){
a[++head]=val;
}
void pop(){
tail++;
}
int top(){
return a[tail];
}
int size(){
return head-tail+1;
}
bool empty(){//队列是否为空
return tail>head;
}
单调队列
例：最大子序和：
问：给定一个长度为N的整数序列，从中找出一段不超过M的连续子序列，使得子序列和最大(
N
,
M
<
=
3
∗
1
0
5
N,M<=3*10^5
N,M<=3∗105)
解：设这个序列是A 设区间右端点为
i
i
i，当我们枚举
i
i
i时，问题就是找到一个左端点
j
j
j，使得
j
ϵ
[
i
−
m
,
i
−
1
]
jepsilon[i-m,i-1]
jϵ[i−m,i−1]并且
S
j
S_j
Sj最小 比较一下两个位置
j
,
k
j,k
j,k若
k
<
j
<
i
k 综上，可能成为最优选择的策略集合一定是一个下标位置递增，对应前缀和也递增的序列，用一个队列保存 随着
i
i
i的从前往后扫描，对于每一个
i
i
i，执行： 1.判断队头决策与
i
i
i的距离是否超出
M
M
M的范围，若超出则出队 2.此时队头就算右端点为i，左端点为j的最优解 3.不断删除队尾决策，直到队尾的
S
S
S值小于
S
i
S_i
Si,将
S
i
S_i
Si入队 这就是著名的单调队列算法，它的思想是在决策集合（队列）中及时排除一定不是最优解的选项 基础操作： 邻接表存图 思想：用一定的方法将需要处理的信息建立映射，与散列表类似，一般由hash函数与链表共同实现 Hash冲突：对每一个hash位置开一个链表，hash值相同的就给他放同一个链表上去 字符串HASH 1.取一固定值
P
P
P，将字符串看作
P
P
P进制数，并分配一个大于0的数值，代表每种字符 2.取一固定值
M
M
M, 求出该数对
M
M
M的余数为该字符串的
H
A
S
H
HASH
HASH值 一般取
P
=
131
P=131
P=131或
P
=
13331
P=13331
P=13331，用
u
n
s
i
g
n
e
d
l
o
n
g
l
o
n
g
unsigned long long
unsigned long long 来存这个数，这样就等于
M
=
2
64
M=2^{64}
M=264 基础操作：记字符串
S
S
S的
h
a
s
h
hash
hash值为
H
(
S
)
H(S)
H(S) 1.已知
H
(
S
)
H(S)
H(S)和
H
(
C
)
H(C)
H(C)，求
H
(
S
+
C
)
H(S+C)
H(S+C)
H
(
S
+
C
)
=
(
H
(
S
)
∗
P
s
i
z
e
(
C
)
+
H
(
C
)
)
m
o
d
M
H(S+C)=(H(S)*P^{size(C)}+H(C)) mod M
H(S+C)=(H(S)∗Psize(C)+H(C))modM 2.已知
H
(
S
+
T
)
H(S+T)
H(S+T)和
H
(
S
H(S
H(S)，求
H
(
T
)
H(T)
H(T)
H
(
T
)
=
(
H
(
S
+
T
)
−
H
(
S
)
∗
P
s
i
z
e
(
T
)
)
m
o
d
M
H(T)=(H(S+T)-H(S)*P^{size(T)}) mod M
H(T)=(H(S+T)−H(S)∗Psize(T))modM 例题：最长回文子串： 则需满足
H
(
S
[
1
k
−
1
]
)
=
R
(
S
[
k
+
1
M
]
)
H(S[1~k-1])=R(S[k+1~M])
H(S[1 k−1])=R(S[k+1 M]) 总复杂度
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n) 二维字符串hash 记
h
i
,
j
h_{i,j}
hi,j为矩形
(
1
,
1
,
i
,
j
)
(1,1,i,j)
(1,1,i,j)的hash值,
a
i
,
j
a_{i,j}
ai,j指矩形a中第i行第j列的字符 至于矩形
(
x
1
,
y
1
,
x
2
,
y
2
)
(x_1,y_1,x_2,y_2)
(x1,y1,x2,y2)的hash值可以这么得到：
a
s
k
(
x
1
,
y
1
,
x
2
,
y
2
)
=
h
[
x
2
]
[
y
2
]
−
h
[
x
2
]
[
y
1
−
1
]
∗
p
1
y
2
−
y
1
+
1
−
h
[
x
1
−
1
]
[
y
2
]
∗
p
2
x
2
−
x
1
+
1
+
h
[
x
1
−
1
]
[
y
1
−
1
]
∗
p
1
y
2
−
y
1
+
1
∗
p
2
x
2
−
x
1
+
1
ask(x_1,y_1,x_2,y_2)=h[x_2][y_2]-h[x_2][y_1-1]*p1^{y_2-y_1+1}-h[x_1-1][y_2]*p2^{x_2-x_1+1}+h[x_1-1][y_1-1]*p1^{y_2-y_1+1}*p2^{x_2-x_1+1}
ask(x1,y1,x2,y2)=h[x2][y2]−h[x2][y1−1]∗p1y2−y1+1−h[x1−1][y2]∗p2x2−x1+1+h[x1−1][y1−1]∗p1y2−y1+1∗p2x2−x1+1 例题： 话不多说，二维hash裸题 作用：在线性时间内找出字符串A是否是B的子串并且求出A在B中每次出现的位置
C
o
d
e
Code
Code 进一步的，求循环元： 据定理，得： 拓展，如果S不存在一个可以被整除的循环元，那么
n
−
n
e
x
t
[
n
]
n-next[n]
n−next[n]就是这个不整除循环元的长度 字符串的最小表示 求法： 定义(以大根堆为例): 用处：1.辅助各类贪心算法 2.求解最值问题
计算区间和问题，一般用前缀和，记
S
i
=
∑
k
=
1
i
A
k
S_i=sum_{k=1}^iA_k
Si=∑k=1iAk,则问题变为求一对
x
,
y
(
x
<
y
)
x,y(xint l=1,r=1;
q[1]=0;
for(int i=1;i<=n;i++){
while(l<=r&&q[l]
struct Node{
int val;
int prev,next;
}node[SIZE];
int head,tail,tot;
void init(){
tot=2;
head=1,tail=2;
node[head].next=tail;
node[tail].prev=head;
}
int insert(int p,int val){
int q=++tot;
node[q].val=val;
node[node[p].next].prev=q;
node[q].next=node[p].next;
node[p].next=q;
node[q].prev=p;
}
void remove(int p){
node[node[p].prev].next=node[p].next;
node[node[.].next].prev=node[p].prev;
}
void clear(){
memset(node,0,sizeof node);
head=tail=tot=0;
}
//加入有向边u->v,边权为z
void add(int u,int v,int z){
node[++tot].v=v,node[tot].val=z,node[tot].next=head[u],head[u]=tot;
}
//访问从u出发的所有边
for(int i=head[u];i;i=node[i].next){
//此时node[i]就是边u->node[i].v
}
HASH
流程：
这样，我们就可以在
O
(
n
)
O(n)
O(n)的时间内预处理出字符串的所有前缀的Hash值，并且在
O
(
1
)
O(1)
O(1)时间内查找它任意子串的值
题目：给定一个串
S
S
S，求TA的最长回文子串长度
解：
将S正着倒着都做一次
h
a
s
h
hash
hash，记正向
h
a
s
h
hash
hash为
H
H
H，逆向
h
a
s
h
hash
hash为
R
R
R
分回文串奇偶讨论：
1.奇回文串
S
[
1
M
]
,
M
=
2
k
−
1
S[1~M],M=2k-1
S[1 M],M=2k−1(k是整数),
S
[
k
]
S[k]
S[k]即为串的中点
2.偶回文串
S
[
1
M
]
S[1~M]
S[1 M]，
M
=
2
k
M=2k
M=2k,
则需满足
H
(
S
[
1
k
]
)
=
R
(
S
[
k
+
1
M
]
)
H(S[1~k])=R(S[k+1~M])
H(S[1 k])=R(S[k+1 M])
于是乎，我们可以枚举最长回文子串的中心位置
i
i
i
1.寻找一个最大的整数
q
q
q，使得
H
(
S
[
i
−
q
i
]
)
=
R
(
S
[
i
i
+
q
]
)
H(S[i-q~i])=R(S[i~i+q])
H(S[i−q i])=R(S[i i+q])且
q
<
i
q 整个串长度为
2
q
+
1
2q+1
2q+1,
2.寻找一个最大的整数
p
p
p，使得
H
(
S
[
i
−
p
i
−
1
]
)
=
R
(
S
[
i
i
+
p
−
1
]
)
H(S[i-p~i-1])=R(S[i~i+p-1])
H(S[i−p i−1])=R(S[i i+p−1])
a
n
s
=
m
a
x
(
a
n
s
,
m
a
x
(
2
∗
p
,
2
∗
q
+
1
)
)
ans=max(ans,max(2*p,2*q+1))
ans=max(ans,max(2∗p,2∗q+1))
由回文串的性质，我们可以对p,q进行二分答案
Code://Author:XuHt
#include
具体思想：将矩阵的行先hash成一个值，然后再对所有列的这个值再hash一次unsigned h[size1][size2];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
h[i][j]=h[i][j-1]*p1+(int)a[i][j];//这里进行行hash
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
h[i][j]=h[i-1][j]*p2+h[i][j];//这里进行列hash,采用不同的p值以免被卡
}
}
给定一个 M 行 N 列的 01 矩阵（只包含数字 0 或 1 的矩阵），再执行 Q 次询问，每次询问给出一个 A 行 B 列的 01 矩阵，求该矩阵是否在原矩阵中出现过。
输入格式
第一行四个整数 M,N,A,B。
接下来一个 M 行 N 列的 01 矩阵，数字之间没有空格。
接下来一个整数 Q。
接下来 Q 个 A 行 B 列的 01 矩阵，数字之间没有空格。
输出格式
对于每个询问，输出 1 表示出现过，0 表示没有出现过。
数据范围
A≤100，M,N,B≤1000，Q≤1000
C
o
d
e
Code
Code:#include
KMP
步骤：
1.对A进行自我匹配，求出数组
n
e
x
t
next
next，其中
n
e
x
t
i
=
max
j
next_i=max{j}
nexti=maxj，其中
j
<
i
j 2.对A,B进行匹配：求出数组
f
f
f,其中
f
[
i
]
=
m
a
x
j
f[i]=max{j}
f[i]=maxj,其中
i
≥
j
igeq j
i≥j且B[i-j+1i]=A[1j]next[1]=0;
for(int i=2,j=0;i<=n;i++){
while(j>0 && a[i]!=a[j+1])j=next[j];
if(a[j+1]==a[i])j++;
next[i]=j;
}//求next
for(int i=1;j=0;i<=m;i++){
while(j>0 && (j==n||b[i]!=a[j+1]))j=next[j];
if(b[i]==a[j+1])j++;
f[i]=j;
//if(f[i]==n)匹配成功
}
定义：若一个字符串S是由一个字符串T重复K次形成的，那么T是S的循环元，使K最大的循环元叫做字符串的最小循环元，此时K是最大循环次数
定理：
S[1~i]具有长度为len
并且不存在更大的
n
e
x
t
[
i
]
next[i]
next[i]满足这个条件
若
i
−
n
e
x
t
[
i
]
i-next[i]
i−next[i]能整除
i
i
i，S[1~i]的最小循环元就是S[1至i-next[i]],最大循环次数就是
i
/
(
i
−
n
e
x
t
[
i
]
)
i/(i-next[i])
i/(i−next[i])
定义：给定一个字符串S[1至n]，若我们不断将它的最后一个字符放在开头，最终会得到n个字符串，则称这n个字符串是循环同构的，其中字典序最小的一个就称为字符串S的最小表示
设
B
[
i
]
B[i]
B[i]是S的第i个循环同构串,
S
S
=
S
+
S
SS=S+S
SS=S+S,显然
B
[
i
]
B[i]
B[i]=
S
S
[
i
,
i
+
n
−
1
]
SS[i,i+n-1]
SS[i,i+n−1]
1.初始化
i
=
1
,
j
=
2
i=1,j=2
i=1,j=2
2.直接从前向后扫描，比较
B
[
i
]
a
n
d
B
[
j
]
B[i] and B[j]
B[i]andB[j]是否相等
（1）若全相等，则S有更小的循环元，，并且该循环元已经扫描完成，此时
B
[
m
i
n
(
i
,
j
)
]
B[min(i,j)]
B[min(i,j)]即为最小表示
（2）在
i
+
k
i+k
i+k和
b
+
k
b+k
b+k处发现不等
1）若
S
S
[
i
+
k
]
>
S
S
[
j
+
k
]
SS[i+k]>SS[j+k]
SS[i+k]>SS[j+k]，令
i
=
i
+
k
+
1
i=i+k+1
i=i+k+1,若此时
i
=
j
i=j
i=j,再令
i
=
i
+
1
i=i+1
i=i+1
2）若
S
S
[
i
+
k
]
<
S
S
[
j
+
k
]
SS[i+k]int n=strlen(s+1);
for(int i=1;i<=n;i++)s[n+i]=s[i];
int i=1,j=2,k;
while(i<=n&&j<=n){
for(k=0;k
堆
1.是一颗完美二叉树
2.树根的权值最大
3.父亲节点的权值永远大于子节点
基本操作：(以大根堆为例)int heap[SIZE],n;
void up(int p){ //向上调整，保持堆性质,O(logn)
while(p>1){
if(heap[p]>head[p/2]){
swap(heap[p],heap[p/2]);
}
else break;
}
}
void insert(int val){//插入 O(logn)
heap[++n]=val;
up(n);
}
int gettop(){return heap[1];}//返回堆顶权值，复杂度O(1)
void down(int p){ //向下调整，O(logn)
int s=p*2;//p的左子节点
while(s<=n){
if(s
