pldzy
2022-07-19 20:34:20
AtC 传送门:【ARC110E】Shorten ABC
碰到这种题就要下意识把字母集转化为数字集,然后考虑使用位运算解决。
在将 abc 转化为 123 之后发现,对于每一个对答案有贡献的长为 len 的字符串,本质上都是在 123 数字序列上划分了 len 段,每一段都把里面所有的数直接异或起来,结果即是那一段的字母。
然后笔者自行惭愧讲不清楚时间不够,所以贴上 @kymru 大佬的题解博客原文内容。
补充说一下最后需要结尾一段异或和为 0 才统计的原因。感性的理解/证明是:发现不论怎样操作字符串,它所对应的数字串的异或和是不变的,故当前面 i 个数异或和与前 n 个数的异或和相同时,这两部分所组成的字符串才是一种操作原串能得到的字符串。(此解释来自 @dyy2020。)
AC Code.