自动搬运

查看原文

来自洛谷，原作者为

	TLEWA 一袋可爱的猫粮喵！

搬运于2025-08-24 23:05:38，当前版本为作者最后更新于2024-11-02 20:32:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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} $ $$

现在考虑加入 =。假设我们有一个串 <=>，匹配为： $(1,2),(1,3),(2,4),(3,4)$。

考虑第一个算式和 = 连续段的关联，我们发现其实这个东西相当于延长了左右 < 与 > 的长度，不同的是 = 内部不存在这样的贡献。同样以 <=> 举例，<=> 可以拆成 << 和 >>，同时 = 被使用了两次。

如何更具体地理解这个东西？我们观察 <==< 这个串中贡献：

• 我们发现 = 对 < 来说，匹配贡献和 < 等同，如当 $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。

接着我们翻遍语言特性，发现我们忽略了一个语法糖，然后我们根据这个东西把所有 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 的古旧版本下甚至不被支持），用 _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。

但是，这份代码的长度仍没有压缩到极限，在 @小之森夏音 帮助下，我们将以下几个地方再次压缩：

[*?<..?>] 变为 (?<..?>)：后者能够再次短下 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)$。（最短解收录于此处）