A=B 第三章题解

评论

前言

这个关键字相当于在找到特定的子字符串之后,删去该子字符串,并且将我们指定的新字符串插入到原字符串的开头与结尾

类似于正则表达式的^与$的应用

很像是我们在第二章的操作:将字母压之后换成其他字母往后排以使得压缩持续进行

3-1 去除

相当简单的教程

1
2
(start)a=
(end)a=

3-2 旋转

这里只针对前面不是a进行操作,可以保证

1
2
(start)b=(end)b
(start)c=(end)c

3-3 A到B 2

思路

开始上难度了,但是其实不难,我们只需要先把所有特定位置的a变成特殊的,然后再处理另一边的特殊的即可

就像是我们之前做过的一样,此时的代码如下

1
2
3
4
5
6
(start)a=x
xa=ax
(end)a=z
az=za
x=b
z=b

优化

我们很容易注意到我们的xa=ax或者之类的操作只是把所有符合要求的串找出来,保证不阻塞生成

于是我们注意到移到另一边的位置显然更好(指行数更小),更新之后如下

代码

1
2
3
4
(start)a=(end)x
(end)x=(start)b
(end)a=(start)x
(start)x=(end)b

3-5 首尾

通过上一题我们就知道弄到尾部直接判断即可

我们唯一要注意的就是判断在前,不然容易出死循环

1
2
3
4
5
6
7
8
9
ax=(return)true #有任意一个就是真的,能迅速检查到
by=(return)true
cz=(return)true

#以下的操作会1.在有相同的时候把除了最后一个字母之外都换成其他字母插入到后面 2.没有相同的时候所有都插入到后面
(start)a=(end)x
(start)b=(end)y
(start)c=(end)z
=(return)false

3-6 最多 2

思路

与之前的类似,但是我们需要保留所有作比较的字母来保证恢复,然后这里其实就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ca=ac
cb=bc
ba=ab
ab=(end)x
cx=(end)y #y代表abc,可随时换成最多的 #剩下ac和bc
#之后我们不用关心y具体是什么,只要二者消耗,剩下的那个做全员回复就行

ac=(end)y
bc=(end)y
#做一个穷举
ax=aa
cy=cc
by=bb
ay=aa
bx=bb

优化

发现ax,ay的行为是相同的,bx,by也是,优化以下

1
2
3
4
5
6
7
8
9
10
11
12
13
ca=ac
cb=bc
ba=ab
ab=(end)x
cx=(end)y #y代表abc,可随时换成最多的
#acy bcy ay by cy 

ac=(end)y
bc=(end)y
x=y
cy=cc
by=bb
ay=a

3-7回文串

思路

判断是不是消除之后全空即可,如3-5的加强版,我们进行全局替换,然后穷举非空情况,但是注意我们不用考虑剩下来的单个字母的情况,因为那种情况也属于回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
cz=
by=
ax=
(start)a=(end)x
(start)b=(end)y
(start)c=(end)z
xy=(return)false
xz=(return)false
yx=(return)false
yz=(return)false
zx=(return)false
zy=(return)false
=(return)true

挑战优化

注意到我们六行代码目的都只是为了判断是否有两个字母及以上存在

修改字符串使之存在首尾标识符即可,也就是说能保证显示出来两个字母不同且存在

1
2
3
4
5
6
7
8
cuZn=
buYn=
auXn=
(start)a=(end)uXn
(start)b=(end)uYn #不影响排空
(start)c=(end)uZn
nu=(return)false  #出现这个说明仍有多个字母存在,整个字符串非空,
=(return)true

Noirking's Pawn

个人简介。