题解补充
查看原帖
题解补充
818000
xxmb楼主2024/3/30 19:21

自己刚刚在看这篇题解的时候看了半天有几个地方没搞懂,讨论了半个小时终于搞懂了!

  • 1.为什么步骤四中:sort(sum,sum+n+1)sort(sum,sum + n + 1) 为什么原先是从1开始的操作,然而要把0也给排序进去?

    举个例子:abab 这组数据会输出1,然而无论凭借哪一个字母作为 幸运数 都会输出0,因为没有能找到与它相等的前缀和,把0这个位置也给排序就解决了这种问题。

  • 2.为什么 “幸运的j” 一定要取最后一个?

    因为要是直接取第一个数字的话会第一个就在 sum[i].a[j]−=sum[i].a[t]sum[i].a[j] -= sum[i].a[t] 这一步骤中被减成0了,之后的减值操作就没有生效。至于为什么要减一个“幸运的j”可以看看一扶苏一的题解。

  • 3.为什么在取答案的时候要使用等差数列?

    在一开始我们已经通过排序使得最接近的前缀和相邻,所以此时往后去找相同的前缀和就可以直接向后找。至于以上问题可以看一下这组数据:abcccbbaaabcccbbaa 。这里的答案显而易见是33,可取abc,ccbbaa和abcccbbaaabc,ccbbaa和abcccbbaa,这里可以观察出两个相邻的 “魔法子串” 可以拼接出一个大的 “魔法子串” ,以此类推想一想多个相邻 “魔法子串” 的情况,就可得统计答案时应使用等差数列求值!

以上就是对题解的补充,如有差错请多谅解!(原作者确实nb!OrzOrz)

2024/3/30 19:21
加载中...