题目链接：https://atcoder.jp/contests/agc061/tasks/agc061_b

做法

Mad，纯纯折磨题。

首先，$n=2$ 的时候是无解的，因为连出 $i=2$ 的路径后剩下的两条边无法连到一起。

做法的核心思想是，将两条路径拼到一起，考虑找出一个更长的路径，然后再拆开。

例如奇数的情况，是把路径拼成 $\frac{n+1}{2}$ 条长度为 $2n$ 的路径，然后拆出结果。

做法就是，下面分别从 $1,3,5..$ 开时重复连 M 型。（下面默认二分图上面部分有 $n$ 个点，下面部分有 $n+1$ 个点）

$n=5$ 的情况如下：

然后当时因为 $2$ 无解，而且偶数的情况我想不出来，感觉应该是无解，然后还证明了，然后就写了交上去，WA飞了，百思不得其解，下了数据才发现除了 $2$ 都有解，但是由于已经忘了怎么证了，也就不知道证明哪里假了。

所以，在做这种题目的时候，不能因为没想出来就主观认为无解（不然你猜猜这道题目的评级为什么 3000+ ），还是应该写个暴力或者手动再验证几组数据再下结论。

那么偶数怎么做呢？

同样的思路，我们发现 $i=n$ 一定会在下面产生两个奇数点，需要一条路径消掉，所以不妨考虑处理 $\frac{n}{2}+2$ 条路经，其中 $\frac{n}{2}-1$ 条处理上面为起终点的长度为 $2(n-1)$ 的路径，然后剩下三条路径一条以上面剩下两个奇数点为起终点，两条在下面。

首先是 $\frac{n}{2}-1$ 的路径，在上面分别以 $3,5,7…$ 为起点，以下面的 $n-1$ 个点为中转点抛出类似 M 的路径，被去掉的 $2$ 个点也是有规律的，按照 $(n-2,n-1),(n-4,n-3)…$ 这样下去。

剩下的边可以凑数长度为 $4,2n,2(n-3)$ 的路径，至于怎么凑，看代码吧。

时间复杂度：$O(Tn^2)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>
#include<cstring>
#define N 110
#define NN 210
using namespace std;
int n;
int v[N][N];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(n==2){printf("No\n");continue;}
        if(n&1){
           int x=1;
            for(int i=0;i+i<=n;i++){
                int cnt=0;int y=x;
                for(int j=1;j<=n;j++){
                    cnt++;
                    if(cnt<=i+i)v[j][y]=i;
                    else v[j][y]=n-i;
                    cnt++;y++;if(y==n+2)y=1;
                    if(cnt<=i+i)v[j][y]=i;
                    else v[j][y]=n-i;
                }
                x+=2;
            }
        }
        else{
            int pre=-1;
            for(int i=1;i<n/2;i++){
                int x=i*2+1,t=n-i*2,y=1,cnt=pre+1;
                while(cnt==2 || cnt==n-3)cnt++;
                pre=cnt;
                int type=cnt;
                // printf("%d %d %d\n",x,y,t);
                for(int j=1;j<n;j++){
                    if(j>cnt)type=n-1-cnt;
                    v[x][y]=type;
                    x++;if(x==n+1)x=1;
                    // printf("%d %d %d\n",x,y,t);
                    v[x][y]=type;
                    y++;if(y==n+2)y=1;
                    while(y==t || y==t+1){y++;if(y==n+2)y=1;}
                    // printf("%d %d %d\n",x,y,t);
                }
            }
            v[1][1]=v[1][2]=v[n][2]=v[n][n+1]=n;
            for(int i=1;i<=n-2;i++)v[n-i][n+2-i]=v[n-i][n+1-i]=n;
            v[2][1]=v[2][2]=v[3][2]=v[3][3]=2;
            v[1][3]=v[4][3]=n-3;
            for(int i=4;i<n;i++)v[i][i]=v[i+1][i]=n-3;
        }
        printf("Yes\n");
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n+1;j++)printf("%d ",v[i][j]);
            printf("\n");
        }
    }
    return 0;
}

回顾：

这道题目其实还是挺有难度的，回顾一下做题过程纪念纪念自己花了这么久时间做出来的一道题目。

而且这道题目的做题过程其实也可以推广到很多存在性构造题上。

首先看到一个构造题，尤其是比较难的构造题，如果直接从其的题目条件出发很多时候不一定能做，因为情况太多，太过复杂和没有规律，这个时候就需要把问题缩小到一个有规律的题目上面，只不过这种缩小有时候可能会无解。

例如奇数的情况我就认为一定存在一种方案使得路径能够连接成 $\frac{n+1}{2}$ 条长度为 $2n$ 的路径，从而把题目变成了一个有规律更好想的题目，但是这种缩小有时候不一定正确，思考缩小的过程也是凭直觉，比较感性，灵感往往来源于自己手动模拟多次后作出的猜想。

再例如，我认为偶数也可以拼成 $\frac{n}{2}$ 条长度为 $2(n-1)$ 的路径，但是却发现剩下的边构成了一个环（事实上想想也知道肯定不是路径，因为此时图中不存在奇数度的点），那么就把一条路径放回去，尝试人为的构造出三条路径。

而且这一步从度数的角度考虑也非常的正确，因为 $i=n$ 的路径一定会在下面创造一对奇数度点，所以我们必须把上面一条由两条路径拼成的路径拆回两条，一条占住他们本来的奇数度点，一条下来消掉 $i=n$ 创造的奇数度点。

然后通过这个操作，问题规模就缩小很多了，接下来就可以自己不断手模求一个通用解了，这样偶数的情况也就搞定了。

所以构造题，往往就是你自己再给题目加上一些约束条件，看看能否找到一个解，找不到就不断调整约束条件，直到找到为止。