【ARC110E】Shorten ABC 题解

pldzy · 2022-07-19 20:34:20 · 个人记录

AtC 传送门：【ARC110E】Shorten ABC

碰到这种题就要下意识把字母集转化为数字集，然后考虑使用位运算解决。

在将 abc 转化为 123 之后发现，对于每一个对答案有贡献的长为 len 的字符串，本质上都是在 123 数字序列上划分了 len 段，每一段都把里面所有的数直接异或起来，结果即是那一段的字母。

然后笔者自行惭愧讲不清楚时间不够，所以贴上 @kymru 大佬的题解博客原文内容。

补充说一下最后需要结尾一段异或和为 0 才统计的原因。感性的理解/证明是：发现不论怎样操作字符串，它所对应的数字串的异或和是不变的，故当前面 i 个数异或和与前 n 个数的异或和相同时，这两部分所组成的字符串才是一种操作原串能得到的字符串。（此解释来自 @dyy2020。）

AC Code.