该笔记目前直接复制的之前的笔记，还未调整格式。页面格式、内容、链接等可能存在混乱错误……
线性筛素数
-
用途：对一定范围$n$内的数，构造素数表。
-
注意点：
ifNot_Prime数组范围为数据大小的范围，并不是个数。
#define MAX_N 100000000 + 5
bool IfNot_Prime[MAX_N]; //0---素数 1---不是素数
int Prime[MAX_N], PNum; //PNum：记录范围内有多少个素数
void Init(int N)
{
for (register int Top=2; Top<=N/2+1; Top++)
{
if (!IfNot_Prime[Top]) Prime[++PNum]=Top;
for (register int C=1; C<=PNum && Top*Prime[C] <= MAX; C++)
{
IfNot_Prime[Top*Prime[C]]=1;
if (Top % Prime[C] == 0) break;
}
}
}
- 解释：
Prime内存放$1\sim n$内的所有素数。
ifNot_Prime内存放否以具体的数是否为素数。
快速幂
long long q_pow(long long base, long long idx) //base 底数、index 指数
{
long long answer = 1;
while (idx)
{
if (idx & 1)
answer = answer * base % MOD; //带模的运算
base = base * base % MOD;
idx >>= 1;
}
return answer;
}
//使用例：
{
q_pow(3,12); //3^12
}
拓展——矩阵快速幂
- 用途：矩阵DP
//long long注意！……
#include <bits/stdc++.h>
#define matrix_MAX 100
#define MOD 1000000007
using namespace std;
struct typeMatrix
{
long long mat[matrix_MAX + 1][matrix_MAX + 1] = {};
int x, y; //x——行，y——列
typeMatrix(int x, int y) : x(x), y(y) {}
inline typeMatrix operator*(const typeMatrix &a) const //矩阵乘法实现
{
typeMatrix res(x, a.y);
for (int i = 1; i <= x; i++) //矩阵a(x1,y1);b(x2,y2)，
//新矩阵为res(x1,y2)，做y1(或x2)次乘法累加
for (int j = 1; j <= a.y; j++)
for (int k = 1; k <= y; k++)
res.mat[i][j] = (res.mat[i][j] + mat[i][k] * a.mat[k][j]) % MOD; //就矩阵乘法
return res;
}
void initPowAns(int size)
{
for (int i = 1; i <= size; i++)
mat[i][i] = 1;
//注意标准快速幂中初始化为令ans=1，换成矩阵后初始化为令主对角线为1……
}
inline typeMatrix operator^(long long power) const //快速幂实现
{
typeMatrix ans(y, y), base = *this;
ans.initPowAns(y);
while (power)
{
if (power & 1)
ans = ans * base;
base = base * base;
power >>= 1;
}
return ans;
}
};
int main()
{
long long n,k;
scanf("%lld%lld", &n, &k);
typeMatrix Matrix(n,n); //定义矩阵
/*读入矩阵*/
typeMatrix ans = Matrix ^ k;
/*输出结果矩阵*/
}
GCD&EXGCD
LL gcd(LL a, LL b) //递归式gcd
{
return b ? gcd(b, b % a) : a;
}
LL gcd_iteration(LL a, LL b) //迭代式GCD
{
while (b ^= a ^= b ^= a %= b);
return a;
}
LL Exgcd_iteration(LL a, LL b, LL &x, LL &y) //迭代式EXGCD
{
x = 1, y = 0; //初矩阵：1 0
int x1 = 0, y1 = 1; // 0 1
while (b)
{
int d = a / b;
tie(x, x1) = make_tuple(x1, x - d * x1); //矩阵乘法
tie(y, y1) = make_tuple(y1, y - d * y1);
tie(a, b) = make_tuple(b, a - d * b); //迭代gcd()
}
return a;
}
并查集
并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。
- 用途：
- 查找（Find）：确定某个元素处于哪个子集。
- 合并（Union）：将两个子集合并成一个集合。
struct typeUnionFind
{
int num, father[N], rank[N]; //这里rank作用是记录节点深度（真实为深度-1），采用了按秩合并的优化
void init(int n)
{
num=n;
for (int i = 1; i <= num; i++)
father[i] = i;
}
inline int find(int node) //查询操作
{
return father[node] == node ? node : (father[node] = find(father[node]));
//这里使用了路径压缩优化
}
inline void merge(int node1, int node2) //合并操作
{
int father1 = find(node1), father2 = find(node2);
if (rank[father1] < rank[father2])
father[father1] = father2;
else if (rank[father1] > rank[father2])
father[father2] = father1;
else if (father1 != father2)
father[father1] = father2, rank[father2]++;
//如果深度一样且父节点不一样（不为一棵树），合并后新树深度会加一
}
} UnionFind;
//使用例：
{
//初始化
UnionFind.init(n);
UnionFind.merge(1,2); //合并1，2这两个子集。
UnionFind.find(3); //查询3这个元素处于哪个子集。
}
ST表
用于处理区间最值询问问题。
#define MAX_N 100005
#define Work max //根据题目要求选择Work方式（最大还是最小）
int Log[MAX_N], //Log表
Num[MAX_N], //存放原本数据的数组
F[MAX_N][30], //ST表
n;
void InitLog() //初始化Log数组
{
Log[1] = 0, Log[2] = 1;
for (int i = 3; i <= n; i++)
Log[i] = Log[i / 2] + 1;
}
void Init()
{
InitLog();
for (int i = 1; i <= n; i++)
F[i][0] = Num[i]; //刚开始f[n][0],即长度为1的序列中最小的就是它本身。
//2开始，log2=1;log3=1;log4=2;log5=2;log6=2;log7=2;log8=3;
for (int i = 2; i <= n; i++)
{
F[i][1] = Work(F[i][0], F[i - 1][0]);//这里特殊处理1，因为2^(1-1)=1,而2<<(1-1)=2
for (int j = 2; j <= Log[i]; j++)
F[i][j] = Work(F[i][j - 1], F[i - (1 << (j - 1))][j - 1]);
}
}
int Find(int l, int r)
{
int k = Log[r - l + 1];
return Work(F[l + (1 << k) - 1][k], F[r][k]);
}
//使用例
{
//初始化：先读入数据个数n，数组。
Init();
cout << Find(l, r); //输出[l,r]间的最值
}
线段树
直接放模板。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int L = 0, R = 1;
struct Message
{ //节点维护的信息
long long sum, len, add, mul; //区间和 区间长度 区间lazy的加法 区间lazy的乘法
/*
ans = ans*mul + add
*/
Message()
{ //初始化函数
sum = 0;
add = 0;
len = 0;
mul = 1;
}
Message(long long xsum, long long xlen, long long xadd, long long xmul)
{ //初始化函数
sum = xsum;
len = xlen;
add = xadd;
mul = xmul;
}
Message operator+(const Message &b)
{ //定义 a+b
Message p(sum + b.sum, len + b.len, 0, 1);
return p;
}
/*
(ans * mul + add) * famul + faadd
*/
void modify(Message fa)
{ //父亲的信息为fa ， 父亲pushdown下传
mul = mul * fa.mul;
add = add * fa.mul + fa.add;
sum = sum * fa.mul + fa.add;
}
};
struct SegmentTree
{
int l, r; //当前管理区间 [l,r]
int son[2]; //左儿子为 son[0] 右儿子为 son[1]
Message x;
} node[N * 2];
void pushdown(int k)
{ //下传标记
if (node[k].x.add != 0)
{
node[node[k].son[L]].x.modify(node[k].x);
node[node[k].son[R]].x.modify(node[k].x);
node[k].x.add = 0;
}
}
void update(int k)
{ //更新节点k
node[k].x = node[node[k].son[L]].x + node[node[k].son[R]].x;
}
int root, ini[N], cnt; //cnt 当前已经有了多少个节点
//假设数组初始时为ini
void buildTree(int &k, int l, int r)
{ //初始化一个管理[l,r]的节点 ， 下标为k
k = ++cnt;
node[k].l = l;
node[k].r = r;
node[k].x.len = (r - l + 1); //初始化[l,r] //k = cnt+1; cnt++;
if (l == r)//没有儿子了
{
node[k].x.sum = ini[l];
}
else //我是爸爸
{
int mid = (node[k].l + node[k].r) / 2; //儿子的左右分界
buildTree(node[k].son[L], l, mid); //调用完后 左右儿子下表就可以被储存
buildTree(node[k].son[R], mid + 1, r);
update(k);
}
}
Message work(int k, int ql, int qr, Message y)
{ //修改 [ql,qr] 顺带查询[ql,qr]
if (ql <= node[k].l && node[k].r <= qr)
{
node[k].x.modify(y);
return node[k].x;
}
else if (ql > node[k].r || qr < node[k].l)
return 空;
else
{
Message p;
pushdown(k);
p = work(node[k].son[L], ql, mid, y) + work(node[k].son[R], mid + 1, qr, y);
update(k);
return p;
}
}
int n, m;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &ini[i]);
buildTree(root, 1, n);
Message ans;
//区间[l,r] += val
int l, r, val;
Message y;
y.add = val;
work(root, l, r, y);
//区间[l,r] *= val
Message y;
y.mul = val;
work(root, l, r, y);
//查询区间[l,r]
y.add = y.len = y.sum = 0;
ans = work(root, l, r, y);
cout << ans.sum << endl;
}
逆序对
用归并排序。
其中包含了对全排列的hash。
#define MAX_LENGTH 5000000
long long inver[MAX_LENGTH]; //记录每位的逆序对
template <typename T>
long long sortMerge_inv(T *rawArray, int indexLeft, int indexRight) //求逆序对版
{
vector<T> tmpArray;
long long sum = 0;
if (indexLeft == indexRight)
return 0;
int mid = (indexLeft + indexRight) >> 1,
indexTmpArray = 0,
indexLeftMerge = indexLeft,
indexRightMerge = mid + 1;
sum += sortMerge_inv(rawArray, indexLeft, mid);
sum += sortMerge_inv(rawArray, mid + 1, indexRight);
while (indexLeftMerge <= mid || indexRightMerge <= indexRight)
{
if (indexLeftMerge <= mid && (rawArray[indexLeftMerge] <= rawArray[indexRightMerge]
|| indexRightMerge > indexRight))
tmpArray.push_back(rawArray[indexLeftMerge++]);
else
{
tmpArray.push_back(rawArray[indexRightMerge++]), sum += mid - indexLeftMerge + 1;
for (ALL(i, indexLeftMerge, mid)) //这里为注意点：为左部分的剩余所有数的逆序对个数++
inver[i]++;
}
}
for (ALL(i, indexLeft, indexRight))
rawArray[i] = tmpArray[indexTmpArray++];
return sum;
}
int hash_index[10];
long long fact(int num)
{
long long ans = 1;
for (ALL(i, 1, num))
ans *= i;
return ans;
}
void hash_init(int len)
{
for (ALL(i, 1, len))
hash_index[i] = len - i;
}
template <typename T>
//求全排列的Hash
long long sortMerge_hash(T *rawArray, int indexLeft, int indexRight, const int &length)
{
if (indexLeft == indexRight)
return 0;
vector<T> tmpArray;
vector<T> tmpFact; //用来swap后对位权的swap
long long hashArr = 0;
int mid = (indexLeft + indexRight) >> 1,
indexTmpArray = 0,
indexLeftMerge = indexLeft,
indexRightMerge = mid + 1;
hashArr += sortMerge_hash(rawArray, indexLeft, mid, length);
hashArr += sortMerge_hash(rawArray, mid + 1, indexRight, length);
while (indexLeftMerge <= mid || indexRightMerge <= indexRight)
{
if (indexLeftMerge <= mid && (rawArray[indexLeftMerge] <= rawArray[indexRightMerge]
|| indexRightMerge > indexRight))
tmpArray.push_back(rawArray[indexLeftMerge++]),
tmpFact.push_back(hash_index[indexLeftMerge - 1]);
else
{
tmpArray.push_back(rawArray[indexRightMerge++]),
tmpFact.push_back(hash_index[indexRightMerge - 1]);
for (ALL(i, indexLeftMerge, mid))
{
hashArr += fact(hash_index[i]); //hash计算
}
}
}
for (ALL(i, indexLeft, indexRight))
rawArray[i] = tmpArray[indexTmpArray++],
hash_index[i] = tmpFact[indexTmpArray - 1]; //补了交换权重【这样可以准确算出每一位的逆序对
return hashArr;
}
//使用例
int arr[MAX_LENGTH], arr_hash[MAX_LENGTH];
{
int n;
scanf("%d", &n);
for (ALL(i, 1, n))
scanf("%d", &arr[i]), arr_hash[i] = arr[i];
printf("Each inversion:\n"); //输出每一位的逆序对个数
cout << setw(7) << "---Top:";
for (ALL(i, 1, n))
cout << setw(7) << i;
cout << endl
<< setw(7) << "---Num:";
for (ALL(i, 1, n))
cout << setw(7) << arr[i];
cout << endl
<< setw(7) << "";
for (ALL(i, 1, n))
cout << setw(8) << "↓";
cout << endl
<< setw(7) << "---CNT:";
long long inverSum = sortMerge_inv(arr, 1, n);
for (ALL(i, 1, n))
cout << setw(7) << inver[i];
printf("\nInversions conut: %lld\n", inverSum); //输出逆序对和
hash_init(n);
printf("Hash: %lld\n", sortMerge_hash(arr_hash, 1, n, n)); //输出全排列hash值
printf("Sort: "); //输出归并排序后结果。
for (ALL(i, 1, n))
printf("%d ", arr[i]);
}
单调队列
用来求一定范围内的最值。
典型例题为“滑动窗口”
给出一个长度为$n$的数组，输出每$k$个连续的数中的最大值和最小值。
- 其中的单调为一种思想：
当我们解决问题的时候发现有许多冗杂无用的状态时，我们可以采用单调思想，用单调队列或类似于单调队列的方法去除冗杂状态，保存我们想要的状态，
struct Node
{
int Value, Top;
} Line[1000005]; //单调队列
int Line_N[1000005], //原数据
ans[1000005], //最终得到的最值，答案数组
Num, //数据个数
Length; //窗口长度
void Push(int Top, int Num, int Tail) //入队操作
{
Line[Tail].Top = Top;
Line[Tail].Value = Num;
}
void Find_Min() //寻找最小值
{
int Head = 1, Tail = 0;
for (int i = 1; i < Length; i++)
//这里前m-1个先直接进入队列，因为不用记录前m-1个的最值，只有第m个才能找出最值
//【假如窗长3，相当于第3个找第1个到第3个内的，第4个找第2个到第4个内的，所以把前2个push进队，从第三个开始找
{
while (Head <= Tail && Line_N[i] <= Line[Tail].Value)
Tail--;
//维护序列单调，如入队的数小于尾，破坏了单调递增，tail--把尾pop出去，直到大于等于队尾呈递增或者队列空
Push(i, Line_N[i], ++Tail); //然后入队
}
for (int i = Length; i <= Num; i++)
{
while (Head <= Tail && Line_N[i] <= Line[Tail].Value)
Tail--;
Push(i, Line_N[i], ++Tail); //同上道理，首先，要维护单调性，然后push
if (Line[Head].Top < i - Length + 1)
Head++; //判断出窗没有
ans[i - Length + 1] = Line[Head].Value; //这个时候第i个窗的最值为队首
}
}
//最大值只用将有关数据比较的小于等于改为大于等于即可
//使用例
{
for (ALL(i,1,Num-Length+1)) cout<<ans[i]<<" "; //直接从头到尾输出答案数组。
}
最小生成树
求出联通整个图所需要的最小边权。
一定会选择$n-1$条边。
典型例题为：
我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
Kruskal
该算法的基本思想是从小到大加入边，是个贪心算法。
-
过程：
- 按照边权进行排序
- 寻找最小边，如果加入后不会形成环，则选择此边。
- 重复，直到所有点联通（选择$n-1$条边）。
-
算法点：
- 并查集（用于判断加入后是否为环）
- 贪心（排序）
- 图的存储
-
用途：
- 最小生成树
- 判断整个图是否联通。
#define N 200005
int n, m,
f[N], //并查集数组
ans, //最小边权和
bs; //当前连了几条边
bool pd = 0; //是否联通，联通为1
struct Edge //储存方式：按边存
{
int u, v, w;
} e[N];
int find(int x) //并查集查找
{
if (f[x] == x)
return x;
return f[x] = find(f[x]);
}
bool cmp(Edge x, Edge y) //按权值排序
{
return x.w < y.w;
}
//初始化
{
for (register int i = 1; i <= n; i++) //并查集初始化
f[i] = i;
sort(e, e + m, cmp); //对边排序
}
//Kruskal算法实现
int main()
{
for (register int i = 0; i < m; i++)
{
int fv = find(e[i].v), fu = find(e[i].u); //我们取出当前边的起点和终点所在的祖先
if (fv == fu)
continue; //如果它们相同，就说明它们联通，那么就不用加这条边了
f[fv] = fu; //把祖先存进去
ans += e[i].w; //总答案+=这条边的权值
if (++bs == n - 1)
{ //连通n个点需要n-1条边
pd = 1; //判断是否连通的东西
break;
}
}
if (!pd)
cout << "orz"; //如果不连通就输出（这题好像没有这个数据
else
cout << ans;
}
最短路
Dijkstra
-
过程： 0. 初始化：将所有距离设为$\inf$，然后把起点设为0，并加入小根堆。
- 对那些刚刚被加入第一个集合的结点的所有出边执行松弛操作。
- 从第二个集合中，选取一个最短路长度最小的结点，移到第一个集合中。
- 重复：直到第二个集合为空，算法结束。
-
注意点：没有负权。
const int MaxN = 100010, MaxM = 500010;
struct edge //存储方式——邻接表
{
int to, dis, next;
} e[MaxM];
int head[MaxN]; //邻接表的头指针
int dis[MaxN], cnt;
bool vis[MaxN];
int n, m, s;
inline void add_edge(int u, int v, int d)
{
cnt++;
e[cnt].dis = d;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
struct node
{
int dis;
int pos;
bool operator<(const node &x) const
{
return x.dis < dis;
}
};
std::priority_queue<node> q;
inline void dijkstra()
{
dis[s] = 0;
q.push((node){0, s}); //初始化2——起点
while (!q.empty())
{
node tmp = q.top();
q.pop();
int x = tmp.pos, d = tmp.dis;
if (vis[x])
continue;
vis[x] = 1; //要取出来后，才证明这个是最小dis，才更改vis
for (int i = head[x]; i; i = e[i].next) //对所有边松弛
{
int y = e[i].to;
if (dis[y] > dis[x] + e[i].dis) //松弛操作
{
dis[y] = dis[x] + e[i].dis;
if (!vis[y]) //没被确定，入堆
q.push((node){dis[y], y});
}
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n; ++i)
dis[i] = 0x7fffffff; //初始化
for (register int i = 0; i < m; ++i) //读边
{
register int u, v, d;
scanf("%d%d%d", &u, &v, &d);
add_edge(u, v, d);
}
dijkstra();
for (int i = 1; i <= n; i++)
printf("%d ", dis[i]);
}
拓扑排序
-
思想：
- 选择一个入度为0的顶点输出
- 从AOV网删除这个节点，并且将所有与这节点有关的节点入度-1
- 重复以上两步，直到不存在入度为0的
- 如果输出数少于节点数，即实际上还有节点没输出出来，因此肯定是此图有回路，否则拓扑排序成功
-
用途：
- 按照“在走到一个节点之前，必须把所有能走到它的节点走到”这种条件，对图排序。（类似于要先学前置知识）
- 判断是否有环。
int In[105], //In记录所有节点的入度，
Out[105][105], //存储方式——邻接表。
//Out记录一个节点能走到的节点
//特别的Out[i][0]为i节点能走到节点的个数（出度）
Line[105]; //Line存排序结果
void Push(int Top, int &Tail) //入Line队列
{
Line[++Tail] = Top;
}
void Pop_Push(int Top, int &Head, int &Tail)
{
cout << Line[Top] << " "; //先输出这个节点
Head++; //删除这个节点，即出队
for (int i = 1; i <= Out[Line[Top]][0]; i++) //把它所有能走到的节点的入度--
{
In[Out[Line[Top]][i]]--;
if (!In[Out[Line[Top]][i]])
Push(Out[Line[Top]][i], Tail);
//这个时候判断是否为0，如果为0即push入队列里
}
}
void Topo(int Many) //拓扑
//如果要判断是否有环，即看tail是否小于many即可
{
int Head = 1, Tail = 0;
for (int i = 1; i <= Many; i++)
//刚开始从头到尾遍历一遍，如果入度为0，push到专门存入度为0的Line队列里
if (!In[i])
Push(i, Tail);
while (Head <= Tail)
Pop_Push(Head, Head, Tail); //开始排序
}
int main()
{
int Many, T;
cin >> Many; //有多少个节点
for (int i = 1; i <= Many; i++)
{
cin >> T; //开始读入每个节点的边
while (T)
{
Out[i][++Out[i][0]] = T; //记录能走到的节点
In[T]++; //能走到的节点的入度++
cin >> T;
}
}
Topo(Many);
}
/* 读入：
5
0
4 5 1 0
1 0
5 3 0
3 0
*/
/* 输出：
2 4 5 3 1
*/
KMP
用于“字符串匹配”问题。
- 什么是字符串的模式匹配？
给定两个字符串$S=“s_1,s_2,s_3,\cdots,s_n”$和$T=“t_1,t_2,t_3,\cdots,t_m"(m \le t)$，
在主串S中寻找子串T的过程叫做模式匹配，T称为模式。
#include <bits/stdc++.h>
#define MAX 2000000
using namespace std;
char s[MAX], f[MAX];
int Next[MAX];
int main()
{
scanf("%s%s", s, f);
int lens = strlen(s), lenf = strlen(f), k = 0;
for (int i = 1; i < lenf; i++)
{
while (k && f[i] != f[k])
k = Next[k];
Next[i + 1] = f[i] == f[k] ? ++k : 0;
}
k = 0;
for (int i = 0; i < lens; i++)
{
while (k && s[i] != f[k])
k = Next[k];
k += s[i] == f[k] ? 1 : 0;
if (k == lenf)
printf("%d\n", i - lenf + 2); //输出子串t在主串s中出现的位置
}
for (int i = 1; i <= lenf; i++)
printf("%d ", Next[i]);
}
/* 输入：
ABABABC
ABA
*/
/* 输出：
1
3
0 0 1
*/
//前面n-1行代表出现的不同位置
//最后一行代表字串t不同长度的border[i]
- border[i]
记为$\pi(i)$，代表：字符串$t$最长的“相等的真前缀与真后缀”的长度。
特别地，规定 $\pi[0]=0$ 。
举例来说，对于字符串
abcabcd，
$\pi[0]=0$ ，因为a没有真前缀和真后缀，根据规定为$0$
$\pi[1]=0$ ，因为ab无相等的真前缀和真后缀
$\pi[2]=0$ ，因为abc无相等的真前缀和真后缀
$\pi[3]=1$ ，因为abca只有一对相等的真前缀和真后缀：a，长度为$1$
$\pi[4]=2$ ，因为abcab相等的真前缀和真后缀只有ab，长度为$2$
$\pi[5]=3$ ，因为abcabc相等的真前缀和真后缀只有abc，长度为$3$
$\pi[6]=0$ ，因为abcabcd无相等的真前缀和真后缀同理可以计算字符串
aabaaab的前缀函数为 $[0, 1, 0, 1, 2, 2, 3]$ 。
Manacher
用于求回文串的算法。
给出一个只由小写英文字符$\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$组成的字符串$S$,求$S$中最长回文串的长度。
字符串长度为$n$。
#include <bits/stdc++.h>
#define N 50000000
#define MaxLen Right - i
#define Mirror 2 * Mid - i
using namespace std;
char s[N << 1];
int RL[N << 1];
void Read() //对读入的预处理——加入#来分割
{
int i = 1;
s[0] = '~', s[1] = '#';
while ((s[++i] = getchar()) != EOF)
s[++i] = '#';
}
int Manacher()
{
int Mid = 2, Right = 3, len = strlen(s) - 3, ans = 0;
RL[1] = 1, RL[2] = 2;
for (int i = 3; i <= len; i++)
{
if (i < Right)
RL[i] = min(MaxLen, RL[Mirror]);
else
RL[i] = s[i] == '#' ? 1 : 2;
while (s[i - RL[i]] == s[i + RL[i]])
RL[i]++;
if (Right < i + RL[i] - 1)
Right = i + RL[i] - 1, Mid = i;
ans = RL[i] - 1 > ans ? RL[i] - 1 : ans;
}
return ans;
}
int main()
{
Read();
cout << Manacher();
}
字典树——Trie
用于：查找一个字符串是否在“字典”中出现过。
找的封装好的模板。
struct trie
{
int nex[100000][26], cnt;
bool exist[100000]; // 该结点结尾的字符串是否存在
void insert(char *s, int l) // 插入字符串
{
int p = 0;
for (int i = 0; i < l; i++)
{
int c = s[i] - 'a';
if (!nex[p][c])
nex[p][c] = ++cnt; // 如果没有，就添加结点
p = nex[p][c];
}
exist[p] = 1;
}
bool find(char *s, int l) // 查找字符串
{
int p = 0;
for (int i = 0; i < l; i++)
{
int c = s[i] - 'a';
if (!nex[p][c])
return 0;
p = nex[p][c];
}
return exist[p];
}
};
其他
快速读入
inline int intRead()
{
int f=1,num=0;
char t=getchar();
while (t<'0' || t>'9') if (t=='-') f=-1,t=getchar(); else t=getchar();
while (t>='0' && t<='9') num=num*10+t-'0',t=getchar();
return f*num;
}
宏
#define ALL(NAME_i, BEGIN, TO) \
int NAME_i = BEGIN; \
NAME_i <= TO; \
NAME_i++
#ifdef SuperSASS
freopen("data.in", "r", stdin);
#endif