题解：P11055 Yet another ZP problem
一道构造题。
题目思路
比赛时发现对于限制，有 \(0 \le m \le 10^5\)。这样的限制似乎十分难以处理。但是我们可以直接得出一个结论。构造一个不论什么限制都能合法的解。
结论
对于 \(n\) 个点，令 \(1\) 连 \(1+ \lfloor \frac{n}{2} \rfloor\)，\(2\) 连 \(2+ \lfloor \frac{n}{2} \rfloor\)，以此类推。所以，一般的，对于每个 \(n_i\ (n_i<\lfloor \frac{n}{2} \rfloor)\)，\(n_i\) 向 \(n_i+\lfloor \frac{n}{2} \rfloor\) 连一条边。
如果 \(n\) 是偶数，那么 \(1\) 再和 \(n\) 连一条边。
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll l,r;
int main(){
cin>>n>>m;
cout<<(n+1)/2<<endl;
for(int i=1;i<=m;i++){
cin>>l>>r;
}
for(int i=1;i<=n/2;++i){
cout<<i<<" "<<i+n/2<<endl;
}
if(n%2!=0){
cout<<1<<" "<<n<<endl;
}
return 0;
}