CF1667C Half Queen Cover 做题记录

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

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

  • a=xa=x
  • b=yb=y
  • ab=xya-b=x-y

输出方案。

1n1051\le n\le 10^5

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

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

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

考虑怎么构造能取到这个下界,显然若 n2(mod3)n\equiv 2\pmod 3 则可以直接这样构造:

而若 n2(mod3)n\not\equiv 2\pmod 3 就可以在左上角或者右下角放来变成 n2(mod3)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;
}