主要思路
这个题还蛮神仙的，我很喜欢。
如果是做暴力的话，那么这个思路是很有限的。我们考虑换一种思路。既然最后的答案是要求 \(\Theta(k^2)\) 级别对的最短路，我们尝试把这个规模进行缩小，然后只求小规模的全局解（并不是求出所有最短路），然后多次求解之后可以得到全规模的全局解。
Continue reading →这个题还蛮神仙的，我很喜欢。
如果是做暴力的话，那么这个思路是很有限的。我们考虑换一种思路。既然最后的答案是要求 \(\Theta(k^2)\) 级别对的最短路，我们尝试把这个规模进行缩小，然后只求小规模的全局解（并不是求出所有最短路），然后多次求解之后可以得到全规模的全局解。
Continue reading →因为是个排列，读入时我们可以把已有的数值放在数轴上，发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组，维护串和反串的哈希然后判断即可。
这套题全都是暴力出奇迹系列。
我们枚举一个端点，然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\)，然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。
然后用 sb 线段树搞下就行了，太特么傻逼了。
刚开始以为是搞\(\log n\)个基底点，然后双向边上面做事情，最后发现找图上最小环的复杂度非常的高。所以 GG。
正解考虑把问题的规模进行缩小：也就是把一些答案预先特判掉。比如说，如果某一个位上有超过三个点连接，那么环的大小就可以被确定为是\(3\)，也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。
再考虑剩下的情况。此时，\(n\)已经缩小了很多，所以我们暴力建图，用 Floyd 跑最小环即可。