BIBI

昨天没打挑战赛，今来补一下题。。。
看到E是一个构造，我就来了 /jk

分析

（听说这是一道2019年上海高三数学竞赛的压轴题）
（个人还没有看MO的题解，所以我就先说说我的思路吧）
（这里我们把换成表示）
我们考虑巨阵和巨阵之间的关系---他们之间两两的三条边会不会有公用的边
显然可知，不可能存在这种情况，即，只会出现图中所示的情形
Nowcoder-7.png
进而，我们考虑构造题的套路---
是否能够得到一个上界，我们再想办法去构造它
假设总共有个巨阵，共有行（列）
那么我们考虑每个点的出度
在个巨阵排成一串时
共有个点出度为，且个点没有出度（这个很好想到）
又因为一个巨阵消耗个出度
那么我们可以列出一个表达式：
我们做一下简单的化简：

所以我们就得到了一个上界（感觉有点口胡，但当时的思路就是这么的奇葩）
到了这里，我们发现上界好像有了，但如何构造呢？（懵逼了1个多小时）
因为构造一定和有关，那么我们考虑将式子整理成我们想要的和有关的式子
原式
好吧，我们发现，这个式子根本没法冲。。。
那么考虑再处理出来一个
那么，原式
考虑这个式子在矩阵上的意义
将整个矩阵两行为一组分为组
每一行贡献个巨阵
另外的个巨阵，由最右边的两列贡献
手摸几个样例，发现没毛病！
那么我们再考虑这样子构造是否存在解
显然，对于一个成立解
将两端的点连起来
形成的这个DAG中，只要不存在环
那么按Topo序给图中的点从小到大赋值
即可得到原矩阵的所有值
对于我们的构造，按Topo之后
所有的度数都汇聚到了的位置
所以我们的构造是成立的
对于时
矩阵的最后一行是空着的，我们需要尽可能的获得更多的巨阵
所以可以如图处理
Nowcoder-6.png
但要注意的是，需要将这个没有任何连边的点赋值为
那么这道题就OK了

实现

由于本人比较懒，所以就给这个图直接连了边，然后跑Topo（/kk）

for(int i=1;i<Total;i+=2) { FOR(j,1,Total-2) Add_Edge(ID(i,j),ID(i,j+1)); }

Nowcoder-1.png

for(int i=2;i<=Total;i+=2) { FOR(j,1,Total-2) Add_Edge(ID(i,j+1),ID(i,j)); }

Nowcoder-2.png

for(int i=2;i<=Total;i+=2) { FOR(j,1,Total-1) Add_Edge(ID(i,j),ID(i-1,j)); }

Nowcoder-3.png

for(int i=2;i<=Total;i++) { if(i%2) Add_Edge(ID(i,Total-1),ID(i-1,Total-1)); Add_Edge(ID(i-1,Total),ID(i,Total)); }

Nowcoder-4.png
特别处理

if(Total%2) {
        for(int i=2;i<=Total-3;i+=2) {
            Add_Edge(ID(Total,i),ID(Total-1,i));
            Add_Edge(ID(Total,i+1),ID(Total,i));
            Add_Edge(ID(Total-1,i+1),ID(Total,i+1));
        }
    }

Nowcoder-6.png

实现

最后的效果
Nowcoder-5.png

//Nowcoder contest 8051 E
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f
#define Mod 998244353
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const int MaxN=1e3+10;

int Next[(MaxN*MaxN)<<1],Head[MaxN*MaxN],End[(MaxN*MaxN)<<1],Cur;
int Cnt,Total,Limit;
int RD[MaxN*MaxN],Ans[MaxN*MaxN];
queue<int>Mine;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Add_Edge(int From,int To) { Next[++Cur]=Head[From]; Head[From]=Cur; End[Cur]=To; RD[To]++; }
inline int ID(int X,int Y) { return (X-1)*Total+Y; } 
inline void Solve() {
    Mine.push(ID(1,Total));
    Ans[ID(1,Total)]=++Cnt;
    while(!Mine.empty()) {
        int New=Mine.front();
        Mine.pop();
        for(int i=Head[New];i;i=Next[i]) 
            if(!(--RD[End[i]])) { Ans[End[i]]=++Cnt; Mine.push(End[i]); }
    }
}

int main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Total;
    if(!(Total%2)) { Limit=((Total*Total-2)>>1); }
    else { Limit=(Total-1)+Total/2*(Total-2)+(Total-2)/2; }
    cout<<Limit<<endl;
    for(int i=1;i<Total;i+=2) { FOR(j,1,Total-2) Add_Edge(ID(i,j),ID(i,j+1)); }
    for(int i=2;i<=Total;i+=2) { FOR(j,1,Total-2) Add_Edge(ID(i,j+1),ID(i,j)); } 
    for(int i=2;i<=Total;i+=2) { FOR(j,1,Total-1) Add_Edge(ID(i,j),ID(i-1,j)); }
    for(int i=2;i<=Total;i++) { if(i%2) Add_Edge(ID(i,Total-1),ID(i-1,Total-1)); Add_Edge(ID(i-1,Total),ID(i,Total)); }
    FOR(i,2,Total) { Add_Edge(ID(i,Total),ID(i,Total-1)); }
    if(Total%2) {
        for(int i=2;i<=Total-3;i+=2) {
            Add_Edge(ID(Total,i),ID(Total-1,i));
            Add_Edge(ID(Total,i+1),ID(Total,i));
            Add_Edge(ID(Total-1,i+1),ID(Total,i+1));
        }
    }
    Solve();
    if(Total%2) { Ans[ID(Total,1)]=++Cnt; }
    FOR(i,1,Total) { FOR(j,1,Total) { cout<<Ans[ID(i,j)]<<" "; } cout<<endl; }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}