P11243 繁花 题解

· · 题解

Upd on 2024/11/11：在 @小之森夏音 大佬的帮助下，将代码长度压缩至 92B，结合另一个优化思路压缩至 91B，更新相关讲解。

观前提示

本题解主要讲解此题代码的 CodeGolf 思路，代码语言为 Ruby，且对题目本身解法可能介绍较简略，使用了较有特色的正则表达式辅助解决了该题的计数，如你还不会本题的解法，不推荐首先观看本题解。

本题解默认大家理解基本的类 C/C++ 语法，如三目运算符等，以及基本的面向对象逻辑，如我不会解释类似 C++ 中的 std::string::size() 的基本使用语法（仅作举例）。

关于 CodeGolf：简单来说 CodeGolf 是在实现指定功能的同时尽量压缩代码长度的运动，短并不意味着简单，在更短的空间内塞下同样的功能不会比更长要简单，欢迎大家闲暇之时进行相关活动放松身心。

思路解析

先考察只有 <，> 的情况，发现答案显然是如样例 1 的第一个输入一样，设 s 为原字符串，S 为 s 的最长连续相同子串集合，答案是：

\sum_{i \in S} \frac{siz(i) \times (siz(i)+1)}{2}

现在考虑加入 =。假设我们有一个串 <=>，匹配为：

考虑第一个算式和 `=` 连续段的关联，我们发现其实这个东西相当于延长了左右 `<` 与 `>` 的长度，不同的是 `=` 内部不存在这样的贡献。同样以 `<=>` 举例，`<=>` 可以拆成 `<<` 和 `>>`，同时 `=` 被使用了两次。 如何更具体地理解这个东西？我们观察 `<==<` 这个串中贡献： - 我们发现 `=` 对 `<` 来说，匹配贡献和 `<` 等同，如当 $a_1 < a_2$ 时，只要 $a_2 \le a_3$，对 $a_1$ 的贡献都等同。 - `<` 对 `=` 来说，匹配贡献也类似：当 $a_3 \le a_4$ 时，只要 $a_4 < a_5$，$a_3,a_4$ 对 $a_5$ 的贡献都相同。 - 在连续 `=` 串中，显然无任何贡献。 于是把 `=` 视作通配符，匹配 `<` 和 `>` 连续串，减去内部 `=` 串的内部贡献即可。 ## 代码编写 本篇题解的重点！根据上面的思路，我们首先写出一个初版代码（长度 160B）： ``` gets.to_i.times{gets;a=gets;p ['<','>'].map{|i|a.scan(/[#{i}=]*#{i}[#{i}=]*/).map{|j|(n=j.size)*(n+1)/2-j.scan(/=+/).map{|k|(m=k.size)*(m+1)/2}.sum}.sum}.sum} ``` 下面来逐步解析一下这个代码里面各个东西的作用： - `gets.to_i.times{}` 首先读入 $T$，转换成整型，然后通过 Ruby 的 times 方法进行多测的循环解题。 - `gets;a=gets` 我们这个代码并不需要知道字符串的长度，直接读掉就好。然后令变量 $a$ 等于读入的字符串 $s$。 - `['<','>'].map{}` 作用类似于 python 的列表推导式和 C++ 的 for_each 语法（`arr.map{|i|}` 类似于 `for(auto i:arr) {}`，不同的是 `map` 中表达式的值会直接返回，在原列表基础上生成一个新列表），我们遍历 `['<','>']` 这个字符列表中的所有变量，根据列表内的变量生成一个等长的新列表。 - `|i|` 钦定变量 $i$ 迭代字符列表内的值。 - `a.scan(/[#{i}=]*#{i}[#{i}=]*/)` 对 $a$ 应用一个正则表达式（`[#{i}=]*#{i}[#{i}=]*`，大意为找到 `<,>` 中，数量为 $1$ 的当前遍历字符，同时在两侧匹配尽量多的`=` 或当前遍历字符（数量可以为 0）），在代码内的作用是生成仅包含遍历中的 `<`，`>` 之一和 `=` 两种字符的最长连续串，同时判掉仅有 `=` 的串（代码中 `#{i}` 表示在表达式串的这个位置插入变量 $i$，在 python 中也有类似语法）。 - `.map{|j|(n=j.size)*(n+1)/2` 计算解题思路内提到的正贡献。 - `-j.scan(/=+/).map{|k|(m=k.size)*(m+1)/2}.sum` 我们对连续段中用到的 `=` 连续串应用同样的方式计算减去的贡献。 - `.sum` 对于列表求和。 - `p` Ruby 的输出函数之一。 这个东西已经很短了，但是其实这个做法的潜力不止于此！我们真的需要这么多长度去单独处理 `=` 的情况吗？不！沿着这个思路，我们可以一路把代码长度压缩到 120B，目前最短！ 我们首先发现其实不需要判掉仅有 `=` 的串，在 160B 代码的内层循环中，这部分多算的贡献会直接被抵消掉，应用这个优化思路简化正则表达式（优化为 `[#{i}=]+`，大意是匹配尽量多的（一个以上）`=` 或当前遍历字符），可以优化到 146B，是我赛时最短的代码（然后就被一个很朴素的 Ruby 代码（133B）打爆了）。 考察一下应用上个改变后两层循环的本质，我们发现所有内层循环的贡献之和实际上只是把所有 `=` 串匹配了两遍，于是我们把减去 `=` 权值的工作移到外层循环（此时正则表达式处理 `=` 时匹配字符集的表达式为 `#{i}=`，生成的字符集为 `==`，被自动去重后正好能匹配上所有最长连续 `=` 串），乘以 $-2$ 的权值即可。 代码变成： ``` gets.to_i.times{gets;a=gets;p ['<','>','='].map{|i|(i=='='?-2:1)*a.scan(/[#{i}=]+/).map{|j|(n=j.size)*(n+1)/2}.sum}.sum} ``` 长度 120B。 然后我们发现字符列表 `['<','>','=']` 由于内层循环被提出来了，相应变成了三个元素，开销较大，我们考虑改写成另一种形式 `"<>=".chars`，节省 2B。以及我们可以把里面计算贡献的 `(n=j.size)*(n+1)/2` 拆成两部分，除法放在外面避免括号的 2B 额外开销，接着我们发现，改写成字符串再转换为字符数组的形式还有额外的好处，我们不用在 `p` 函数后面加一个空格，Ruby 也可以正常解析我们的代码了，于是再节省 1B。 接着我们翻遍语言特性，发现我们忽略了[一个语法糖](https://ruby-doc.org/core-2.4.0/Enumerable.html#method-i-sum)，然后我们根据这个东西把所有 `map{}.sum` 缩写为 `sum{}` 即可压缩到 107B（对于 `sum` 方法支持这种语法，但是对于 `max`，`min` 等方法是不支持的，请注意）。 代码： ``` gets.to_i.times{gets;a=gets;p"<>=".chars.sum{|i|(i=='='?-2:1)*a.scan(/[#{i}=]+/).sum{|j|(n=j.size)*n+n}/2}} ``` 接下来，我们就要应用一些更魔怔的压行思路了！`"<>=".chars` 这个写法还是太长，我们利用一些不太为人知的写法，再次改写为 `%w(< = >)` 或 `[*?<..?>]`，可以节省 2B，但是 `p` 后面的空格没法再压于是只能增加 1B，整体长度仍减少。 我们发现我们显式声明循环变量名称还是有点太长了！（`|i|`，开销至少 3B）我们不妨使用在 Ruby 2.7 引入的一项功能（[但是在 tio.run 的古旧版本下甚至不被支持](https://tio.run/##KypNqvz/P9pQx0jHOFYvN7GgukAh3rD2/38A)），用 `_1` 代替我们显式声明的循环变量吧！可惜的是，其对嵌套循环支持不是很好，我们仅压缩了内层循环的 2B 长度。 回到我们对多测的处理，`gets.to_i.times` 和两次 `gets` 还是开销太大，我们不妨滥用一下 Ruby 提供给我们的全局变量 `$<`，其能获取到全部输入，于是我们直接操作流，以 2B 的代价和一些其它处理读入所有有用部分的东西： 先以一个 `gets` 读掉最前面不方便在循环内处理的测试用例数量（我们并不需要它的数值，而且因为破坏输入规整性的特性只好以 5B 的巨大开销去处理！），然后使用 `.map` 遍历 `$<`，此时输入的每一行都是我们遍历的一个元素，我们发现提前读掉 $T$ 后我们第一次遍历到的是第一个测试数据的 $n$，我们也不需要。好在这个时候 `$<` 把 $n$ 遍历出来之后读入流同时移动到了下一行。我们直接令 `a=gets`，在读入需要处理的串的同时，`gets` 也会再次使流后移，此时结束本次循环之后 `$<` 刚好直接遍历到下一组测试用例的 $n$，形成循环。这样处理内部的解题代码也不用做读入串合法的额外判断，完美符合我们缩短长度的目的。 具体到代码： ``` gets;$<.map{a=gets;p [*?<..?>].sum{|i|(i=='='?-2:1)*a.scan(/[#{i}=]+/).sum{(n=_1.size)*n+n}/2}} ``` 长度 95B。 但是，这份代码的长度仍没有压缩到极限，在 @[小之森夏音](https://www.luogu.com.cn/user/532572) 帮助下，我们将以下几个地方再次压缩： `[*?<..?>]` 变为 `(?<..?>)`：后者能够再次短下 1B，在这个场景下，范围和数组应当发挥一样的作用，但是在我的在线编辑环境下似乎并不支持后面那种写法。 `'='` 变为 `?=`：我的严重疏忽，单字符字符串在 Ruby 中，除了以 `''` 包裹，也可以在前方加上 `?` 将其转变为字符串。 `.sum{(n=_1.size)*n+n}/2` 变为 `.sum{(1.._1.size).sum}`：思路解析中的算式，本质上是一个简单的等差数列求和，我们为何要通过复杂的求和公式 $O(1)$ 计算和式？直接列出等差数列并求和可以获得更短的长度，同时复杂度瓶颈仍在正则表达式的字符串匹配，复杂度不变。 同时，我有了另一个小优化：再次滥用一下 Ruby 提供的全局变量，我们可以不显式声明 `a=gets`，`gets` 的结果会存储在变量 `$_` 中，直接访问 `$_` 即可省下 1B。 代码最终变为： ``` gets;$<.map{gets;p (?<..?>).sum{|i|(i==?=?-2:1)*$_.scan(/[#{i}=]+/).sum{(1.._1.size).sum}}} ``` 长度 91B，时间复杂度 $O(\sum n)$。（最短解收录于[此处](https://www.luogu.com.cn/article/nlbz7z8j)）