自己刚刚在看这篇题解的时候看了半天有几个地方没搞懂,讨论了半个小时终于搞懂了!
-
1.为什么步骤四中:sort(sum,sum+n+1) 为什么原先是从1开始的操作,然而要把0也给排序进去?
举个例子:ab 这组数据会输出1,然而无论凭借哪一个字母作为 幸运数 都会输出0,因为没有能找到与它相等的前缀和,把0这个位置也给排序就解决了这种问题。
-
2.为什么 “幸运的j” 一定要取最后一个?
因为要是直接取第一个数字的话会第一个就在 sum[i].a[j]−=sum[i].a[t] 这一步骤中被减成0了,之后的减值操作就没有生效。至于为什么要减一个“幸运的j”可以看看一扶苏一的题解。
-
3.为什么在取答案的时候要使用等差数列?
在一开始我们已经通过排序使得最接近的前缀和相邻,所以此时往后去找相同的前缀和就可以直接向后找。至于以上问题可以看一下这组数据:abcccbbaa 。这里的答案显而易见是3,可取abc,ccbbaa和abcccbbaa,这里可以观察出两个相邻的 “魔法子串” 可以拼接出一个大的 “魔法子串” ,以此类推想一想多个相邻 “魔法子串” 的情况,就可得统计答案时应使用等差数列求值!
以上就是对题解的补充,如有差错请多谅解!(原作者确实nb!OrzOrz)