P5304:[GXOI/GZOI2019]旅行者 – 题解

主要思路

这个题还蛮神仙的，我很喜欢。

如果是做暴力的话，那么这个思路是很有限的。我们考虑换一种思路。既然最后的答案是要求 \(\Theta(k^2)\) 级别对的最短路，我们尝试把这个规模进行缩小，然后只求小规模的全局解（并不是求出所有最短路），然后多次求解之后可以得到全规模的全局解。

因为是个排列，读入时我们可以把已有的数值放在数轴上，发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组，维护串和反串的哈希然后判断即可。

首先发现\(k\)非常的小，且\(n\)也较小，所以考虑直接暴力，枚举经过每一个超市的顺序，然后顺起来就行了（提前处理\(k\)次最短路即可）。

这套题全都是暴力出奇迹系列。

我们枚举一个端点，然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\)，然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。

然后用 sb 线段树搞下就行了，太特么傻逼了。

刚开始以为是搞\(\log n\)个基底点，然后双向边上面做事情，最后发现找图上最小环的复杂度非常的高。所以 GG。

正解考虑把问题的规模进行缩小：也就是把一些答案预先特判掉。比如说，如果某一个位上有超过三个点连接，那么环的大小就可以被确定为是\(3\)，也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。

再考虑剩下的情况。此时，\(n\)已经缩小了很多，所以我们暴力建图，用 Floyd 跑最小环即可。

其实就是靠墙走，然后乱七八糟的东西全部用 Djisktra 来搞就行了。