自动搬运

查看原文

来自洛谷，原作者为

	zyh_helen 是一本除小说主角外所有人都是小说主角的小说的主角

搬运于2025-08-24 23:02:03，当前版本为作者最后更新于2024-08-22 20:26:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

非常有意思的一道题，这里提供一下我的构造方法。

点进来一看到样例吓一跳，这不直接猜棋子数是 $n^2$ 吗？又看 $n=2$ 的样例，就直接猜 $n$ 是奇数的时候棋子数是 $n^2$ 了。

先不细想正确性，考虑 $n$ 是偶数的最小棋子数，看到样例很难不让人想到 $(n-1)^2$，但想构造越想越不对劲，感觉还可以再放，但放满 $(n-1)^2$ 之后就再也放不了了呀。

小小手玩了一下，发现 $n=4$ 的时候可以在外面先围个圈，再在其中放就可以做到更优秀。

我们改变之前从上往下放的思路，但是整体归纳分析的思路不能变，于是我们使用经典的从外到内放，发现外面的一圈对中间是没有影响的：每个棋子八个方向各有 $x$（外围圈数）个皇后，刚好抵消了。

所以我们只用考虑一圈怎么构造。接着我们开始手玩，这里我直接给出方法：

• 首先对于上边和下边，我们交替错开分别连着放两个棋子，容易证明这时符合要求。

• 接着对于左边和右边，我们也是交替错开分别连着放两个棋子，这时候由于上边和下边的皇后对于一个点刚好抵消，所以也是符合要求的。

这里一定要注意边界细节，可以参考代码的实现。

观察到我们此时昨晚上面两步后的形状大概是这样的：

111110
100001
100001
100001
100001
011110

但最后三个棋子无论怎样都放不进去，这时候我们做一步巧妙的步骤：往内层右上角先放一个。

我们发现它是能放进去的，并且放进去后，外层右上角也能放了，接着右下角，左下角都能放了。

这也带来一个问题，那就是我们往内层放了一个，打乱了节奏。这也很好解决，我们下一轮左右翻转一下就行了，毕竟我们本来第一个就是放角落的。

分析一下，除了最后到了 $2\times2$ 的矩阵无法继续操作，其他都可以，所以我们偶数的最小步数是 $n^2 - 3$。（别急，还不是正解，但我显然当时以为是最小了）

回过头看奇数，不也是这么做吗？

但同样的，到了 $3\times3$ 的矩阵无法继续操作，这时候，就要注意样例了！

样例给出了 $3\times3$ 的构造方案，我们只要将其前两步调转（显然不影响）正确性，就是我们所需要的解了。

到这里，我们已经有了清晰的构造方案，奇数 $n^2$，偶数 $n^2-3$。

但是当你信心满满的交上去，竟是 WA！

偷偷看一下错误信息，原来是偶数我们的答案大了 1。

接着又是手玩，可以在 $4\times4$ 的最后时候人类智慧的优化一步。

1110    1110    1111    1111    1111    1111
1001 -> 1011 -> 1011 -> 1011 -> 1011 -> 1011
1001    1001    1001    1101    1101    1111
0110    0110    0110    0110    0111    0111

左右翻转的时候同理。

至此这道题就结束了。

#include<bits/stdc++.h>
//#include<Windows.h>
#define int long long
//#define ll long long
//#define double long double
#define fi first
#define se second
//#define ls t[p].l
//#define rs t[p].r
#define y1 yyyyyyyyyyyyyyyy1
using namespace std;
const int N = 4e3 + 10, inf = 1e9, M = 2e5;
//const double eps = 1e-16;
const int mod = 1e9 + 7;
//const int mod;
//const int AQX = 9;
mt19937 rnd(time(0) ^ clock());
int random(int l, int r){
	return rnd() % (r - l + 1) + l;
}
const int offset = 101, offset2 = 103;
/*
		    	           _      _        _          
			       ____  _| |_   | |_  ___| |___ _ _  
			      |_ / || | ' \  | ' \/ -_) / -_) ' \ 
			      /__|\_, |_||_|_|_||_\___|_\___|_||_|
			          |__/    |___|                              
				       
*/
//struct Graph{
//	int head[N], tot;
//	struct edge{
//		int t, f;
//		int d, fa;
//		int next;
//	}e[N << 1];
//	void edge_add(int u, int v, int w = 0){
//		e[++tot].next = head[u];
//		e[tot].t = v;
//		e[tot].d = w;
//		e[tot].f = u;
//		head[u] = tot;
//	}
//	void clear(int n){
//		for(int i = 1;i <= tot;i++)e[i].t = e[i].f = e[i].d = e[i].next = 0;
//		for(int i = 1;i <= n;i++)head[i] = 0;
//		tot = 0;
//	}
//}g1, g2;
//int qmr(int x, int a){
//	int ret = 1, p = x;
//	while(a){
//		if(a & 1)ret = ret * p % mod;
//		p = p * p % mod;
//		a >>= 1;
//	}
//	return ret;
//}

int n, vis[N][N];
vector<pair<int, int> >v;
void work(int nw, int f, int p){
	if(nw == 2)return;
	if(nw == 3){
		if(f == 1){
			v.push_back({p + 1, p + 2});
			v.push_back({p + 1, p + 1});
			v.push_back({p + 2, p});
			v.push_back({p + 2, p + 2});
			v.push_back({p + 2, p + 1});
			v.push_back({p, p + 1});
			v.push_back({p, p + 2});
			v.push_back({p + 1, p});
		}
		else {
			v.push_back({p + 1, p});
			v.push_back({p + 1, p + 1});
			v.push_back({p + 2, p + 2});
			v.push_back({p + 2, p});
			v.push_back({p + 2, p + 1});
			v.push_back({p, p + 1});
			v.push_back({p, p});
			v.push_back({p + 1, p + 2});
		}
		return;
	}
	if(f == 1){
		for(int i = p + 1, f = 0;i < nw + p - 1;i++, f ^= 1){
			if(f)v.push_back({p, i}), v.push_back({p + nw - 1, i});
			else v.push_back({p + nw - 1, i}), v.push_back({p, i});
		}
		for(int i = nw + p - 2, f = 0;i > p;i--, f ^= 1){
			if(f)v.push_back({i, p}), v.push_back({i, p + nw - 1});
			else v.push_back({i, p + nw - 1}), v.push_back({i, p});
		}
		if(nw == 4){
			v.push_back({p + 1, n - p});
			v.push_back({p, n - p + 1});
			v.push_back({p + 2, n - p - 1});
			v.push_back({p + 3, p + 3});
			v.push_back({p + 2, p + 2});
		}
		else {
			v.push_back({p + 1, n - p});
			v.push_back({p, n - p + 1});
			v.push_back({n - p + 1, n - p + 1});
			v.push_back({n - p + 1, p});
			work(nw - 2, 2, p + 1);
		}
	}
	else {
		for(int i = nw + p - 2, f = 0;i > p;i--, f ^= 1){
			if(f)v.push_back({p, i}), v.push_back({p + nw - 1, i});
			else v.push_back({p + nw - 1, i}), v.push_back({p, i});
		}
		for(int i = nw + p - 2, f = 1;i > p;i--, f ^= 1){
			if(f)v.push_back({i, p}), v.push_back({i, p + nw - 1});
			else v.push_back({i, p + nw - 1}), v.push_back({i, p});
		}
		if(nw == 4){
			v.push_back({p + 1, p + 1});
			v.push_back({p, p});
			v.push_back({p + 2, p + 2});
			v.push_back({p + 3, p});
			v.push_back({p + 2, p + 1});
		}
		else {
			v.push_back({p + 1, p + 1});
			v.push_back({p, p});
			v.push_back({n - p + 1, p});
			v.push_back({n - p + 1, n - p + 1});
		}
		work(nw - 2, 1, p + 1);
	}
}
signed main(){
	cin >> n;
	if(n <= 2){
		cout << "1\n1 1\n" << endl;
		return 0;
	}
	cout << n * n - 2 * (n % 2 == 0) << endl;
	v.push_back({1, 1});
	work(n, 1, 1);
	for(auto x : v)printf("%lld %lld\n", x.fi, x.se);
	return 0;
}
/*


2 3
3 1
2 2
1 1
3 3
3 2
1 2
1 3
2 1
*/