CF1667C Half Queen Cover 做题记录

有一个 $n\times n$ 的棋盘，你要在上面放最少数量的”半皇后“，使得每个格子都能被攻击到。

一个位于 $(x,y)$ 的 ”半皇后“ 能攻击到 $(a,b)$ 当且仅当满足以下条件中至少一个：

• $a=x$；
• $b=y$；
• $a-b=x-y$；

输出方案。

$1\le n\le 10^5$。

设有 $k$ 个”半皇后“ 就能攻击到所有格子，那么首先不考虑斜着的攻击，则横竖攻击覆盖之后还剩下 $(n-k)\times (n-k)$ 的子矩阵没有被攻击到，需要使用斜着的攻击。

考虑这个子矩阵的第一行第一列，一共有 $2n-2k-1$ 个格子，并且每个格子所在的对角线都不同，并且只要用斜着的攻击覆盖到这些格子就能覆盖完整个子矩阵。

所以至少需要 $2n-2k-1$ 个”半皇后“才能斜着覆盖这些格子，那么可以列出不等式 $2n-2k-1\le k$，所以 $k\ge \frac{2n-1}{3}$，那么 $k$ 的理论下界就是 $\left\lceil \frac{2n-1}{3}\right\rceil$。

考虑怎么构造能取到这个下界，显然若 $n\equiv 2\pmod 3$ 则可以直接这样构造：

而若 $n\not\equiv 2\pmod 3$ 就可以在左上角或者右下角放来变成 $n\equiv 2\pmod 3$ 的情况。

代码如下：

// 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;
}