模拟几百步就可以了。
爆搜一下,时间复杂度大概是 $O(4 * n)$
Code: 56306723
二分答案,然后验证一下就好了,第一个数越小越好,之后的数都要求和前一个相等或者大一点。复杂度 $n * log(n)$
对于每一个 $i$,需要计算出最小的 $x$,使得 $s[i-x] = s[x] = s[i + x]$,对于 $i$ 而言,如果区间左端点在 $[1, i - x]$ 且右端点在 $[i + x, n]$,这样的区间就是合法区间。
处理出每一个合法区间集合:左端点在 $[1, i - x]$ 且右端点在 $[i + x, n]$,最后的工作就是去重,计算有多少种不同的区间。这个可以用矩形面积并来解决,不赘述。
这题的复杂度我不太会计算,第一步我是暴力算出来的,看似 $O(n^2)$ 的操作,结果好像很快就跑过去了。
Code:56313123
E - And Reachability
还没看,但是这题有空一定要做一下。