一般这种题我们都是先推导下界 再来构造
那我们假设我们当前放置了k位半皇后 我们只考虑横竖被吃掉 并且贪心的(类似于八皇后的选择)横竖都不重叠
我们把他固定在左上角的kk的矩阵里 因为横竖都有被一个板皇后占到 所以我们只有右下角那个(n-k)(n-k)的矩阵了
下面边长为n-k的矩阵 对角线有2(n-k)-1条 而我们已放置了k个半皇后 这样我们就可以得到一个不等式 k>=2(n-k)-1 -> k = \(\lceil (2n-1)/3 \rceil\)
有了这个下界我们来考虑其是否有可行的构造解 我们想到反对角线这一种情况 因为他恰好合法并且对角线都不重合
我们可以发现当 n%3==2时最特殊 因为要是我们n在此刻+1 那么我们的下界也会+1 n+2 下界也会+2 每次下界+1 我们也可以通过在(n,n)放置一个将其变成(n-1)(n-1)的矩阵
那我们就只用的n%3==2时进行构造即可
我们考虑将反对角线分成k/2 k/2+1 因为k一定是奇数 然后放在k*k的矩阵里 很容易构造出一组互补的并且不重不漏地
最后注意特判1即可
#include <bits/stdc++.h>
using namespace std;
const int N =3e5+10;
const int M = 998244353;
const int mod = 135799;
#define int long long
#define endl '\n'
#define Endl '\n'
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define inf 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
void solve() {
int n;cin>>n;
if(n==1){
cout<<1<<endl;
cout<<1<<' '<<1<<endl;
return;
}
vector<pair<int,int>>ans;
while(n%3!=2){
ans.emplace_back(n,n);
n--;
}
int t=(n-2)/3;
for(int i=1,j=t+1;i<=t+1;i++,j--)ans.emplace_back(i,j);
for(int i=n-t+1,j=n;i<=n;i++,j--)ans.emplace_back(i,j);
cout<<ans.size()<<endl;
for(auto i:ans)cout<<i.first<<' '<<i.second<<endl;
}
signed main(){
fast
int T;T=1;
while(T--) {
solve();
}
return ~~(0^_^0);
}
标签:783,int,矩阵,Codeforces,下界,对角线,Div,我们,define
From: https://www.cnblogs.com/ycllz/p/16617490.html