自动搬运

查看原文

来自洛谷，原作者为

	Milthm ?

搬运于2025-08-24 23:03:52，当前版本为作者最后更新于2024-09-15 19:20:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

赛时被创飞了，所以我仔细地思考了一下这种题应该怎么做。

首先出题人比较良心，在题目名就告诉我们这是一道诈骗题，当然这不能成为我们做题的依据。

读完题，我们发现这道题是构造题，所以先想想这个最小的局面在什么时候会产生。因为这题的基础限制，每个数都至少要被用一次，所以答案最少也就是 $\lceil \frac{n}2 \rceil$。

到这里我们可能会想到根据给定的特殊限制去做，但是经过尝试之后发现这很难，因为多个限制之间的相交很难处理。那么这个题要么是我太菜了不会处理，要么这个方向是错的。

如果不是前面那种情况的话，那基本上就只剩一种可能了，就是这个特殊限制其实没用，也就是说存在一种构造使得任意的特殊限制都能满足。

从最理想的情况（即答案为 $\lceil \frac{n}2 \rceil$）考虑，那么我们这 $\lceil \frac{n}2 \rceil$ 对整数必须要有一些特殊的性质才可以。看看分母上这个 $2$，再想想这个“只有一个端点在区间内”的限制，发现其实可以用很多个小区间（长度小于等于 $\frac{n}2$）依次盖住这 $n$ 个点，这样对于每个特殊限制总有一个小区间的左或右端点在区间之内。

又因为小区间的数量要尽可能小，所以我们只需要输出所有满足 $1\le i \le \lfloor \frac{n}2 \rfloor$ 的 $(i,i+\lfloor \frac{n}2 \rfloor)$ 即可（奇数的话还要补一个 $(1,n)$）。

然后我们就以时空复杂度均 $O(n)$ 的。短到难以置信的代码 AC 了这道题，这就是诈骗题的魅力，下次别出了。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
	cin>>n>>m;
	cout<<(n+1)/2<<'\n';
	for(int i=1;i<=n/2;++i)cout<<i<<" "<<i+n/2<<'\n';
	if(n&1)cout<<1<<" "<<n<<'\n';
	return 0;
}

当然，这种题能猜到结论更好，但这并不是每个人都能做到的。