题解：P6360 [CEOI 2018] Lottery

InnitTimmer_ · 2025-11-12 14:06:24 · 题解

一道不是很好想的题，这种枚举两个区间的方式第一次见。

首先一个暴力的想法是枚举两个区间然后暴力计算其中对应位置是否相等，这样时间复杂度是 O(n^3) 的，过不了。

首先注意到 n\leq 10000，显然只能 O(n^2) 去做，所以我们要考虑一种枚举方式。

我们注意到对于一个区间 [L,R]，下一个区间就是 [L+1,R+1]，那么我们可以讲 a_{L} 的贡献扔掉，把 a_{R+1} 的贡献加进来，但是我们固定一个区间去让另一个区间这样跑就还是只能 O(n^3) 来计算，所以我们考虑枚举两个区间的位置差值，这样一个区间跑的时候另外一个区间也会跟着跑，时间复杂度就成了 O(n^2) 了。

代码比较难写，细节较多，太难看了，就不放了。