有一个 的棋盘,你要在上面放最少数量的”半皇后“,使得每个格子都能被攻击到。
一个位于 的 ”半皇后“ 能攻击到 当且仅当满足以下条件中至少一个:
- ;
- ;
- ;
输出方案。
。
设有 个”半皇后“ 就能攻击到所有格子,那么首先不考虑斜着的攻击,则横竖攻击覆盖之后还剩下 的子矩阵没有被攻击到,需要使用斜着的攻击。
考虑这个子矩阵的第一行第一列,一共有 个格子,并且每个格子所在的对角线都不同,并且只要用斜着的攻击覆盖到这些格子就能覆盖完整个子矩阵。
所以至少需要 个”半皇后“才能斜着覆盖这些格子,那么可以列出不等式 ,所以 ,那么 的理论下界就是 。
考虑怎么构造能取到这个下界,显然若 则可以直接这样构造:

而若 就可以在左上角或者右下角放来变成 的情况。
代码如下:
// Problem: Half Queen Cover
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1667C
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int main()
{
scanf("%d",&n);
printf("%d\n",(n*2-1)/3+((n*2-1)%3!=0));
if(n==1) return puts("1 1"),0;
int f=0;
if(n%3==0) printf("%d %d\n",1,1),n--,f=1;
else if(n%3==1) printf("%d %d\n",1,1),printf("%d %d\n",n,n),n-=2,f=1;
int cnt=(n*2-1)/3;
for(int i=1;i<=cnt/2;i++) printf("%d %d\n",f+n-cnt+cnt/2-i+1,f+n-cnt+i);
for(int i=1;i<=(cnt+1)/2;i++) printf("%d %d\n",f+n-(cnt+1)/2+i,f+n-i+1);
return 0;
}