P11067 题解

· · 题解

神仙题。

大概按难度排序。

task1

考虑引入其他字符进行计数，注意不要漏掉 L。

8
change 0 a 1 d
change 0 b 2 e
change 0 c 3 f
#
change 1 d 1 a
change 2 e 2 b
change 3 f 3 c
#

task2

与 task1 大致相同。

8
change 0 a 0 d
change 0 b 0 e
change 0 c 0 f
#
change 0 d 0 b
change 0 e 0 c
change 0 f 0 a
#

task6

循环删除 abc 串，剩至多两种字符。

然后删除 ab、bc、ac 即可。

然后去重。

8
change 0 abc 0 @
change 0 ab 0 @
change 0 ac 0 @
change 0 bc 0 @
change 0 aa 0 a
change 0 bb 0 b
change 0 cc 0 c
#

task7

考虑用以下做法保留两数众数。

change 0 ab 0 w
change 0 bw 0 bb
change 0 w 0 a

整三遍就过了。

ex_task7

考虑将其中两次「保留两数众数」并起来。

9
change 0 bc 0 f
change 0 cf 0 cc
change 0 f 0 b
change 0 ac 0 d
change 0 cd 0 cc
change 0 ab 0 d
change 0 bd 0 bb
change 0 d 0 a
#

task3

考虑将含 a 盒子的 b、c 替换为 d、e。

然后删除 b、c。

d、e 替换为 b、c。

8
change 0 ab 0 ae
change 0 ac 0 af
change 0 b 0 @
change 0 c 0 @
#
change 0 e 0 b
change 0 f 0 c
#

task4

结构上类似 task3。

8
change 0 ab 0 ae
change 0 ac 0 af
change 0 b 0 ab
change 0 c 0 ac
#
change 0 e 0 b
change 0 f 0 c
#

task8

手算每个字符对每个点贡献，优化掉其中一个位置。

9
change 1 a 2 dafgh
change 1 b 2 daafffgggghhhhh
change 1 c 2 daaaafffffffffgggggggggggggggghhhhhhhhhhhhhhhhhhhhhhhhh
#
change 2 d 1 a
change 2 f 3 a
change 2 g 4 a
change 2 h 5 a
#

task5

进制优化：压成一个字母进行操作。

13
change 0 a 1 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
change 0 b 1 wwwwww
change 0 c 1 w
#
change 4 ws 5 w
change 3 ws 4 w
change 2 ws 3 w
change 1 ws 2 w
change 0 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww 0 assssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
change 0 wwwwww 0 bssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
change 0 w 0 csssss
change 0 s 0 @
#

ex_task3

利用 task5 的进制优化技巧可以四行优化为三行。

7
change 0 b 0 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
change 0 ac 0 ae
change 0 c 0 @
#
change 0 e 0 c
change 0 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc 0 b
#

ex_task4

利用 task5 的进制优化技巧可以四行优化为三行。

7
change 0 ac 0 ae
change 0 b 0 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
change 0 c 0 ac
#
change 0 e 0 c
change 0 ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc 0 b
#

task10/ex_task10

直接进制优化，然后前缀和，这是容易的。

然后加一行运行次数的优化就行：

14
change 3 i 4 ij
change 2 i 3 ij
change 1 i 2 ij
change 4 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii 5 jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
change 4 i 5 j
change 0 c 0 ij
change 0 b 0 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
change 0 a 0 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
#
change 0 i 0 @
change 0 jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj 0 b
change 0 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb 0 a
change 0 j 0 c
#

task9

大概是进制优化，用官方题解所说的批量操作，然后合并优化一下。

解法建议看 std。

ex_task9

19
change 0 f 1 r
change 0 g 2 r
change 0 h 3 r
change 0 i 4 r
change 0 j 5 r
change 0 rrrr 0 vssssa
change 0 vssssab 0 ovssssa
change 0 vssssac 0 vssssa
change 0 aa 0 abcoooooooooo
change 0 bc 0 bcffffgggghhhhiiiijjjj
change 0 srr 0 @
change 0 or 0 v
change 0 rssssa 0 effgghhiijj
change 0 rsssa 0 dffgghhiijj
change 0 rssa 0 cffgghhiijj
change 0 rsa 0 bffgghhiijj
change 0 r 0 @
change 0 v 0 fghij
#