A=B 第二章题解

评论

前言

我们要好好理解一下a=(return)b干了啥:

  1. 找到匹配的字符串a
  2. 将整个我们的字符串变成b
  3. 中断循环,看结果

换成函数表达就是

1
2
3
if a in s:
	s=b
	return s

之后判题的只能看到你返回的字符串b

2.1 你好世界

这里给出来了一个提示,在我们用空等的时候

1
=(return)helloworld

2.2 AAA

思路

我们需要看a的数量,也就是说我们不用管b,c,将二者全消除之后剩下的就是a,再看其是否大于等于3个即可

代码

1
2
3
4
b=
c=
aaa=(return)true
=(return)false

2.3 恰好三个

思路

不用管到底是哪个字符,我们只需要验证是不是三个字符即可,所以先把所有字符变成一样的,例如c

接下来我们要判断的不是ccc=(return)true,因为字符串cccc同样包含ccc,

  • 我们首先就排除掉大于3个字符的,其一定包含四个及以上的字符串
  • 这时候对只有三个字符的返回true
  • 剩下的也是false

代码

1
2
3
4
5
a=c
b=c
cccc=(return)false 
ccc=(return)true  
=(return)false

2.4 余数

思路

这个是return使用的一个示例,所以我们考虑的仍然是只关心字符串长度,不关心内容

  1. 将所有都替换成同样的字符
  2. 发现求的事余3,我们只需要每次都将三个字符的串放空,剩下的字符串长度就是总长度余3的结果
  3. 将长度换成数字

代码

这个思路在后续也有用

1
2
3
4
5
6
a=c
b=c 
ccc=           
cc=(return)2
c=(return)1
=(return)0

2.5 奇数

思路

划分问题

终于开始上难度了,但是这个 思想其实不难理解,我们先做一个简单的想法,我如何判断一长串a是否由奇数组成?

  1. 考虑到字符串长度为1<=n<=7,很容易知道0,1,3,5,7为可能的长度
  2. 暴力枚举虽好,但是长度有点太大了,我们可以用另一个方法:奇数减去2之后仍然为奇数
  3. 所以我们很容易想到aaa=a来清理串,为什么不能是aa=?
    1. 因为这样没有办法确认是刚开始就没有a,还是被偶数a消除掉的
  4. 此时长度0,1,2,只有2表示原串是偶数

做法

然后我们知道要去做什么了:把三个字符串相同的集中在一起,相当于按顺序再为这三个字符轮流做上述检查操作

所以需要排序,让相同字符待在一起

接下来问题就好解决了

代码

1
2
3
4
5
6
7
8
9
10
ba=ab
cb=bc
ca=ac
aaa=a
bbb=b
ccc=c
aa=(return)false
bb=(return)false
cc=(return)false
=(return)true

进阶

你肯定要回来看的,如果你看不懂2.6的话

发现了什么?我们将同样的情况循环了3遍,也就是说,在单独讨论的时候a,b,c其实是等价的,有没有什么办法将它们的等价用代码解释出来?

一个很有趣的想法是将b,c转换成等价a,最后判断三段a是否都满足奇数

一点点魔法:设置一个障碍,让所有相邻相同的字母没有障碍,而让不同的字母之间有障碍

考虑如下代码的运作

1
2
3
4
5
ba=ab
cb=bc
ca=ac
b=xxax
c=xaxx

这种情况下会发生什么:相邻的b变成了中间隔着3个x的a,不同字母之间隔着2个x

更加显式地能看到假设 bacacc:

1
2
3
aabccc
-> aaxxaxxxaxxxaxxxaxx
-> a|a| xxax |xaxx|xaxx|xaxx

仔细观察,发现相隔3个x的都能去掉!,此时会变成用两个x阻隔的三个段,每个段里面的a的个数是a或b或c的个数,此时bacacc变成aaxxaxxaaaxx

然后判断即可

得出来新的代码如下

1
2
3
4
5
6
7
8
9
ba=ab
cb=bc
ca=ac
b=xxax
c=xaxx
xxx=
aaa=a #等价处理
aa=(return)false
=(return)true

这种等价思想很重要,在之后会多次使用

其实这种等价想法在于什么:在于让相同字母之间的间隔一样,不同字母的间隔不一样,以这种思路你完全可以设计如下方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#其中()表示重复几次
b=x(n)ax(m)
#则c和b之间的距离也应为n,b和b之间距离为m+n
#所以
c=x(n-m)ax(2m)
#符合以上要求的都可以替换
#比如以下代码n=6,m=3,一样可以通过
ba=ab
cb=bc
ca=ac
b=xxxxxxaxxx
c=xxxaxxxxxx
xxxxxxxxx=
aaa=a
aa=(return)false
=(return)true

2.6 独一无二

思路

这里建议先看一下上面的拓展

然后我们先翻译一下题目:希望这个长字符串出现的单字符字符串有且只有一个:

  • aaabccc:只有一个a,是我们需要的
  • aaabacc:b和a都有,是错误的
  • 实际上我们要做的是在aaa=aa;bbb=bb;ccc=cc之后,看单个的不成对字母有几个

我们只需要知道是不是等于1

和上题拓展法类似,我们等价之后再做类似操作,现在得出来的因为没有排序,我们现在能保证的是

  1. 相同字母之间x个数为0或者3
  2. 不同字母之间x个数为1或者2

由上述两条我们将串收敛一下,把相等相邻的聚在一块,然后格式一下彼此之间距离

此时出现的就是axaaaxaaxa之类的东西,更进一步地,我们将所有长串都收成空串

此时我们要找的是此时里面是不是只有一个a

看到a就return肯定不行,但是我们能先把多个a存在的删掉,其格式一定为axaxa之类,因为我们上述操作不相同的单字符串串之间一定有一个x阻隔

这时候就有只剩下a的情况了,此时是我们想要的

剩下的情况就是全是长串,也是我们不想要的

代码

1
2
3
4
5
6
7
8
9
b=xxax
c=xaxx
xxx= #这之后相邻的同字符的串就是相邻的a
xx=x #此时不同串之间相差1x
aaa=aa 
aa= #两步除长串
axa=(return)false
a=(return)true
=(return)false

2.7上升

思路

排序

  1. 做之后还会有效的两两对比
  2. 先确定是不是c比d多,再确定是不是b比a多
  3. 建议先看下面的两个

实现上面的体现

  1. c比b多则b全部化为d,此时还有c剩余
  2. d比a多则a全消失,d还有剩余
  3. 也就是说dc存在的时候其实是(bcc)还有剩,合法性足够强
  4. 我或许需要一些更加显然的理解,但是现在没有...以后可能试试
1
2
3
4
5
6
7
8
ca=ac
cb=bc
ba=ab #先排序
bc=d   #合法情况是adc
bd=db  #此时d代表的是bc
ad=    #消去abc 此时如果合法一定是dc
dc=(return)true
=(return)false #其他就都不合法

2.8最多

思路

  1. 对于这种考虑总体字母的,我们先把他们放在一起,先排序
  2. 我们考虑到排序,所以我们只要比较三者的多少,很明显能考虑到两两对比
  3. 接下来我们最好看代码讲解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
ca=ac
cb=bc
ba=ab #先排序

bc=d    
bd=db  #此时d代表的是bc
ad=    #消去abc,接下来剩下的就只有一个或两个字母,一定,而且不是bc,把三种组合罗列一下就是结果,只有一个字母显然是答案
ac=
ab=

a=(return)a
b=(return)b
c=(return)c

2.9最少

思路

思路与上面的类似

直接看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
ca=ac
cb=bc
ba=ab #先排序

ab=d
db=bd
dc=  #销去了abc,可能剩下ad,ac,bc
 
d=(return)c #d存在说明d比c多,也就是ab组合都比c多
ac=(return)b 
bc=(return)a

Noirking's Pawn

个人简介。