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;
}