算法学习:马拉车算法

学习自博客:

马拉车算法(音译,Manacher’s algorithm)是一个复杂度为 $O(n)$ 的、求一个字符串最长回文子序列的算法。

回文字符串,就是指无论从左向右读还是从右向左读结果都是一样的字符串。如字符串google的最长回文字串为goog

极限暴力的求得字符串最长回文字序列的方法都是寻找每个中心点开始向两边扩延一位一位地看是否相同,这样的算法复杂度回到 $O(n^2)$,显然不满足一般的需求。且由于回文字符串长度的奇偶问题,还需要特别的奇偶分类问题:如回文字符串aba的中心是b这个字母,回文字符串abba的中心是两个b之间。这两种情况需要分别考虑。

马拉车算法思想

去除字符串长度奇偶分类的问题

马拉车首先在每两个字符之间(包括首尾两端)插入一个原字符串没有的特殊符号,比如#。假设我们现在的字符串为google,插入#后便转换为了:#g#o#o#g#l#e#。设字符串长度为 $len$,加入的特殊字符个数一定为 $len + 1$,而 $len$ 与 $len + 1$ 中必为一奇一偶,所以结果一定是一个奇数,这样的话部分回文字符串(如#g#o#o#g#)的中心一定会是一个字符而不是两字符中间。

半径数组

设原来的字符串为 $str$,加上特殊字符处理后的字符串为$strM$。为了记录每一位对应的最长回文字串半径,我们引入与 $strM$ 半径数组 $p[]$,其中 $p[i]$ 表示以 $strM[i]$ 为中心的最长回文字串的半径,如果 $p[i] = 1$ 就说明该回文串就是 $strM[i]$ 本身。如例子#g#o#o#g#l#e#,可得到如下表格:

$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12
$strM[i]$ # g # o # o # g # l # e #
$p[i]$ 1 2 1 2 5 2 1 2 1 2 1 2 1

可以观察到,$p[i] - 1$ 就是以第 $i$ 位为中心的回文字串在原字符串中的长度。假设在原字符串中,该回文字符串的长度 $l$,由于加入了 $l+ 1$ 个#,在新字符串中的长度就会变为 $ln = 2 \times l + 1$。而 $p[i]$ 存储的是新的字符串的回文字串的半径,也就是 $\frac{ln + 1}{2}$ $=$ $l + 1$,即 $p[i] = l + 1$,所以最终结果为 $p[i] - 1$。

由于字符串的最开始与最后都有一个#字符,为了在搜索回文字串时避免总是判断是否越界,我们在字符串的左端与右端都加上另外一个特殊字符,如$^。(其实最后一位处不需要加上这个特殊字符,因为字符串的最后本来就是有一位\0用以标记字符串的结束的。)

所以这个算法的重点就在于如何计算数组 $p[]$ 的值。

$p[]$ 数组求解

引入两个变量,分别为idmx。其中id为一个已经检查过了的最大的回文字符串的中心点,mx为这个回文字符串的最终点。在马拉车算法的过程中,我们不断的对这两个变量进行更新。在这个过程中,我们有公式:
$$
p[i] = \min(mx - i, p[2\times id - i])
$$
现在我们就重点来讲解这个公式,如下图所示(其中 $j$ 是 $i$ 关于 $id$ 的对称点($j = 2\times id - i$),蓝色串➀为以 $j$ 为中心的回文串,橙色串为以 $i$ 为中心的回文串,绿色串为以 $id$ 为中心的回文串):

1565748502350

目前我们已经求得了满足 $0 \leq x \leq i - 1$ 的 $p[x]$,接下来就是要使用以前的数据推得 $p[i]$。会有如下情况

  1. $i \leq mx$

    由于 $j$ 与 $i$ 关于 $id$ 对称,所以以 $j$ 为中心的回文串关于 $id$ 对称一下就成了以 $i$ 为中心的回文串。所以我们这个时候需要判断一下情况:

    1. 如果橙色串的末尾没有超过 $mx$, 即 $p[j] \leq mx - i$,此时 $p[i] = p[j]$。
    2. 如果橙色串的末尾超过了$mx$,即 $p[j] > mx - i$,此时就不能确定 $p[i] = p[j]$ 一定会成立了。则先赋值 $p[i] = mx - i$ ,然后手动向两边扩来得到最长回文子串。为什么 $p[j] = mx -i + 1$ 的情况归到了这里?因为当 $p[j] = mx -i + 1$,我们的回文子串直接定到了 $mx$ 上,我们不能确定 $mx$ 以后的位是否还能满足关于 $i$ 回文。
  2. $i > mx$

    那我们只能保证 $mx - i $ 这一段是满足的,所以我们就先让 $p[i] = mx -i$,其余部分使用笨方法慢慢扩张。

有没有可能橙色串的左端超过了 $mx$ 的对称点呢?不可能。如果说左端超过了 $mx$ 的对称点,且中心位于 $i$ 的话,则 $i$ 为中心的回文字串长度会超过以 $id$ 为中心的回文字串,也就是说以 $j$ 为中心的回文子串长度超过了 $id$ 为中心的回文字串,那么我的 $id$ 在之前应该被更新为 $j$。所以这种情况是不存在的。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
string Manacher(string str)
{
/*改造字符串*/
string res="$#";
for(int i=0; i < (int)str.length(); ++i) {
res += str[i];
res += "#";
}

/*数组*/
vector<int> p(res.length(), 0);
int mi = 0, right = 0; //mi为最大回文串对应的中心点,right为该回文串能达到的最右端的值
int maxLen = 0, maxPoint = 0; //maxLen为最大回文串的长度,maxPoint为记录中心点

for (int i = 1; i < res.length(); ++i){
p[i] = (right > i)? min(p[2 * mi - i], right - i) : 1; //关键句,文中对这句以详细讲解

while(res[i + p[i]] == res[i - p[i]])
++p[i];

if(right < i + p[i]) //超过之前的最右端,则改变中心点和对应的最右端
{
right = i + p[i];
mi = i;
}

if(maxLen < p[i]) //更新最大回文串的长度,并记下此时的点
{
maxLen = p[i];
maxPoint = i;
}
}
return str.substr((maxPoint - maxLen) / 2, maxLen - 1);
}

算法学习:扩展KMP

2019年8月5日下午,冰冷的雨滴击打着脆弱的窗户玻璃,机房里异常的安静,仿佛每个人都等待着一轮风暴。HDU的第五场多校赛已经过去了一半,距离吃饭只有两个半小时了,但我却没有一点开心的感觉。抬头,映入眼帘的就是一道魔鬼签到题目,和红色背景白色字体的“(-5)”字眼。机房的空调从来没有这么好使过,我甚至感到浑身寒冷,有几分想要颤抖身体。

比赛还是如期地结束了。这场比赛的这个签到题我还是没能做出来。是的,爆零了。我开始怀疑人生,怀疑自己存在的意义。挫败的我打开了题解,发现了这个叫做”扩展KMP“算法。虽然忧伤,但我还是尝试学习一下这个算法。于是……

题解传送门🚪

算法引入

假设现在有两个字符串,分别为 $S$ 与 $T$ ,其中 $S$ 为待匹配的串,$T$ 为进行匹配的串,现在我需要知道 $S$ 的每一位开始,分别可以匹配成功 $T$ 串中从头开始的连续的多长子串。

举个例子,比如现在 $S$ 为字符串AAAAABBB, $T$ 为字符串AAAAAC。我们定义数组extend[]为最终结果,其中 $extend[i]$ 为 $S.\mathrm{substr}(i,n)$ ($S[i \cdots n-1]$) 中与 $T$ 匹配成功的最长相同前缀的长度。如本例中可得到如下表格:

$i$ 0 1 2 3 4 5 6 7
$S$ A A A A A B B B
extend[i] 5 4 3 2 1 0 0 0

如果使用暴力进行这个匹配过程的话,算法复杂度就达到了 $O(m\times n)$,所以我们要用更好的算法来解决这个问题。这就是扩展 KMP 的任务。

算法思想

我们为何引入并使用next[]数组

暴力算法的问题就在于extend[]数组中的数据彼此之间是会有一些联系的,而暴力法并没有用上这些联系而直接进行了重新匹配。

假设我们现在匹配到了第 $i$ 个位置,如下图:

1565080573726

其中图中 $p$ 指从 $S$ 的第 $a$ 位开始与 $T$ 匹配成功的最后一位的下一位,也就是说 $S.\mathrm{substr}(a,p) = T.\mathrm{substr}(0,p-a)$。如果从 $i$ 开始的几位与 $T$ 开头的几位相同,那么 $extend[i]$ 的值就是这段距离的长度。所以我们引入 next[]数组来记录匹配串 $T$ 中相同前缀部分的长度。比如对于AAAAAC,我们就可以得到以下列表:

$i$ 0 1 2 3 4 5
$T$ A A A A A C
next[i] 6 4 3 2 1 0

从头开始遍历 $S$,设当前遍历到了第 $i$ 位,$i + next[i -a ]$ 的值会有以下几种情况:

注意next[]数组

  1. $i + next[i - a] <p$

    1565095531149

    说明这个时候的 $i + next[i-a]$ 还在可控范围内。因为我们已经知道了 $S.\mathrm{substr}(a, p)$ 与 $T.\mathrm{substr}(0, p-a)$ 相同,而 $S[i + next[i -a]]$ 还在 $S.\mathrm{substr}(a, p)$ 的范围内,所以这个时候 $S.\mathrm{substr}(i, i + next[i - a])$ 与 $T.\mathrm{substr}(i - a, i - a + next[i - a])$ 就可以成立,于是 $S.\mathrm{substr}(i, i + next[i - a])$ 与 $T.\mathrm{substr}(0, next[i - a])$ 就会成立,所以我们就可以知道 $extend[i]$ 的值为 $next[i - a]$。

  2. $i + next[i - a] = p$

    1565095544744

    这种情况下,$S[p]$ 与 $T[p - a]$ 不一定相同,$T[p - i]$ 与 $T[p - a]$ 也不一定相同,但却有 $T[p - a]$ 与 $S[p]$ 相同的情况,所以我们就直接对比 $S[p]$ 与 $T[p - a]$ 及以后。然后得到 $next[i]$ 的值。当我最后匹配直到 $S[p + k]$ 与 $T[p+k-a]$ 相同,则可得到 $next[i]$ 的值为 $p + k - i$。下一次再匹配时,只需要从 $a = i$、$p = p + k$ 开始就可以了。

  3. $i + next[i - a] > p$

    1565097429456

    这种情况下我们就不能确定这上面的匹配方式相同了,所以我们就需要从 $S[p]$ 与 $T[p - i]$ 开始匹配,具体做法同第 $2$ 种情况。

获得next[]数组

其实这个就很简单了。next[]数组反映的即是 $T$ 字符串中从第 $i$ 位开始的内容与从第 $0$ 位内容开始的最大相同前缀,所以其实只是把 $T$ 与自己匹配跑了一编这个算法。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int next[100];
int extend[100];
string S, T;
void getNext(){
int m = T.length();
// m:T的长度
int a = 0, p = 0;
next[0] = m;
for (int i = 1; i < m; i++) {
if (i >= p || i + next[i - a] >= p) {
if (i >= p) p = i;
while (p < m && T[p] == T[p - i])
p++;
next[i] = p - i;
a = i;
}
else
next[i] = next[i - a];
}
}
void getExtend(){
int n = S.length();
int m = T.length();
int a = 0, p = 0;
getNext();
for (int i = 0; i < n;i ++){
if (i >= p || i + next[i - a] >= p) {
// i >= p 的作用:举个典型例子,S 和 T 无一字符相同
if (i >= p) p = i;
while (p < n && p - i < m && S[p] == T[p - i])
p++;
extend[i] = p - i;
a = i;
}
else
extend[i] = next[i - a];
}
}

算法学习:离散化

Banner 图源网络,侵删。

离散化

离散化:将无限空间中的有限个体映射到有限的空间中。

比如说我有一个无尽的坐标轴,上面有 $10^4$ 个点,每个点的坐标值可以很大很大接近无限。如果我想知道比其中一个点小的点有多少个,暴力比较每个点的坐标值则会因为数据过大而 Boom。而我们通过点与点相对关系,将点的值进行重新赋值,则可以大大减小算法的复杂度。

比如,我现在的数轴上只有6个点, 他们的坐标分别为 $0$、$610$、$10^5+2$、$99$、$5$、$10^9+45$,如果我只是按照他们原有的值进行比较,最大要比较到 $10^9+45$。而如果我们用他们的相对大小来进行比较,即转换为 $0$、$3$、$4$、$2$、$1$、$5$ 则会方便很多。这就是离散化的思想,就是将离散的事物进行重新分配

离散化方法:排序+二分

(推荐使用本方法)

基本原理就是排序后使用STL中的unque()函数来获取整体数据不同元素的个数,然后在已排序序列二分查找 $num[i]$ 的值,从而得到对 $num[i]$ 对应的值,然后进行重新赋值。

1
2
3
4
5
6
7
8
for(int i = 0; i < n; i++){
scanf("%d", &num[i]);
disc[i] = num[i]; // num:原数据数组,disc:离散化后的数组
}
sort(disc, disc + n);
cnt = unique(disc, disc + n) - disc; // STL中的unique函数,具体内容见👇
for(int i = 0; i < n; i++)
num[i] = lower_bound(disc, disc + n, num[i]) - disc;
  • unique(a, b)函数:STL中比较常见的函数,他的功能是“删除”序列中所有相邻的重复元素(只保留一个),因为只是处理相邻的重复元素所以在使用这个函数之前要进行排序。(此处略去更具体的都能再写一页博客的内容)。其中参数a,b为指针,类似sort()函数中的参数。
  • lower_bound(a, b, v)函数:二分查找返回ab指针之间空间中大于等于 $v$ 的第一个迭代器。

离散化方法:排序+暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define MAX_N 1e5+5 // 根据实际问题调整
struct Node{
int data;
int index;
}num[MAX_N];
bool cmp(Node a, Node b){
return a.data < b.data;
}
int rank[MAX_N], n;
int main(){
scanf("%d", &n);
for(int i = 0;i < n; i++){
scanf("%d", &num[i].data);
num[i].index = i;
}
sort(num, num + n, cmp);
for(int i = 1; i <= n; i++){
rank[num[i].id] = i;
}
return 0;
}

排序之后按照原顺序进行赋值,相同元素就会出现离散化不成同一元素的情况,所以不推荐这种方法。


听大佬说洛谷P1955是一道有关离散化的题,我这个蒟蒻还没有做。🙃

有时间做了再搞题解什么的。🙃

题解我搞出来了,传送门:🚪

算法学习:后缀数组

学习自:

后缀数组简介

后缀:从字符串某个位置 $i$ 到字符串末尾的子串,我们定义以字符串 $str$ 的第 $i$ 位为第一个元素的后缀为suff[i]。(后缀的英文:suffix

后缀数组:把字符串 $str$ 的每一个后缀按照字典序排序后所形成的数组。

后缀数组的实现

变量定义

  • suff[]数组,用来记录从第 $i$ 位开始的后缀
  • sa[]数组(suffix array),存储的是字典第 $i$ 小的后缀的下标。比如sa[0] = 8代表的是suff[]数组中第 $8$ 位后缀在字典序中最小。而suff(sa[0])才真正存储这最小的那个后缀的内容。
  • rank[]数组,与sa[]相反,存储的是下标为 $i$ 的后缀为第几小。一定存在关系 $\text{rank}[\text{sa}[i]] = i$。

倍增算法

问题在于我们怎么给这个后缀数组排序,如果强硬 sort 的话,sort 算法复杂度本来就有 $O(n\log_2n)$ 字符串排序还不用于一般数字的排序,每个字符串对比还有 $O(n)$ 复杂度。也就是说用 sort 的话,复杂度会达到 $O(n^2\log_2n)$。这就很伤不是么,所以我们要想出来一个复杂度更低的算法。

我们知道,两个字符串的比较,如果前半部分相同则比较结果取决于后半部分的比较结果,否则只需要看前半部分的比较结果。基于这个事实,我们考虑以下方法:

对于字符串 $str$,定义k-前缀为:

$$
str_k=\begin{cases}
str[0\dots k - 1] = str.\mathrm{substr}(0, k) & (k\leq str.\mathrm{length}()) \\
str & (k > str.\mathrm{length}())
\end{cases}
$$
然后类似的,我们定义出基于k-前缀意义下的sa[]数组和rank[]数组,在这里我们记作 $sa_k$ 与 $rank_k$ 数组。其中 $sa_k$ 为k-前缀意义下的后缀数组,$rank_k$ 为k-前缀意义下的名次数组。则有以下计算方式:

  • 容易求出 $rank_1$ 的值与 $sa_1$ 的值,只需要进行 sort 对第一个字母排序就可以了。

  • 得到了 $rank_k$,则定义二元组 $(rank_k[i],rank_k[i + k])$,按照“如果 $rank_k[i]$ 相同则比较$rank_k[i +k]$,否则则比较 $rank_k[i]$ ”的方法来进行sort,即可求出 $sa_{2k}$。

  • 求出了 $sa_k$ 则可以很快求出 $rank_k$,有以下关系:
    $$
    rank_k[i] = \begin{cases}
    rank_k[i - 1] & suff[sa[i]]_k = suff[sa[i - 1]]_k \\
    rank_k[i - 1] + 1 & suff[sa[i]] _ k \neq suff[sa[i - 1]]_k
    \end{cases}
    $$

这样的话我们求解的顺序就是:
$$
sa_1 \ \& \ rank_1 \rightarrow sa_2 \rightarrow rank_2 \rightarrow sa_4 \rightarrow rank_4 \rightarrow \cdots \rightarrow sa_n \rightarrow rank_n
$$
当不再出现并列的 $rank$ 的时候就可以结束循环。整个过程如下图所示:

1564227558972

每一次排序需要进行 $n\log_2n$ 次比较,每一次比较需要 $O(1)$ 复杂度,总共进行 $\log_2n$ 次比较,因此总时间复杂度为$O(n\log_2^2n)$。

基数排序

这一部分我们要试图探索比 $O(n\log _2^2n)$ 更优的排序算法。

算法学习:线性基

线性基 ——异或和求最大值

学习自博客:https://blog.sengxian.com/algorithms/linear-basis

基(basis)是线性代数中的一个概念,他是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素被称为基向量。向量空间中的任意一个元素,都可以唯一地被表示成基向量的线性组合。异或空间基向量,被称为线性基。

从线性代数开始的异或世界

线性空间(向量空间)

定义$({\Bbb F},\mathrm V,+,\cdot)$为线性空间(Vector Space)。其中 $\Bbb F$ 为域,其中的元素为标量;$\mathrm V$ 为集合,其中的元素称为向量,有以下两个运算:

  1. 向量加法:$\mathrm V+\mathrm V\rightarrow \mathrm V$,记作 ${\bf v}+{\bf w},\exists {\bf v},{\bf m} \in \mathrm V$;
  2. 标量乘法:${\Bbb F}\cdot \mathrm V\rightarrow \mathrm V$,记作 $a \cdot {\bf v}, \ \exists {\bf a} \in {\Bbb F},{\bf v}\in \mit \mathrm V$

且运算满足以下公理:

  1. 向量加法结合律:${\bf u} + ({\bf v} + {\bf w}) = ({\bf u} + {\bf v} ) + {\bf w}$;
  2. 向量加法交换律:${\bf v} + {\bf w} = {\bf w} + {\bf v}$;
  3. 向量加法的单位元:$\mathrm V$ 中有一个被称为零向量的 $\bf 0$,$\forall {\bf v}\in \mathrm V$,${\bf v} + {\bf 0} = {\bf v}$;
  4. 向量加法的逆元素:$\forall {\bf v}\in \mathrm {V}$,$\exists {\bf w} \in \mathrm V$,使得${\bf v} + {\bf w} = 0$,其中 ${\bf w}$ 称为 ${\bf v}$ 的逆元;
  5. 标量乘法与标量的域乘法相容:$a(b{\bf v} ) = (ab){\bf v}$;
  6. 标量乘法的单位元:域$\Bbb F$存在乘法单位元 $1$ 满足 $1{\bf v} = {\bf v}$;
  7. 标量乘法对向量加法的分配律:$a({\bf u} + {\bf v}) = a{\bf u} + a{\bf v}$;
  8. 标量乘法对域加法的分配律:$(a+b){\bf v} = a{\bf v} + b{\bf v}$。

基本性质

  • 零元素 $0$ 是唯一的;
  • 对任意的$a\in {\Bbb F}$,$a \cdot {\bf 0} = {\bf 0}$;
  • 对任意的${\bf u}\in \mathrm V$,${\bf 0}\cdot{\bf u} = {\bf 0}$( ${\bf 0}$ 是 $\Bbb F$ 的加法单位元);
  • 如果 $a \cdot {\bf u} = {\bf 0}$,则要么 $a = 0$ ,要么 ${\bf u} = {\bf 0}$;
  • 向量加法的逆向量 $\bf v$ 是唯一的,记作$-\bf v$。${\bf u} + {- \bf v}$ 也可以写成 ${\bf u} - \bf v$,两者都是标准的;
  • 对 $\forall {\bf u} \in \mathrm V$, $-1\cdot {\bf u}=-{\bf u}$。
  • 对 $\forall a\in \Bbb F$ 以及${\bf u}\in V$,$(-a)\cdot {\bf u} = -(a\cdot {\bf u}) = a \cdot (-{\bf u})$。

其他扩展内容

最为常见的向量空间的例子是给定了直角坐标系的平面:平面上的每一点 $P$ 都有一个坐标 $P(x,y)$ ,并对应着一个向量 $(x,y)$。所有普通意义上的平面向量组成了一个空间,记作 $\Bbb R^2$(因为每个向量都可以表示为两个实数构成的有序数组$(x,y)$。可以验证,对于普通意义上的向量加法和标量乘法,$\Bbb R^2$ 满足向量空间的所有公理。设所有普通意义上的平面向量记作 $\mathrm V$ ,则 ${\Bbb R}^2 = ({\Bbb R}, \mathrm V,+,\cdot)$。实际上,向量空间是 $\Bbb R^2$ 的推广。

对于通常意义上的多项式加法和标量乘法,所有系数为实数的多项式的集合 $\Bbb R[\bf X]$ 也构成一个向量空间。更广泛的,所有从实数域射到实数域的连续函数的集合 $\mathcal C(\mathbb R,\mathbb R)$也是向量空间

线性无关

对向量空间中 $\mathrm V$ 上的 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,若存在不全为 $0$ 的数 $a_i\in \mathbb F$,满足:
$$
a_1{\bf v}_1 + a_2{\bf v_2} + \dots + a_n{\bf v} _ n = 0
$$
则称 $n$ 个向量线性相关Linearly Dependent),否则称为线性无关Linearly Independent)。

线性组合

对于向量空间中 $\mathrm V$ 上 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,其线性组合Linear Combination)是如下形式的向量:
$$
a_1{\bf v_1} + a_2{\bf v}_2 + \dots+a_n{\bf v}_n
$$
其中 $a_1,\dots,a_n\in \mathbb F$。

张成(Span

对于相连空间中 $V$ 上 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,其所有线性组合所构成的集合称为 $({\bf v}_1,\dots,{\bf v}_n)$ 的张成Span),记作$\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$。

基(Basis)

Basis)(也称为基底)是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素称为基向量。向量空间中任意一个元素,都可以唯一地表示成基向量的线性组合。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数

给定一个向量空间 ${\displaystyle \mathrm {V}}$。${\displaystyle \mathrm {V}}$ 的一组 ${\displaystyle {\mathfrak {B}}}$ 是指 ${\displaystyle \mathrm {V} }$ 里面的可线性生成 ${\displaystyle \mathrm {V} }$ 的一个线性无关子集。${\displaystyle {\mathfrak {B}}}$ 的元素称为基向量

更详细来说,设 ${\displaystyle {\mathfrak {B}}={\mathbf e_{1},\mathbf e_{2},\cdots ,\mathbf e_{n}}}$ 是在系数域 ${\displaystyle \mathbb {F}}$(比如实数域 ${\displaystyle \mathbb {R}}$ 或复数域${\displaystyle \mathbb {C}}$)上的向量空间 ${\displaystyle \mathrm {V}}$ 的有限子集。如果 ${\displaystyle {\mathfrak {B}}}$ 满足下列条件:

  1. 对任意 ${\displaystyle (\lambda_{1},\lambda_{2},\cdots ,\lambda_{n})\in \mathbb {F} ^{n}}$ ,如果 ${\displaystyle \lambda_{1}\mathbf e_{1}+\lambda_{2}\mathbf e_{2}+\cdots +\lambda_{n}\mathbf e_{n}=0}$ 则必然 ${\displaystyle \lambda _{1}=\lambda _{2}=\cdots =\lambda _{n}=0}$;
  2. 对任意 ${\displaystyle \mathbf v\in \mathrm {V} }$,可以选择 ${\displaystyle (\lambda_{1},\lambda_{2},\cdots ,\lambda_{n})\in \mathbb {F} ^{n}}$,使得 ${\displaystyle v=\lambda_{1}\mathbf e_{1}+\lambda_{2}\mathbf e_{2}+\cdots +\lambda_{n}\mathbf e_{n}}$。

就说 ${\displaystyle {\mathfrak {B}}}$ 是向量空间 ${\displaystyle \mathrm {V} }$ 的一组

性质

设 $\mathfrak {B}$ 是向量空间 $\mathrm V$ 的基。则 $\mathfrak {B}$ 具有以下性质:

  1. $\mathrm V$ 是 $\mathfrak {B}$ 的极小生成集,就是说只有 $\mathfrak {B}$ 能张成 $\mathrm V$,而它的任何真子集都不张成全部的向量空间。
  2. $\mathfrak {B}$ 是 $\mathrm V$ 中线性无关向量的极大集合,就是说 $\mathfrak {B}$ 在 $\mathrm V$ 中是线性无关集合,而且 $\mathrm V$ 中没有其他线性无关集合包含它作为真子集。
  3. $\mathrm V$中所有的向量都可以按唯一的方式表达为 $\mathfrak {B}$ 中向量的线性组合。

第三点尤其重要,感性的理解,基就是向量空间中的一个子集,它可以通过唯一的线性组合,来张成向量空间中所有的向量,这样就可以大大的缩小我们向量空间的大小。

线性相关性引理(Linear Dependent Lemma

如果 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$ 在 $\mathrm V$ 中是线性相关的,并且 $\mathbf{v}_1 \neq 0$,则有至少一个 $j \in {2, \ldots, m}$使得下列成立:

  1. $\mathbf{v}_j \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_{j - 1})$;
  2. 如果从$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$ 去掉第 $j$ 项,则剩余向量组的张成仍然等于 $\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v_n})$。

证明:

设 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$在 $\mathrm V$ 中是线性相关的,并且 $\mathbf{v}_1 \neq \mathbf{0}$,则有不全为 $0$ 的 $a_1, \ldots, a_n \in \mathbb F$,使得
$$
a_1\mathbf{v}_1 + \ldots + a_m\mathbf{v}_m = \mathbf{0}
$$
$a_2, a_3, \ldots, a_n$不会全为 $0$(因为 $\mathbf{v}_1 \neq \mathbf{0}$)。设 $j$ 是 ${2, \ldots, m}$ 中使得 $a_j \neq 0$ 的最大者,那么
$$
\mathbf{v}_j = -\frac {a_1} {a_j}\mathbf{v}_1 - \ldots - \frac {a_{j - 1}} {a_j}\mathbf{v}_{j - 1}
$$
这就有 $(1)$ 成立。

为了证明 $(2)$,设 $\mathbf{u} \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$,则存在 $c_1, \ldots, c_n \in F$,使得
$$
\mathbf{u} = c_1\mathbf{v}_1 + \ldots + c_n\mathbf{v}_n
$$
在上面的等式中,可以用之前的等式右边来代替$ \mathbf{v}_j$。这样 $\mathbf{u} $包含于从 $(\mathbf{v}_0, \ldots, \mathbf{v}_n)$ 去掉第 $j$ 项的张成,因而 $(2)$ 成立。

线性基

对于一个十进制数 $a$,我们将其转换为二进制得到 $(b_m\dots b_0)_2$。然后将转换后的二进制看作是一个向量,则得到$\mathbf a = (b_m,b_{m-1},\dots,b_0)$。方便起见,我们称向量 $\mathbf a$ 的第 $i$ 位为 $b_i$。

向量组 $\mathbf a_1,\dots\mathbf a_n$ 可以张成一个向量集合 $\mathrm{span}(\mathbf a_1,\dots,\mathbf a_n)$,则可以得到一个线性空间 $\mathrm V = ({0,1},\mathrm{span}(\mathbf a_1,\dots,\mathbf a_n),\oplus,\cdot)$。

按照以下的方法得到这个线性空间的一个基 $\mathfrak B = (\mathbf a_1,\dots,\mathbf a_n)$ :

第 $1$ 步:如果 $\mathbf a_1 = \mathbf 0$,则从 $\mathfrak B$ 中去除 $\mathbf a_1$,否则保持 $\mathfrak B$ 不变。

第 $j$ 步:如果 $\mathbf a_j \in \mathrm{span}(\mathbf a_1, \dots ,\mathbf a_{j - 1})$ ,则从 $\mathfrak B$ 中去掉 $\mathbf a_j$,否则保持 $\mathfrak B$ 不变。

经过 $n$ 步后终止程序,得到一个向量组 $\mathfrak B$。由于每一次去掉的项包含于前面诸向量的张成,到最后这个组 $\mathfrak B$ 仍然可以张成 $\mathrm V$。而且这一程序确保了 $\mathfrak B$ 中的任何向量都不包含于它前面诸向量的张成,根据线性相关性引理可知 $\mathfrak B$ 是线性无关的。于是 $\mathfrak B$ 是 $\mathrm V$ 的一个基。

利用高斯消元来判断向量能否被前面的向量张成,就可以写出下面的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define MAX_BASE 63 // 当数据为long long型时,int型为31
void cal(){
for(int i = 0; i < n; i++){
for(int j = MAX_BASE; j >= 0; j--){
if(a[i] >> j & 1){
if(b[j])
a[i] ^= b[j];
else{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--){
if (b[k] && (b[j] >> k & 1))
b[j] ^= b[k];
}
for (int k = j + 1; k <= MAX_BASE; k++){
if (b[k] >> j & 1)
b[k] ^= b[j];
}
break;
}
}
}
}4
}
  • b[]数组用来记录最后得到的基 $\mathfrak B$ ;a[]数组为起初的每一个数字,即 $\mathbf a_1,\mathbf a_2,\dots,\mathbf a_n$。
  • 虽然数组每一个位置存储的是一个int型数字,但实际上表示的是一个二进制向量,为了表述方便,我们称b[i]为数组b[]的第 $i$ 行。
  • 在第 $i$ 步时,从高到低考虑数 $a_i$ 为 $1$ 的二进制位 $j$,如果数组b[]中第 $j$ 行已经存在内容了,我们就不能将$a_i$ 加到b[]中第 $j$ 行这个位置。而为了保证未来加进去的基向量与其他基向量线性无关,将数 $a_i$ 与 $b_i$ 进行异或计算,就可以消掉可用已经存在的基向量来表示的部分。
  • 如果数组b[]中的第 $j$ 行不存在内容(内容为 $0$),则我们可以将(已经被前面步骤处理好的)数 $a_i$ 加入到这一行。此后为了维护对角矩阵,先用下面的行消自己,再用自己消上面的行。
  • 上面代码中,b[j] >> k & 1可以用来判断 $b_j$ 二进制的第 $k$ 位是否为 $1$。为什么需要& 1?如果没有这个操作,我得到的不仅仅是第 $k$ 的信息,& 1可以让结果只保留第 $k$ 位的信息。

我们来模拟一下这个过程。设 $n = 5$,$a = {7, 1, 4, 3, 5}$。矩阵 $\mathfrak B$ 一开始长这样:
$$
\begin{bmatrix}
0 &0 &0 \\
0 &0 &0 \\
0 &0 &0
\end{bmatrix}
$$
我们从 $a_1$ 开始,$a_1 = 7 = (111)_2 = \mathbf a_1$,而 $\mathfrak B$ 目前为空。所以我就可以直接把他放进去了,因为$j = \mathrm{$MAX\_BASE} = 2$,所以我就把他放在了第二行(因为是上三角矩阵,所以最下面的为第 $0$ 行)。
$$
\begin{bmatrix}
1 &1 &1 \\
0 &0 &0 \\
0 &0 &0
\end{bmatrix}
$$
然后考虑放$a_2$,$a_2 = 1 = (001)_2 = \mathbf a_2$,在 $j = 2$ 与 $j = 1$ 时都不满足a[i] >> j & 1的条件,所以不进行操作。$j = 0$ 时,第 $0$ 行没内容,所以就直接放在了第 $0$ 行上,于是矩阵就成了:
$$
\begin{bmatrix}
1 &1 &1 \\
0 &0 &0 \\
0 &0 &1
\end{bmatrix}
$$
然后用下面的行消自己,好的不存在下面的行。再用自己消上面的行,所以第 $2$ 行会消去最后一个 $1$,矩阵变成:
$$
\begin{bmatrix}
1 &1 &0 \\
0 &0 &0 \\
0 &0 &1
\end{bmatrix}
$$
接下来就轮到了 $a_3$ 了,$a_3 = 4 = (100)_2 = \mathbf a_3$,在 $j = 2$ 时符合条件,但第 $2$ 行已经有内容了,所以我们进行 $a_3 = a_3 \oplus b_2$ 的操作,于是 $a_3$ 成了 $(010)_2$ 。$j = 1$ 时有一次满足条件,所以将他放在了第 $1$ 行上,于是矩阵成了:
$$
\begin{bmatrix}
1 &1 &0 \\
0 &1 &0 \\
0 &0 &1
\end{bmatrix}
$$
然后用下面的行消自己,好的什么都消不了。然后用自己消上面的行,所以第 $2$ 行中间的 $1$ 被消掉了,矩阵变成了:
$$
\begin{bmatrix}
1 &0 &0 \\
0 &1 &0 \\
0 &0 &1
\end{bmatrix}
$$
接下来谁也进不去了,结束。

那既然已经知道了结果会是一个上三角矩阵为啥我不直接生成一个呢?因为最终生成的 $\mathfrak B$ 很有可能不是一个满的上三角矩阵,比如这个样子的:
$$
\begin{bmatrix}
1 &0 &1&0 \\
0 &1 &0 &0 \\
0 &0 &0 &0 \\
0 &0 &0 &1
\end{bmatrix}
$$
这样所有被选上的 $\mathbf a_i$ 构成了一个向量空间 $\mathrm V$ 的一个基 $\mathfrak B$,同样矩阵 $b$ 的每一个非 $\mathbf 0$ 向量 $\mathbf b_i$ 组成的基也是向量空间 $\mathrm V$ 的基。我们所指的线性基,特指高斯消元解出的对角矩阵的非零行构成的向量组。如果矩阵的主对角线上第 $i$ 行的元素为 $1$,此时我们称第 $i$ 位存在于线性基中。对于存在于线性基的二进制位,有一个重要的性质:
$$
对于任意存在于线性基的二进制位\ i ,至多只有一个\ \mathbf b_j\ 满足第\ i\ 位为\ 1。
$$
因为我们已经在得到线性基的过程中,不断地使用每一个向量来对上下进行消除,所以 $\mathbf b_j$ 一定消去了别的向量第 $i$ 位上的 $1$,所以二进制位 $i$ 只存在于 $\mathbf b_j$ 上。而对于不再线性基中的二进制位 $i$,那么主对角线第 $i$ 行位以下的全部为 $0$, 而上方就可能会有若干个 $1$。

线性基的应用

线性基的题型相对比较固定,以下几类基本就是线性基了:

  • 最大异或和
  • 第 $k$ 大异或和 / 这些元素的异或和是第几大
  • 求所有异或值的和

例题$(1)$ To xor or not to xor

题目连接:https://codeforces.com/problemsets/acmsguru/problem/99999/275

Description

The sequence of non-negative integers $A_1$, $A_2$, …, $A_n$ is given. You are to find some subsequence $Ai_1$, $Ai_2$, …, $Ai_k$ $(1 \leq i_1 < i_2 < … < i_k \leq N)$ such, that $Ai_1 \oplus Ai_2 \oplus \dots \oplus Ai_k$ has a maximum value.

Input

The first line of the input file contains the integer number $N$ $(1 \leq N \leq 100)$. The second line contains the sequence $A_1, A_2, \dots , A_n (0 \leq Ai \leq 10^{18})$.

Output

Write to the output file a single integer number – the maximum possible value of $Ai_1 \oplus Ai_2 \oplus \dots \oplus Ai_k$ .

Sample test(s)

Input
1
2
3 
11 9 5
Output
1
14

很单纯的求最大异或和。根据以上的内容,我们可以求出这个向量空间的一组线性基 $\mathfrak B$,则最大的异或和就是将线性基中所有的向量异或起来得到的向量所对应的数。证明如下:

最高的二进制位只存在于数值最大的基向量上,所以最大的基向量肯定要被选。运用归纳法,假设前 $i$ 大的都需要选,考虑第 $i + 1$ 大的向量选不选。显然第 $i + 1$ 大的基向量能对异或和贡献它的最高的二进制位 $j$,因为二进制位 $j$ 在之前的异或和中必然为零(因为二进制位 $j$ 只存在于第 $i + 1$ 大的基向量中)。如果不选,之后的所有数对答案的贡献都只能在小于这个二进制位的地方做贡献,总是比选 $i + 1$ 得到的答案小,所以这个数必须选。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define MAX_BASE 63
long long a[101];
long long b[MAX_BASE];
int n;
void cal(){
for(int i = 0; i < n; i++){
for(int j = MAX_BASE; j >= 0; j--){
if(a[i] >> j & 1){
if(b[j])
a[i] ^= b[j];
else{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--){
if (b[k] && (b[j] >> k & 1))
b[j] ^= b[k];
}
for (int k = j + 1; k <= MAX_BASE; k++){
if (b[k] >> j & 1)
b[k] ^= b[j];
}
break;
}
}
}
}
}
int main(){
scanf("%d" ,&n);
memset(b, 0, sizeof(b));
memset(choice, 0, sizeof(choice));
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
cal();
long long ans = 0;
for (int i = 0; i <= MAX_BASE; i++) {
if(b[i]){
ans ^= b[i];
}
}
printf("%lld\n", ans);
}

算法学习:尺取法

假设给你一个数组与一个整数,要求你的到这个数组中的一个子区间使其的区间和等于这个整数,你会怎么做呢。可能首先想到的就是开一个双重循环,然后每一次都求一次和,然后和给定的数进行比较:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int sum;
int ansi, ansj;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
sum = 0;
for(int k = i; k <= j; k++){
sum += ls[k];
}
if(sum == x){
ansi = i; ansj = j;
goto ans;
}
}
}
ans:
printf("%d %d\n", ansi, ansj);

这样的话,复杂度就会到达 $O(n^2)$。

尺取法的算法思想来源于以上那个算法,区别在于不再对前后指针进行疯狂枚举,也不再需要每次都进行一次求和。我们设置两个指针,起初都指向开头。然后如果区间的元素和小于给定的数,则将右指针右移。如果大于指定的数,则将区间的左指针右移。相同就出结果了。这样的话每次求和只需要加上或减去那个唯一一个有区别的元素。复杂度会降低到 $O(n)$。

如下习题(POJ 3016):

Description

A sequence of $N$ positive integers $(10 < N < 100000)$, each of them less than or equal $10000$, and a positive integer $S(S < 100000000)$ are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to $S$.

Input

The first line is the number of test cases. For each test case the program has to read the numbers $N$ and $S$, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file. if no answer, print $0$.

Sample Input

1
2
3
4
5
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Sample Output

1
2
2
3

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <climits>
using namespace std;
int lis[100005];
long long sum;
int min(int a, int b){
if(a > b)
return b;
else return a;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
int N, S;
scanf("%d %d", &N, &S);
for (size_t i = 0; i < (size_t)N; i++) {
scanf("%d", &lis[i]);
}
int left = 0, right = 0;
sum = lis[0];
int ans = INT_MAX;
while(left <= right && right < N){
if(sum < S){
right++;
sum += lis[right];
}else if(sum >= S){
ans = min(ans, right - left + 1);
sum -= lis[left];
left++;
}
}>
if(ans != INT_MAX)
printf("%d\n", ans);
else printf("0\n");
}
}

算法学习:倍增思想

个人认为来源于二进制的思想。

img

对于如图式的一系列区域。

以往的记录方式,都是从A出发,走一步到了A右面一格,走两步到了A右面两格位置,……,走11步,走到了B位置。这样记录的话,每个节点都需要记录 $n - i$ 条内容,全部也就是需要 $\frac{n(n-1)}{2}$条,也就是 $O(n^2)$ 的空间复杂度。而由于每个数都可以写为2进制,那么每个点我只需要记录走一步、走两步、走四步、走八步……的位置,比如从A点,我可以走 $1+2+8=11$ 步到达B,也就是读取A走1步后在读取目前这个格子走两步再读取目前这个格子走八步的位置就可以到达B点。

而对于每一个点,走4步的位置就相当于走两步后的位置再走两步,走八步的位置就相当于走两步的位置再走两步再走两步……以此类推。

位运算符

位运算符为二进制运算符,所以是将参与运算的数据转换为二进制后进行运算。按右对齐,左补符号位运算。

  • >>:右移运算符,右移 $i$ 位相当于将该数乘以了 $2^i$。
  • <<:左移运算符,左移 $i$ 位相当于将该数除以了 $2^i$。
  • &:按位与运算,如 $5 & 3$ 相当于即为$(0101)_2 & (0011)_2 = (0001)_2$,所以结果为$1$。
  • |:按位或运算 ,如 $5 \ | \ 3$ 相当于 $(0101)_2\ |\ (0011)_2 = (0111)_2$,所以结果为$7$。
  • ~:按位取反。
  • ^:异或运算符,如 $5 \ \text{^} \ 3$ 相当于 $(0101)_2\ \text{^} \ (0011)_2 = (0110)_2$,所以结果为$6$。
    • 异或交换律:$a\otimes b = b\otimes a$
    • 异或结合律:$(a\otimes b)\otimes c= a\otimes(b\otimes c)$
    • 异或自反性:$a\otimes b\otimes b=a\otimes 0=a$
    • 对于任何数都有:$x\otimes x =0$、$x\otimes 0=x$
  • &=|=>>=<<=^=:位运算的复合赋值运算符

快速幂

1
2
3
4
5
6
7
template <class T>
T quick_power(T x,T y){ // 求x^y
int p = 1;
for(int i = y; i; i >>= 1, x = x * x)
if(i & 1) p = p * x;
return p;
}
  • i >>= 1:即i /= 2,用于不断地向右取幂次数的二进制位。

  • i & 1:用以判断对应这一二进制是否需要进行$\times x^{2^{cnt}}$($cnt$ 为要进行的幂次方数,由 x = x * x 语句决定)处理。

  • 原理即为对于任意的被幂次数都可以写为2进制形式。如$13$可写为$1101$,那么$5^{13} = 5^{2^3\times1+2^2\times1+2^1\times0+2^0\times1}=5^{2^3} \times 5^{2^2}\times 5^{2^0}$

  • 设最开始x值为 $x$,第i次循环x值为 $x_i$,则可以得到 $x_i = x^{2^i}$。

ST表

ST表是一种离线查询表,用以查找特定区间内的最大(最小)值。预处理的时间复杂度为$\text O(n\log n)$,查找时间复杂度为$\text O(1)$,优于线段树(线段树的预处理与查找的复杂度均为$\text O(n\log n)$)。

  • st[x][y] 用以查询区间$[x,x+2^y-1]$内数的最大(最小)值,也就是从 $x$ 开始的 $2^y$ 个数的最大(最小)值。
  • st[x][y]a[x]本身。

预处理(实例中为查找最小值的ST表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int a[1010];//原始输入数组
int st[1010][20];//st表

void init(int n)
{
for (int i = 0; i < n; i++)
st[i][0] = a[i];

for (int j = 1; (1 << j) <= n; j++)
{
for (int i = 0; i + (1 << j) - 1 < n; i++)
st[i][j] = min(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
}
}
  • 1 << j 相当于求出$2^j$的值
  • $\text{st}[x][y] = max/min(\text{st}[i,j-1],\text{st}[i+2^{j-1},j-1])$:将$[x,x+2^y-1]$(指序号大小,下同)分为$[x,x+2^{y-1}-1]$与$[x+2^{y-1},x+2^y-1]$两部分
  • 因为j是从小到大遍历的,所以在得到st[i][j]的值之前,一定会得到st[i + (1 << (j-1))][j - 1]的值

查找(实例为查找最小值)

查找区间$[l,r]$内的最小值:

1
2
3
4
5
int search(int l, int r)
{
int k = (int)(log((double)(r - l + 1)) / log(2.0));
return min(st[l][k],st[r - (1 << k) + 1][k]);
}
  • 有定理: $2^{\log_2 a}>\frac{a}{2}$ 成立。如果设 $t = \log_2{len}$,其中 $len$ 为从 $l$ 到 $r$ 的长度($len = r-l+1$),则有$2^{\log_2len} > \frac{len}{2} \Rightarrow 2^t > \frac{len}{2}$ 成立,所以 $l+2^t$ 跨过了区间的中间位置,那么我们可以得到 $l$ 到 $r$ 的最小值是 $l$向前 $2^k$ 长度区间与 $r$ 向前 $2^k$ 长度区间的最小值的最小值。所以区间 $[l,r]$ 内的最小值为min(st[l][k], st[r - (1 << k) + 1][k])

LCA

  • LCA:最近公共祖先。
  • LCA 的定义可以得到:两点的 LCA 一定是两个点的祖先中深度最大的。那么也就是说两个点如果深度相同的话,他们沿着树向上走x步就可以同时到达 LCA
    • 如果深度不同,则深度较大的向上跳到深度相同的地方。
    • 如果深度相同,则一同向上跳到找到 LCA

倍增法求LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lca(int a, int b){
if(depth[a] < depth[b])
swap(a, b);
int c = depth[a] - depth[b];
for(int i = 20; i >= 0;i--)
if(c & (1 << i)) a = fa[a][i];

// if(u == v) return u;

for(int i = 20;i >= 0;i--)
if(fa[a][i]!=fa[b][i])
a = fa[a][i], b = fa[b][i];

return fa[a][0];
}
  • 其中数组fa[a][x]表示的是对于节点a,向上跳$2^x$次后的父节点。这体现了倍增二分的思想。
  • i从大到小遍历,遍历到了父节点不同就将a,b转移到这个不同的节点,然后继续向上遍历。通过二分法来降低算法复杂度。

ST表求LCA

1563251878821

如上图所示的树,使用DFS遍历$^*$,并对每个点进行编号,得到一下序列:

A B D B E F E G E B A C A
1 2 3 2 3 4 3 4 3 2 1 2 1

$^*$ 不同于一般的DFS遍历,这里的DFS遍历需要记录回溯走过的顶点信息。

则可以得到以下性质:两个点首次出现位置中间这一段中深度最小(也就是值最小)的即为两点的LCA。

所以我们就可以把求LCA转换为求一段序列中的最小值 → 转换为使用ST表求一段的最小值。

所使用的DFS算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int q[1000000];
top = 0;
void dfs(int u, int Fa){
q[++top] = u, sta[u] = top;
for(int i = 1;i <= 30;i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = head[u];i;i = e[i].next){
int to = e[i].to;
if(to == Fa)
continue;
fa[to][0] = u;
dfs(to, u);
}
q[++top] = u,end[u] = top;
}

求LCA的具体算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lca(int a, int b){
int ans = INT_MAX;
begin = 0;
for (int i = 0; i < top; i++){
if (q[i] == a || q[i] == b){
if(!begin)
begin = 1;
else break;
}
if (begin)
ans = min(ans, q[i]);
}
return ans;
}

算法学习:字典树、KMP与AC自动机

字典树

学习自博客:https://blog.csdn.net/qq_42815188/article/details/88677836

字典树(又称为单词查找树,Tire 树)是一种树形结构。它与字典相似,当要查找的一个单词是否在字典树中,首先看单词的第一个字母是否在字典树的第一层。如果不在,说明字典树中没有该单词;如果在,就在该单词的子节点中找是否有单词的第二个字母,如果没有,则说明没有此单词,有的话就继续查找,以此类推。

字典树

字典树有以下的基本性质:

  • 字典树使用边表示字符;(也可以理解为每个节点上保存字符,因为这个边的信息是使用j节点来标识的)
  • 有相同的前缀的单词共用前缀节点;
  • 根结点不包含有字符;
  • 每个单词结束的时候都用一个特殊字符表示,如图中使用的是一个 $ \$ $ 符号;(或者使用数字表示存在该字符串的个数)
  • 从根结点道到一个 $ \$ $ 所经过的所有边的字母就是一个字符串。

字典树常用于统计、排序和保存大量的字符串(不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

优点:利用字符串的公众前缀来节约存储空间,最大限度地减少无用字符串的比较。

构建字典树

编号方案

引入数组tire[][]tire[i][j] = k表示:tire树中编号为i的节点的边上为字母(char)( 'a' + j )的儿子为编号为j的节点(这里不用于一般的树的储存方式)。而这个节点应存储的信息(如这个单词出现了多少次)则单独开一个以编号为下标的数组来记录。

数组编号信息

以此种方式标记好的字典树将如下图所示:(图中的数字指的是这条边结尾处的节点的编号,其中根结点编号为 $0$)。

建树

插入操作

当有新的需要插入的词语(字符串)出现时,我们就依次对比每一个字母在对应层中是否已经出现来判断新进入的词语是否与已经存在的词相同或语有相同的前缀。当出现差异时,我们就标记激活这个节点(标记这个节点为单词词尾节点并将其值(指另一个存储该节点信息的值)加一)。相同词语则直接使词尾节点的值(指另一个存储该节点信息的值)递增。具体操作如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 实例为字符串中只有'a'~'b'26个字母的字典树
#define SIGMA_SIZE 26
// MAXN_NODE根据题意进行赋值
int tire[MAXN_NODE][SIGMA_SIZE] = {0};
int tag[MAXN_NODE] = {0}; // 标记编号为i的节点是否为单词节点
int cnt[MAXN_NODE] = {0}; // 记录编号为i的单词节点所对应的单词出现次数
int node = 0; // Trie树的节点个数

void Insert(string str){
int now = 0; // 用以记录目前遍历到的节点编号
int len = str.length();
for(int i = 0; i < len; i++){
if(!tire[now][str[i] - 'a']){ // 如果这个节点未曾有子节点(前缀出现偏差)
tire[now][str[i] - 'a'] = ++node;
}
now = ch[now][str[i] - 'a'];
}
tag[now] = true;
cnt[now] ++;
}

查询操作

只要建树搞得好,这就莫的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 如果找到则返回词的个数,如果没有找到或无该词则返回-1
int find(string str){
int len = str.length();
int now = 0;
for(int i = 0; i < len; i++){
int c = str[i] - 'a';
if(tire[now][c] == 0){ // 没有子节点了,也就是这个单词不存在实锤
return -1;
}
now = trir[now][x];
}
if(tag[now])
return cnt[now];
else return -1;
}

KMP 算法

学习自博客:https://blog.csdn.net/v_july_v/article/details/7041827

Knuth-Morris-Pratt 字符串查找算法,简称 KMP 算法,常用在于一个文本串S内查找一个模式串P的出现位置,这个算法由Donald KnuthVaughan PrattJames H. Morris三人联合发表,故取这三个人的姓氏命名此算法。

传统的模式串匹配使用的是纯暴力匹配算法。

纯暴力匹配

  • 如果当前字符匹配成功(S[i] == P[j]),则i++j++,继续匹配下一个字符;
  • 如果没有匹配成果(S[i] != P[j]),则令i = i - (j - i)(回溯到开始匹配的字符的下一个字符)、j = 0,重新匹配模式串。

如以下的图解(假设文本串S = "BBC ABCDAB ABCDABCDABDE",模式串P = "ABCDABD"):

  • 首先从第0位开始匹配:

    匹配第0位

    发现匹配不成功,则匹配串右移。

  • 匹配文本串的第1位:

    匹配第1位

    发现依旧不匹配,继续将匹配串右移。

  • 直到出现了一次匹配(匹配串移动到了第4位):

    第1位匹配成功

    发现匹配成功,则i++j++。对下一位进行匹配。

  • 将文本串的第5位与匹配串的第1位匹配:

    第2位匹配成功

    发现匹配成功,继续i++j++。对下一位匹配,直到出现不能匹配的项。

  • 再次出现不能匹配的项:

    出现失配

    发现匹配不成功,则匹配串右移,重新从匹配串的第一位开始进行匹配。

  • じゃ、もう一度!

    重新匹配

从示例可以看出,这种匹配模式下,每次出现错误的匹配都需要回溯到词头再进行匹配,十分的低效,算法复杂度也到了$O(m\cdot n)$。如果我们在进行匹配的时候,能基本做到不进行回溯而只移动模式串的话,算法复杂度将极大地提升。

KMP算法匹配字符串

让我们回到起点重新进行模式串匹配:

  • 首先匹配文本串的第0位:

    KMP匹配第0位

    发现匹配不成功,则匹配串右移。

  • 匹配文本串的第1位:

    KMP匹配第1位

    发现依旧不匹配,继续将匹配串右移。

  • 直到出现了一次匹配(匹配串移动到了第4位):

    KMP第1位匹配成功

    发现匹配成功,则i++j++。对下一位进行匹配。

  • 将文本串的第5位与匹配串的第1位匹配:

    KMP第2位匹配成功

    发现匹配成功,继续i++j++。对下一位匹配,直到出现不能匹配的项。

  • 再次出现不能匹配的项:

    KMP失配

    发现匹配不成功,则匹配串右移,重新从匹配串的第一位开始进行匹配。

这时我们考虑,真的要回溯到文本串的第5位然后重新开始与模式串的第一位进行比较么?我们可以发现我们已经匹配了的部分中有一段字符串"AB",而模式串的前缀中也有"AB"。也就是说,其实我们可以认为已经将模式串的前两位匹配成功了,我们只需要继续匹配模式串的第2位(从0开始编号)就可以了。

  • 不进行回溯而将模式串右移一定的位:

    KMP回溯

    发现匹配错误,将模式串继续移位。

  • 移位将字符串的第10位与模式串第0位进行匹配:

    KMP回溯

  • 发现匹配错误,移位对字符串的下一位进行匹配。

  • 移位将字符串第11位与模式串第0位进行匹配:

    KMP再次回配

    发现匹配成功。则i++j++,进行下一位匹配。以此类推,直到再次发生不能匹配。

  • 直到再一次发生匹配失败:

    KMP失配

    情况与上一次相似,都是出现在了'D'位,所以模式串向右移动。

  • 模式串向右移动四位:

    KMP回溯&再再回配

    发现匹配成功,则不断的i++j++

  • 匹配完成:

    KMP最终匹配成功

这种匹配方式下,字符串完全不需要进行回溯,只需要将模式串进行一定量的右移就可以得到最终结果。这是一种高效的模式串匹配方法。算法的时间复杂度仅为 $O(m + n)$。

那么这个算法的重点就是在于:模式串应该如何的右移,也就是当发生匹配失败时,我应该去匹配模式串的哪一位?所以我们引进了next[]数组。

从我们过程的分析中可以发现,我们判断需要将模式串向右移动几位是依据我们的模式串的开头部分与结尾部分中是否有重复出现的一部分,如果存在,我们就可以移动模式串使着相同的部分重合,从而节省了前面一段部分的匹配。所以我们要找出这一位以前(包括这一位)前缀与后缀的数量的这个子串中出现的最长的具有相同元素的前缀与后缀。我们可以得到如下表格:

模式串的各个子串 前缀 后缀 最大公共元素长度
A 0
AB A B 0
ABC A, AB C, BC 0
ABCD A, AB, ABC D, CD, BCD 0
ABCDA A, AB, ABC, ABCD A, DA, CDA, BCDA 1
ABCDAB A, AB, ABC, ABCD, ABCDA B, AB, DAB, CDAB, BCDAB 2
ABCDABD A, AB, ABC, ABCD, ABCDA, ABCDAB D, BD, ABD, DABD, CDABD, BCDABD 0
字符 A B C D A$_1$ B$_2$ D
最大前缀后缀公共元素长度 0 0 0 0 1 2 0

nect[]数组的作用是,重复到拥有相同前缀的位置。所以我这一位要回到哪里要看的是这一位之前的字符串中最长长度的拥有的相同的前后缀的长度为多少。而对于第一位,他之前没有字符串,所以我需要做的是将字符串右移一位然后进行重新匹配,所以next[0]的值应为 $-1$ 。所以next[]数组的值即为将最大前缀后缀公共元素长度表的内容全体后移一位然后将第0位赋值成 $ -1$ 即可!示例的next[]数组如下:

字符 A B C D A$_1$ B$_1$ D
next[]对应位的值 -1 0 0 0 0 1 2

而在求模式串的next[]数组的过程中,我需要找到模式串子串的前后缀,即比对模式串子串与模式串是否有相同部分的内容,同样可以使用KMP算法,所以我们在求后面几位的next[]时完全可以用到前面几位的next[]的值。

求得next[]数组的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void GetNext(string p,int next[])
{
int p_len = p.length();
next[0] = -1;
int k = -1;
int j = 0; // 标记目前在计算第几位的next值
while (j < p_len - 1){
//p[k]表示前缀,p[j]表示后缀
if (k == -1 || p[j] == p[k]) { // 初始状态或者需要右移或者匹配成功
++k;
++j;
next[j] = k;
} else {
k = next[k]; // 匹配失败
}
}
}

在使用KMP算法匹配字符串的算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int KMPSearch(string str, string p){
int i = 0, j = 0;
int str_len = str.length();
int p_len = p.length();
while (i < str_len && j < p_len){
if (j == -1 || s[i] == p[j]){ // 如果需要后移或者匹配成功
i++;
j++;
}else{ // 如果匹配失败
j = next[j];
}
}
if(j == p_len) // 匹配成功
return i - j;
else return -1; // 匹配失败
}

AC 自动机

学习自博客:https://blog.csdn.net/bestsort/article/details/82947639

AC自动机是以字典树作为搜索数据结构,利用KMP原理减少回溯的操作,以实现多模式串匹配。算法复杂度优化到了 $O(n)$。

AC自动机就是在字典树的基础上,增加上一个fail指针,如果当前点处匹配失败的话,就将指针转移到fail指针所指的位置,来减少没有必要的回溯。(类似KMP中的next[]的作用)

如我现在有待匹配的串,为"shershisher"。我现在有模式串"hers""hrs""she",形成如图所示的字典树:

形成字典树

fail指针的作用就是在我出现匹配失败的时候,我能立刻转移到相近的能继续匹配下去的串而不需要重新再来。所以我们需要找出在不同模式串中前缀匹配的部分。fail指针的构建都是用BFS来实现的,基本的操作就是指向节点的父节点fail指针所指向的节点的子节点中与其相同的节点,如果没有,则指向它父亲节点的fail指针指向的节点。以如图所示的字典树,我对他进行fail指针构建:

  • 第一层遍历,每个串的首字母肯定是指向根节点:

    第一层遍历

  • 第二层遍历,我们瞄准最左面的子树的第一个节点(被e指向的绿色节点):

    应指向他的父节点(h指向的橙色节点)的fail指针指向的节点(蓝色的根结点)的子节点中指向边为e的节点,不存在,所以指向他父节点的fail指针指向的节点(根结点)

    第二层第一节点

  • 第二层的第二个节点,相同。接下来看第三个节点(被h指向的绿色节点):

    应指向他的父节点(s指向的橙色节点)的fail指针指向的节点(蓝色的根结点)的子节点中指向边为h的节点(h指向的橙色节点)。所以得到如下图:

    第二层二三节点

  • 依次如此作图,最终得到如下图(有点乱):

    AC自动机

在我进行字符串"shershisher"匹配时,首先匹配"she"成功,ans++e之后没有字符继续匹配,所以指向fail指针指向的另一个e即开始匹配"hers",匹配成功,ans++。后s指向最右侧树的s,开始匹配"she",匹配到h后失配,所以指向fail开始匹配"hers",到s匹配失败。所以最终结果为 $2$。

算法学习:搜索

深度优先搜索(DFS)

DFS是一种使用栈结构的搜索方式,一般使用递归实现(因为递归就是在压栈嘛)。一般用于判断是否图是否连通或找到图的拓扑序来解决更多的图论问题,最基础使用DFS的问题就是迷宫问题。在进行搜索时,不断地向深处找下一个节点,如果没有下一个节点或下一个节点已经被访问的话,就回溯到有下一个节点可访问的点继续搜索。

如下图所示的图:

1563515220039

它的DFS遍历顺序为:$1 \rightarrow 2 \rightarrow 3\rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 9$(这个真的只是巧了)。

有的时候还需要得到带有回溯的DFS序,如图就为:$1\rightarrow 2\rightarrow 3 \rightarrow 4\rightarrow 5\rightarrow 4\rightarrow 6\rightarrow 7\rightarrow 6\rightarrow 8\rightarrow 9\rightarrow 8\rightarrow 6\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 1$

但DFS不仅仅只有搜索图那么简单还可以解决一些实际问题。如下题目(POJ 3900):

一个劫匪带着一个可装 $m$ 重量的超大背包去抢银行,银行有 $n$ 个大箱子,第 $i$ 个箱子里有 $i$ 个重量为 $w_i$ ,价值为 $c_i$ 的大钻石,问该劫匪抢走钻石的最大价值。(一共有 $T$ 组数据)

HINT

$1\leq T \leq 74$;

$1 \leq n \leq 15$;

$1 \leq m \leq 1000000000\ (10^9)$;

$1 \leq w_i, c_i \leq 1000000000 \ (10^9)$。

这道题看上去是一个01背包问题,但由于数据量巨大,无法开那么大的数组,所以只能使用DFS搜索。所以能够得到下面这段DFS代码:

1
2
3
4
5
6
7
8
9
void dfs(int pos, long long nowcost, long long lastw){
// pos:搜索的位置 nowcost:当前抢走的总价值 lastw:背包剩余的空间
if (pos == n || lastw <= 0) // 如果搜到了最后一个箱子或者没空间了
return;
ans = max(ans, nowcost);
for (int i = a[pos].num; i >= 0; i--){ // 对每个箱子一个一个钻石的查
dfs(pos + 1, nowcost + i * a[pos].c, lastw - i * a[pos].w);
}
}

但这样太暴力了!TLE预定系列。所以我们要对我们的DFS进行一定的优化。

深度优先搜索的优化

剪枝:对不满足条件的情况进行清除,减少算法所需要的时间,分为以下两种:

  • 可行性剪枝:判断搜索能否得出答案,如果不能的话直接回溯。
  • 最优性剪枝:又称为上下界剪枝,是一种重要的剪枝策略。它记录当前得到的最优值,如果当前节点已经无法产生比当前最优解更优的解时,可以提前回溯。

以上一个题目为示例,我们考虑它可能出现的剪枝方法:

  1. 在枚举时,如果出现了$w_{\text{当前要去取的}} > w_{\text{背包剩余的}}$,则直接跳过:

    1
    if (i * a[pos].w > lastw) continue;

    这是一种可行性剪枝

  2. 在枚举时,如果$c_\text{已经拿了的} + c_\text{还没有拿的箱子的全部钻石} < ans$,则不可能会出现更优解,所以回溯:

    1
    if (nowcost + sum[pos] < ans) return;

    这是一种最优性剪枝

  3. 在枚举时,设矿物的性价比为 $s$ ,$s_i = \displaystyle\frac{c_i}{w_i}$。如果 $w_\text{背包剩余的} * s_\text{还未偷的最大的} < ans$,则不可能出现最优解,所以回溯。如果要石用这个剪枝的话,则要求在开始时就将这 $n$ 个箱子按照性价比从高到低进行排序,而 $n$ 的最大值也就只有 $15$ ,所以时间复杂度不高,完全可以满足要求。

    1
    if (nowcost + (long long)ceil(a[pos].s * lastw) < ans) return;

    这是一种最优性剪枝

另一个可以优化的搜索题目(POJ 1088):

题目描述

Michael 喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:
$$
\begin{eqnarray}
& 1 & 2 & 3 & 4 & 5 \\
& 16 & 17 & 18 & 19 & 6 \\
& 15 & 24 & 25 & 20 & 7\\
& 14 & 23 & 22 & 21 & 8 \\
& 13 & 12 & 11 & 10 & 9
\end{eqnarray}
$$
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。

记忆化搜索:记录以前搜索所得到的结果,当我搜索其他位置而需要这个位置的值时,我就可以直接使用这个值而减少搜索时间。

如在这个题目中,每个点到最低点的最优解是一定的,所以我在遍历的过程中可以记住已经遍历出结果的点,这样就可以节省很多的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int dfs(int x, int y){
if (f[x][y] != 0) // 已经记录了这个点的结果
return f[x][y];
int maxt = 1; 用以计数
int t; // test 用以记录中间结果
for (int i = 0; i < 4; i++){ // 上下左右四个点
int tx = x + dx[i], ty = y + dy[i]; // dx[] 与 dy[] 是用来记录得到四个点坐标的操作数组
if(tx > 0 && ty > 0 && tx <= r && ty <= c && hill[tx][ty] > hill[x][y]){
t = dfs(tx, ty) + 1;
maxt = max(t, maxt);
}
}
f[x][y] = maxt; // 记忆化
return maxt;
}

广度优先搜索(BFS)

BFS是一种使用队列实现的搜索算法,每次搜索对一层的节点进行搜索,所以最后呈现出来的结果是一圈一圈地扩大,具体过程如下图所示(其中Q为当前的队列信息,标有阴影的边为BFS算法所走过的边):

1563521989690

由于BFS是一层一层地进行搜索,所以BFS很适合进行搜索到一个点最少步数类型的搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int stepArr[4][2] = {{-1, 1, 0, 0}, {0, 0, -1, 0}}; // 方向数组:分别为上下左右移动
int visited[x][y]; // 标记是否已经被访问
struct Node{
int x;
int y;
int step;
Node(int x1,int y1,int step1):x(x1),y(y1),step(step1){} // 生成节点的函数
};
Node node(0,0,0); // 生成一个节点
queue<Node> q;
int BFS(){
q.push(node);
while(!q.empty()){
node = q.front();
q.pop();
if(node.x == n-1 && node.y == n-1){
return node.step;
}
visit[node.x][node.y] = 1;
for(int i=0; i < 4; i++){
int x = node.x + stepArr[i][0];
int y = node.y + stepArr[i][1];
if (x >= 0 && y >= 0 && x < n && y < n && visit[x][y] == 0 && 其它条件 ){
visit[x][y] = 1;
Node next(x,y,node.step+1);
q.push(next);
}
}
}
return-1;
}

广度优先搜索的优化

  • 双向广搜:从初状态和末状态两端进行广搜,直到两区域开始重叠或者有公众节点结束

    如果一个节点产生的系统呈二叉树式增长,那么对于扩展 $n$ 次的代价, 单向为 $2^n$,而双向则是 $2 * 2^\frac{n}{2} = 2 ^{\frac{n}{2} + 1}$

  • 利用散列表(Hash表)记录状态,避免遇到相同状态而增加搜索时间

如以下题目(洛谷P2730):

题目背景

在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有8个大小相同的格子的魔板:
$$
\begin{eqnarray}
&1&2&3&4 \\
&8&7&6&5
\end{eqnarray}
$$

题目描述

我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。对于上图的魔板状态,我们用序列(1,2,3,4,5,6,7,8)来表示。这是基本状态。

这里提供三种基本操作,分别用大写字母“A”,“B”,“C”来表示(可以通过这些操作改变魔板的状态):

“A”:交换上下两行;

“B”:将最右边的一列插入最左边;

“C”:魔板中央四格作顺时针旋转。

下面是对基本状态进行操作的示范:

A:
$$
\begin{eqnarray}
&8&7&6&5 \\
&1&2&3&4
\end{eqnarray}
$$
B:
$$
\begin{eqnarray}
&4&1&2&3 \\
&5&8&7&6
\end{eqnarray}
$$
C:
$$
\begin{eqnarray}
&1&7&2&4 \\
&8&6&3&5
\end{eqnarray}
$$
对于每种可能的状态,这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到目标状态的转换,输出基本操作序列。

A、B、C三种操作我们可以找到规则,写为函数来进行模拟,于是这样进行BFS。重点在于我们如何记录每一个状态。如果我们保留这8位数存储,使用一个8位的bool数组存储,判重时需要接近 $10^8$ 的布尔数组,空间接近200M,肯定超过限制。而我们最终需要的结果是操作的序列,所以我们不如使用操作序列来记录所有的状态。

所以有以下的AC代码(摘自洛谷巨佬getchar123):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
string a;#include<bits/stdc++.h>
using namespace std;
string a;
map<string,string>m;
queue<string>q;
void A(string x){
string xx=x;
for(int i=0;i<4;i++){
char x1=x[i];
x[i]=x[7-i];
x[7-i]=x1;
}
if(m.count(x)==0){//没有出现过
q.push(x);
m[x]=m[xx]+'A';
}
return;
}
void B(string x){
string xx=x;
x[0]=xx[3],x[1]=xx[0],x[2]=xx[1],x[3]=xx[2],x[4]=xx[5],x[5]=xx[6],x[6]=xx[7],x[7]=xx[4];
if(m.count(x)==0){
q.push(x);
m[x]=m[xx]+'B';
}
return;
}
void C(string x){
string xx=x;
x[1]=xx[6],x[2]=xx[1],x[5]=xx[2],x[6]=xx[5];
if(m.count(x)==0){
q.push(x);
m[x]=m[xx]+'C';
}
return;
}
void bfs(){
q.push("12345678");
m["12345678"]="";
while(q.empty()==false){
A(q.front());
B(q.front());
C(q.front());
if(m.count(a)!=0){//当出现目标序列
cout<<m[a].size()<<endl<<m[a];
return;
}
q.pop();
}
return;
}
int main(){
for(int i=0;i<8;i++){
char a1;
cin>>a1;
a+=a1;
getchar();
}
bfs();
return 0;
}
map<string,string>m;
queue<string>q;
void A(string x){
string xx=x;
for(int i=0;i<4;i++){
char x1=x[i];
x[i]=x[7-i];
x[7-i]=x1;
}
if(m.count(x)==0){//没有出现过
q.push(x);
m[x]=m[xx]+'A';
}
return;
}
void B(string x){
string xx=x;
x[0]=xx[3],x[1]=xx[0],x[2]=xx[1],x[3]=xx[2],x[4]=xx[5],x[5]=xx[6],x[6]=xx[7],x[7]=xx[4];
if(m.count(x)==0){
q.push(x);
m[x]=m[xx]+'B';
}
return;
}
void C(string x){
string xx=x;
x[1]=xx[6],x[2]=xx[1],x[5]=xx[2],x[6]=xx[5];
if(m.count(x)==0){
q.push(x);
m[x]=m[xx]+'C';
}
return;
}
void bfs(){
q.push("12345678");
m["12345678"]="";
while(q.empty()==false){
A(q.front());
B(q.front());
C(q.front());
if(m.count(a)!=0){//当出现目标序列
cout<<m[a].size()<<endl<<m[a];
return;
}
q.pop();
}
return;
}
int main(){
for(int i=0;i<8;i++){
char a1;
cin>>a1;
a+=a1;
getchar();
}
bfs();
return 0;
}

A*算法

(看到这里请提醒博主填完这里或者删掉

算法学习:基础数据结构

单调队列、树状数组、差分队列与线段树。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×