题解：P11055 Yet another ZP problem

· · 题解

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

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

读完题，我们发现这道题是构造题，所以先想想这个最小的局面在什么时候会产生。因为这题的基础限制，每个数都至少要被用一次，所以答案最少也就是 \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;
}

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