P10871 题解

· · 题解

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

点进来一看到样例吓一跳，这不直接猜棋子数是 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
*/