Markov Algorithm Online

接触了一种全新游戏.

规则

这是一种简单的语言,只有两个语句:
a:b:把字符串a替换成b.
a::b:把字符串a替换成b,程序结束.

(模式/替换的前导/尾随空格会被直接忽略)

执行顺序:每次都是先执行前面的语句,如果第一句找到了就执行第一句,然后从头开始接着执行(中间执行了::会直接结束的).

题解

0001

直接替换.

Hello,:World!
//或
Hello,::World!

0002

删除所有的s

s:

0003

把s加在头上(注意只能执行一次防止死循环)

::s

0004

剪刀石头布,对每种情况进行替换,注意每种只能执行一次.

R::P
P::S
S::R

0005

给一堆只有i的串,在每个之间插一个w.
也就是把所有ii换成iwi.

ii:iwi

0006

对ABC进行排序,枚举三种将要进行的排序准则分别替换即可.

BA:AB
CB:BC
BA:AC

0007

给一段o判断有奇数个还是偶数个.
发现两个o没有贡献,直接消掉,最后判断即可.

oo:
o::odd
::even

(注意先判有的odd,因为even是兜底的)

0008

给一段只有b的串,加一个s在末尾.
首先考虑bb变成bsb,然后掉转顺序变成bbs,最后删掉所有的bsb.写出来长这样:

bb:bsb
sb:bs
bsb:bb

考虑顺序优化.每次查子串是从第一句开始查,也就是符合条件的语句编号越小越优先执行,调整一下:

sb:bs
bb:bsb
bsb:bb

这个时候我们发现,他变成了一直往尾部加s,一个,两个…
我们让b变成bs,然后把sb:bs的交换优先级调整的比添加高,就可以顺到最后了,然后ss::s结束.(bb:bsb会WA,只有一个b的情况)AC代码:

ss::s
sb:bs
b:bs

0009

给一个二进制串,按位反转.
交换,肯定有个tmp的防止反转再反转,于是0先换成2,再换成1,1也一样,调一下优先级.

发现死循环了.注意到,即使是结果也是可以当输入的,我们要手动结束程序,于是考虑扫描,从左插一个a,每次枚举a左边的进行反转,a到头结束.

a0:1a
a1:0a
a::
:a

0010

写一个加法器.
我们需要插一个东西在末尾.我们如何判定他插到末尾了?
答: 插两个的时候.(第一个不动了说明到头了,第二个到头的时候会碰到第一个)
然后程序向前遍历就很好写了.

0ss::1
1ss:ss0
ss::1
s0:0s
s1:1s
:s

0011

计数.
首先,每一个o都是看成1,进位的时候直接放到左边.
数之间不允许直接加,否则会乱位,于是调整一下o变成1的优先级即可.

0o:1
1o:2
2o:3
3o:4
4o:5
5o:6
6o:7
7o:8
8o:9
9o:o0
o:1

0012

会11的话12就很简单了.反向搞就行,注意0作为进位标志最后再摘.

1:0o
2:0oo
3:0ooo
4:0oooo
5:0ooooo
6:0oooooo
7:0ooooooo
8:0oooooooo
9:0ooooooooo
o0:0oooooooooo
0:

0013

0014

0015

0016

比5长的直接迭代缩减即可.

oooooo:ooooo

0017

比5短的直接迭代增加即可.

ooooo::ooooo
:o

0018

判断ox序列哪个多,输出win,lose,draw.
难点在于6行内完成.题解借用很长一段x保证xo一定能消掉o,从而完成消掉另一方,然后再归还x,多就是输,默认赢,不变就是平手.

xo:
win+xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx:lose+
win+xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx:draw+
+x:+
+::
:win+xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

0019

发现排好序一定是12345,考虑如何把12345搞掉:

1:
2:
3:
4:
5::12345

0020

给一个数字串,在每两个数字间加点.
直接扫描即可.

a0:0.a
a1:1.a
a2:2.a
a3:3.a
a4:4.a
a5:5.a
a6:6.a
a7:7.a
a8:8.a
a9:9.a
.a::
:a

0023

给一个数列(只有012),求他们的和模3.
显然暴力是会超行的,考虑替换,把0替换成111,2换成11就可以很简单的消除了.但是注意一个小坑是111:错1111:1对,因为假如最后没数字了就寄了.

0:111
2:11
1111:1
111::0
11::2

0032

发现值域很窄,直接枚举.

xo:x
oooooooooooooooooooooooooooooooo:5x
oooooooooooooooo:4x
oooooooo:3x
oooo:2x
oo:1x
o:0x
x::

0035

把第三个字符替换成x.

ooo::oox

0036

把倒数第三个字符替换成x,插一个a,扫到末尾结束.

ao:oa
oooa::xoo
:a

0037

直接替换,注意第一个问号的优先级是最低的.

m?:ma
a?:ar
r?:rk
k?:ko
o?:ov
?:m

0038

发现转移的时候多余的o会没,但是最终状态的o也会跟着没,考虑扫描.

xbob:oxb
xb:x
xo:x
x::
:x

0045

直接删掉-即可.

-:

0048

找最大公因数即可.

ooo:oof
oofoofoofoofoof:oofobfoofbofooz
oofoofoofo:oofobfoofb
oofoo:oofob

0049

直接替换.

bb:ba

0050

替换小心头部重复替换.

aa:ba
bbb:bab

0051

扫描一遍即可.

zab:baz
z::
:z

0052

来一个被减数,左右对消即可.

ozo:z
z::
:ooooooooooz

0053

这里开始是几道闪电题,意思是尽快做出来而不是压行做出来,题目也非常难.

xoo:ox
x::
:x

0054

0061

冒号不能动,右边减一个左边加一个即可.

(:
::(

0062

考虑整体转变,00先变成01再一个变成00.

00:01
01::00

0063

打印空格.由于前导/尾随空格都会没,我们要构造两面包夹的形态.

114514:
1919810::
:114514 1919810

0064

我们要去掉中间的空格,显然扫描线做.
注意到我们开头要插入一个没空格的,这里是没法转移的.我们考虑插一个形如x y的结构,然后再把y去掉,就可以成功转移了.

x a:ax
x b:bx
x c:cx
y:
x::
:x y

0069

注意到数据是4个t起手,考虑做一个头然后沿伸.

testtt:testtest
tttt:testtest

0078

直接查找.

iwi::[iwi]

0079

最优解只有四行,而且结果可以作为输入,只好使用扫描线.但是扫描头添加(2),转移(2),检测(1),超了,要魔改.

鉴于只有iw,可以构造:很多iiiiii,然后不用转移ii,转移iw,就结束了.正好四行.

iiiiiiiiiiiiiiiiiiiiiiwi:[iwi]iiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiw:wiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiii::
:iiiiiiiiiiiiiiiiiiiii

0080

发现拆括号的过程就是放到外面然后乘二即可.

o]:]oo
[]:

0083

判断子序列是否含有 2021 .
一个很naive的想法是,开局插一个字母,然后遍历碰到子序列就变字母,直到最后判断是不是.

a2:b
b0:c
c2:d
d1:e//子序列匹配上

a0:a
a1:a
b1:b
b2:b
c0:c
c1:c
d0:d
d2:d
e0:e
e1:e
e2:e//字母移动

e::yes
b::no
c::no
d::no
aa::no//判断

:a//如果实在没有了(开局或者没字母了)会再插一个字符

然而最优解七行…

0:no
2no2nononononononononononononononono:nnoo
2nononononononononononononononono:nononononononononononononononono2
on:
1:0000000000000000
2:no
nnoo:yes

大致意思是,把0换成no,把2021换成nnoo(yes),然后no会被最后消成一个,如果出现yes也会消,最后判断,非常仙的思路.

0084

0085

我们考虑同质化,把他们变成0+啥,然后由于最后一个数字也肯定是0+,所以考虑+0:0,然后最后转化回去就可以了.

2:0++
1:0+
+0:0
00:0
0++::2
0+::1