曼哈顿距离

题目链接：https://codeforces.com/contest/1968/problem/E

题意

给定一个整数n，在网格的网格中选择n个不同单元格，最大化任意单元格之间的不同曼哈顿距离，如下图所示.
Image

数据范围

题解1     本人的取巧做法，个人感觉比较麻烦，不过代码确实能AC过本题。解题思路主要是从题目所给的样例6得到启示.
    首先，一张网格的最大曼哈顿距离一定是处于对角两边形成的唯一最大值，所以曼哈顿距离的种类数最大也是加上本身的零.以n=6为例，其符合条件的距离为0,1,2,3,4,5,6,7,8,9,10.当我们放置对角两个以及某一角落的相邻两个时，剩下需要找的距离为0,1,2,3,4,5,6,7,8,9,10.
    正是因为有临接在角落的三个，所以我们每次按三格单位距离向下倒推退，就一定会有三个从小到大的距离满足！如图，假设现有的棋子位居(1,1),(1,2),(1,3),(6,6)，那我们现在右下移动{2,1}格距离，也就是(3,4)格放置，此时剩下要找的距离为0,1,2,3,4,5,6,7,8,9,10.同理，再在(5,5)格放置棋子，此时所有距离均能满足，且棋子数正好达到6，实现了最大化的要求.
    然而，当n增加时，因为每次向下跨越两格，极有可能在纵向无法摆放的情况下，棋子数尚未使用完，同时也未能满足所有的曼哈顿距离；所以我们可以对剩余的棋子从(n,n)处往上开始摆，往左上移动{-2,-1}的距离，这样既能够摆完所有的棋子（因为纵向大约有2*n的空间），又能满实现曼哈顿距离从大到小的满足，恰好与前者进行互补.
Code1: 
#include< bits/stdc++.h>
#define int long long
#define endl '\n' 
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        if(n==2){
            cout << "1 1" << endl;
            cout << "2 1" << endl;
            continue;
        }else if(n==3){
            cout << "2 3" << endl;
            cout << "2 1" << endl;
            cout << "3 1" << endl;
            continue;
        }else if(n==4){
            cout << "4 4" << endl;
            cout << "4 3" << endl;
            cout << "1 3" << endl;
            cout << "1 1" << endl;
            continue;
        }
        cout << "1 1" << endl;
        cout << "1 2" << endl;
        cout << "1 3" << endl;
        cout << n << ' ' << n << endl;
        int m = n;
        m -= 4;
        int x = 1, y = 3;
        int i;
        for(i=1;i<=m;i++){
            x += 2, y++;
            cout << x << ' ' << y << endl;
            if(x+2>n)
                break;
        }
        if(i==m+1)continue;
        x = n, y = n;
        for (int j = i + 1; j <= m; j++){
            x -= 2, y--;
            cout << x << ' ' << y << endl;
        }
    }
    return 0;
}
题解2(极简)     在的棋盘中摆放n个棋子，可以试着摆满对角线，即(1,1),(2,2),...,(n,n),不难发现，此时所有**偶数**的曼哈顿距离全部满足，只需要对其中一个棋子进行**距离为1的移动**即可构造出**奇数**的距离，我们将(2,2)向上移动到(1,2)的位置，此时一定满足所有的情况.     不过需要注意的是，当时，网格实在太小，直接打表即可.
Code2: 
#include
#define int long long
#define endl '\n' 
#define INF 1e15
using namespace std;
typedef pairpii;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        if (n == 2){
            cout << "1 1" << endl;
            cout << "2 1" << endl;
            continue;
        }
        else if (n == 3){
            cout << "2 3" << endl;
            cout << "2 1" << endl;
            cout << "3 1" << endl;
            continue;
        }
        cout << "1 1" << endl;
        cout << "1 2" << endl;
        for (int i = 3; i <= n;i++)
            cout << i << ' ' << i << endl;
    }
    return 0;
}