答案中相邻两个数距离 $\le 2$ 的数对至少有 $n/4-1$ 对。因此随意一对距离 $\le 2$ 的数，在答案中相邻的概率约为 $1/8$。随机 $K$ 次的正确率约为 $1-(7/8)^K$，每次可以 $O(n)$ 求出最长的长度，总时间复杂度 $O(Kn)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #219 for Problem #5045. King
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:16:43
Last updated: 2025-12-13 00:16:47
题解
Comments
No comments yet.