Znzryb's Blog

一些常见的trick

Posted on 2025-05-15 Edited on 2026-03-14

思路讲解

【Codeforces Round 1024 (Div. 2) 题目讲解 ABCDE (CF2102)】【精准空降到 16:30】 https://www.bilibili.com/video/BV1CFELzVExf/?p=5&share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=990

这场的E题，用到了一个技巧，就是2，2，3，4 → 1，2，3，4 这如何利用set就能做到（维护一个序列，要求 $a_i≥ i$ ，然后给你一堆数，要求你能够最长化这个序列）？其实可以换个思路，初始的 set 里有 1，2，3，4，5 然后删。

具体见CF-1024-E. 23 Kingdom。

CF-1028-D. Gellyfish and Camellia Japonica（直接构造等于难，构造最小的大于等于）

https://www.luogu.com.cn/article/rae0b6wl

总结的话，主要的启发就是把 构造使得与目标相等 转换成 最小的构造使得大于等于目标。

方法论之解决后效性的方法

Posted on 2025-05-13 Edited on 2026-03-14

介绍

消除后效性，狭义上指的是dp，但广义上来说，贪心做法等也有时需要考虑后效性问题。

总体而言，只要你是想要把一个问题拆开来分析求解，那么合起来的时候，就要考虑后效性了。

案例分析

CF-1024-D. Quartet Swapping（四重交换）这个是解决了交换数量要保持相同，但是最优情况可能无法保持相同，如何找到次优情况呢？或者说什么发现该情况只适用于次优情况呢？涉及冒泡排序以及逆序对。

2025金马高校联赛-B战术单元协同训练利用链表来消除后效性

Edu-179-E. Changing the String 在线处理比较难，需要考虑对后续操作的影响，可以采用离线方法处理，因为下标小的。

CF-1024-E. 23 Kingdom

Posted on 2025-05-13 Edited on 2026-02-16

思路讲解

不难注意到，你所选择的区间之中，不允许出现两个区间相离的情况。

因为这两个区间如果变为相交的话，贡献的答案值一定更大。

由这个结论，那么新加入的区间的 $右端点>以前的所有左端点$ ，并且 $左端点<以前的所有右端点$ ，因此，所有的左右端点就会分居两端，因为起始的 $右端点>左端点$ ，新加入的 $右端点>以前的所有左端点$ ，左端点反之亦然。

那么贪心地，我们其实就是想让 $\sum{i_l}$ 最小， $\sum{i_r}$ 最大，那么左端点只要贪心地选择下标小的，右端点我们只要贪心地选择下标大的。

最后一个问题，就是当我们拿到一个序列，如 $2，2，3，4$ ，我们如何知道他是否可以映射到 $1，2，3，4$ 只通过减法。

那么这个其实有一个小的 trick，如果说用加入元素的方法判断，大抵是要用到树状数组或者线段树，但如果使用删除的方法，就可以只用 set 实现。

set<ll> st;
auto init=[&](){  // 初始化函数
	st.clear();
	FOR(i,0,N+1){
		st.insert(i);
	}
};
auto proc=[&](ll x){  // 处理函数
	auto it=st.upper_bound(x);
	--it;
	if(*it==0){
		return false;
	}else{
		st.erase(it);
		return true;
	}
};

AC代码

https://codeforces.com/contest/2101/submission/319792559

源代码

// Problem: C. 23 Kingdom
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/C
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define debugN(var,N) \
	do{ \
		std::cerr<<#var<<":"; \
		FOR(i,1,N){ \
			std::cerr<<var[i]<<" "; \
		} \
		std::cerr<<"\n"; \
	}while(0)
#define debugMap(variable) \
    do { \
        std::cerr << #variable << ":\n"; \
        for (const auto& pair : variable) { \
            std::cerr << "  " << pair.first << " => " << pair.second << "\n"; \
        } \
        std::cerr << std::endl; \
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
/*
根据题意，A就代表了B数组的上界。
1 5 2 8 4 1 4 2
1 4 2 3 3 1 4 2
*/

ll Pre[MAXN],Suf[MAXN],sufSum[MAXN],preSum[MAXN];
inline void solve(){
	cin>>N;
	FOR(i,0,N+5){
		Pre[i]=0;
		Suf[i]=0;
		sufSum[i]=0;
		preSum[i]=0;
	}
	set<ll> st;
	auto init=[&](){
		st.clear();
		FOR(i,0,N+1){
			st.insert(i);
		}
	};
	auto proc=[&](ll x){
		auto it=st.upper_bound(x);
		--it;
		if(*it==0){
			return false;
		}else{
			st.erase(it);
			return true;
		}
	};
	init();
	ll ind=0;
	vector<ll> mp(N+5,0),mp2(N+5,0);
	FOR(i,1,N){
		cin>>A[i];
		if(proc(A[i])){
			++ind;
			mp[ind]=mp[ind-1]+i;
		}
		Pre[i]=ind;
	}
	mp[0]=0;
	ind=0;
	init();
	ROF(i,N,1){
		if(proc(A[i])){
			++ind;
			mp2[ind]=mp2[ind-1]+i;
		}
		Suf[i]=ind;
	}
	
	
#ifdef LOCAL
    debugN(preSum,N);
    debugN(sufSum,N);
    debugN(Pre,N);
    debugN(Suf,N);
    DEBUG(mp);
    DEBUG(mp2);
#endif
	ll ans=0,up=0;
	
	FOR(i,1,N-1){
		up=max(up,min(Pre[i],Suf[i+1]));
	}
#ifdef LOCAL
    debug(up);
#endif
	FOR(i,1,up){
		ans=max(ans,mp2[i]-mp[i]);
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
#ifdef LOCAL
    cerr << "---------------" << '\n';
#endif
	}
	// solve();
	return 0;
}
/*
hack:
1
10
1 1 2 2 3 3 4 4 5 5
ans:
18

AC https://codeforces.com/contest/2101/submission/319792559
*/

心路历程（WA，TLE，MLE……）

其实我们的要求是没有任意两个区间相离，这个用线段树判断是有点问题的。

一个比较好的近似解

hack:
1
10
1 1 2 2 3 3 4 4 5 5
ans:
18

https://codeforces.com/contest/2101/submission/319732582

源代码

// Problem: C. 23 Kingdom
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/C
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
ll posMatch[MAXN];
/*
根据题意，A就代表了B数组的上界。
1 5 2 8 4 1 4 2
1 4 2 3 3 1 4 2
*/
vector<ll> pos[MAXN];
struct Tree{
	ll l,r,sum,add;
}tr[MAXN];

void build(ll node,ll l,ll r){
	tr[node].sum=0,tr[node].add=0;
	tr[node].l=l,tr[node].r=r;
	if(tr[node].l>=tr[node].r) return;
	tr[lson(node)].l=l;
	tr[lson(node)].r=l+(r-l)/2;
	tr[rson(node)].r=r;
	tr[rson(node)].l=tr[lson(node)].r+1;
	build(lson(node),tr[lson(node)].l,tr[lson(node)].r);
	build(rson(node),tr[rson(node)].l,tr[rson(node)].r);
}

inline void pushdown(ll node){
	if(tr[node].l==tr[node].r) return;
	tr[lson(node)].sum+=tr[node].add*(tr[lson(node)].r-tr[lson(node)].l+1);
	tr[rson(node)].sum+=tr[node].add*(tr[rson(node)].r-tr[rson(node)].l+1);
	tr[lson(node)].add+=tr[node].add;
	tr[rson(node)].add+=tr[node].add;
	tr[node].add=0;
}
inline void pushup(ll node,ll val){
	node>>=1;
	while(node){
		tr[node].sum+=val;
		node>>=1;
	}
}
inline bool isInter(ll l,ll r,ll l1,ll r2){
	if(l>r2) return false;
	if(r<l1) return false;
	return true;
}
void add(ll node,ll l,ll r,ll val){
	pushdown(node);
	if(tr[node].l>=l && tr[node].r<=r){
		ll num=tr[node].r-tr[node].l+1;
		tr[node].sum+=val*num;
		tr[node].add+=val;
		pushup(node,val*num);
		return;
	}
	if(isInter(tr[lson(node)].l,tr[lson(node)].r,l,r)) add(lson(node),l,r,val);
	if(isInter(tr[rson(node)].l,tr[rson(node)].r,l,r)) add(rson(node),l,r,val);
}
ll query(ll node,ll l,ll r){
	pushdown(node);
	if(tr[node].l>=l && tr[node].r<=r){
		return tr[node].sum;
	}
	ll res=0;
	if(isInter(tr[lson(node)].l,tr[lson(node)].r,l,r)) res+=query(lson(node),l,r);
	if(isInter(tr[rson(node)].l,tr[rson(node)].r,l,r)) res+=query(rson(node),l,r);
	return res;
}
inline void solve(){
	cin>>N;
	FOR(i,0,N+5){
		posMatch[i]=0;
	}
	FOR(i,1,N){
		pos[i].clear();
	}
	FOR(i,1,N){
		cin>>A[i];
		pos[A[i]].pb(i);
	}
	build(1,1,N);
	set<ll> st,stEd;	// st保存的是现在可用的，stEd是已经用过的。
	ll ans=0;
	ROF(i,N,1){
		st.insert(pos[i].begin(),pos[i].end());
		if(SZ(st)>=2){
			ll beg=*st.begin(),ed=*st.rbegin();
			ll res=query(1,beg,ed);
			if(res>0){	// 只要有区间相交，那么就取用最大区间即可
				add(1,beg,ed,1);
				ans+=ed-beg;
				stEd.insert(beg);	// 已经用过，在已经用过中增加
				stEd.insert(ed);
				posMatch[beg]=ed;
				posMatch[ed]=beg;
				st.erase(st.begin());	// 已经用过了，在可用中删除
				st.erase(--st.end());
			}else{	// 没有与其他区间相交，那么就需要上一点手段了
				if(SZ(stEd)>=2){	// 理论上来说stEd不是空的就是
					// stEd不是空的，那我们就需要让区间们相交
					ll mnEd=*stEd.begin(),mxEd=*stEd.rbegin();
					ll len1=ed-mnEd,len2=mxEd-beg,oldLen1=posMatch[mnEd]-mnEd,
					oldLen2=mxEd-posMatch[mxEd];
					ll eff1=len1-oldLen1,eff2=len2-oldLen2;
					if(eff1>eff2 && eff1>0){
						add(1,mnEd,ed,1);
						st.erase(ed);
						ans+=eff1;
						stEd.erase(posMatch[mnEd]);
						st.insert(posMatch[mnEd]);
						posMatch[mnEd]=ed;
						posMatch[ed]=mnEd;
						stEd.insert(ed);
					}else if(eff2>0){
						// 有一段重复加了？没关系，这个值只是表示这段区间有东西。
						add(1,beg,mxEd,1);
						st.erase(beg);
						ans+=eff2;
						stEd.erase(posMatch[mxEd]);
						st.insert(posMatch[mxEd]);
						posMatch[mxEd]=beg;
						posMatch[beg]=mxEd;
						stEd.insert(beg);
					}
				}else{	// stEd是空的，和res>0一样处理
					add(1,beg,ed,1);
					ans+=ed-beg;
					stEd.insert(beg);	// 已经用过，在已经用过中增加
					stEd.insert(ed);
					posMatch[beg]=ed;
					posMatch[ed]=beg;
					st.erase(st.begin());	// 已经用过了，在可用中删除
					st.erase(--st.end());
				}
			}
		}else if(SZ(st)==1){
			ll ed=*st.begin(),beg=*st.begin();
			if(SZ(stEd)>=2){	// 理论上来说stEd不是空的就是
					// stEd不是空的，那我们就需要让区间们相交
					ll mnEd=*stEd.begin(),mxEd=*stEd.rbegin();
					ll len1=ed-mnEd,len2=mxEd-beg,oldLen1=posMatch[mnEd]-mnEd,
					oldLen2=mxEd-posMatch[mxEd];
					ll eff1=len1-oldLen1,eff2=len2-oldLen2;
					if(eff1>eff2 && eff1>0){
						add(1,mnEd,ed,1);
						st.erase(ed);
						ans+=eff1;
						stEd.erase(posMatch[mnEd]);
						st.insert(posMatch[mnEd]);
						posMatch[mnEd]=ed;
						posMatch[ed]=mnEd;
						stEd.insert(ed);
					}else if(eff2>0){
						// 有一段重复加了？没关系，这个值只是表示这段区间有东西。
						add(1,beg,mxEd,1);
						st.erase(beg);
						ans+=eff2;
						stEd.erase(posMatch[mxEd]);
						st.insert(posMatch[mxEd]);
						posMatch[mxEd]=beg;
						posMatch[beg]=mxEd;
						stEd.insert(beg);
					}
				}
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
#ifdef LOCAL
    cerr << "---------------" << '\n';
#endif
	}
	// solve();
	return 0;
}
/*

*/

CF-1024-D. Quartet Swapping（四重交换）

Posted on 2025-05-13 Edited on 2026-03-26

思路讲解

那么注意到，在该操作过程中，一个数下标的的奇偶性是不会发生变化的。
还有一个比较隐秘的不变量就是偶数下标的反转数和奇数下标的反转数是相同的，因为每次交换相邻偶数下标时, 会迫不得己地同时交换奇数下标，反之亦然。

那么要用到我们观察出来的第二个性质，就是偶数下标的反转数和奇数下标的反转数是相同的，那么如果说偶数下标序列和奇数下标序列的逆序对数量的奇偶性不相同（逆序对数量其实也就是需交换操作数量，因为本道题目是只能相邻交换，相当于冒泡排序），那么就说明必须要牺牲一个不反转（或者有时是在有序的基础上，再多反转一个，反正无论是 $+1$ 还是 $-1$ 以后奇偶性一定就相同了）。

那么应该反转哪个最优呢？不难发现这样交换最优。

1
2
3

if((revOdd-revEven)%2!=0){
	swap(Ans[N],Ans[N-2]);
}

AC代码

https://codeforces.com/contest/2101/submission/319512581

源代码

// Problem: B. Quartet Swapping
// Contest: Codeforces - Codeforces Round 1024 (Div. 1)
// URL: https://codeforces.com/contest/2101/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN];
ll Ans[MAXN];
/*
交换ai和ai+2，交换ai+1和ai+3
输出通过该操作能够达到的字典序最小的数组
其实就是把两个数当成一块然后换个位置

那么注意到，在该操作过程中，一个数位置的奇偶性是不会发生变化的。
还有一个比较隐秘的不变量就是反转数的奇偶性，因为每次交换相邻偶数下标时, 会迫不得己地同时交换奇数下标。
然后呢，这个其实除了最后的3个位置，其实前面的位置按照奇偶性排序输出即可。

那么最后的问题。最后三个元素的位置是什么？那么其实就是要么就是一奇二偶，要么就是一偶二奇。
奇偶之间亦无需多言，那么就是偶偶奇奇之间如何判断的问题。
*/
struct BIT {  // 普通的单点修改区间查询树状数组，含有查找第K个空位的功能
  vector<ll> tr;
  int n;
  inline int lowbit(int x) { return x & (-x); }
  BIT(int ln) {  // 构造+初始化函数
    n = ln;
    tr.resize(n+5,0);
  }
  inline void add(int p, int x) {
  	if(p==0) return;
    while (p <= n) {
      tr[p] += x;
      p += lowbit(p);
    }
  }
  inline ll query(int l, int r) {
    ll lres = 0, rres = 0;
    l -= 1;
    while (l > 0) {
      lres += tr[l];
      l -= lowbit(l);
    }
    while (r > 0) {
      rres += tr[r];
      r -= lowbit(r);
    }
    return rres - lres;
  }
  inline int findKth(int k) {  // 找到第k个空位
    int cx = 0;
    for (int i = 1 << 20; i > 0; i >>= 1) {  // 这个你可以理解为不断缩小步长的搜索
      if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
        // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
        k -= lowbit(cx + i) - tr[cx + i];
        cx += i;
      }
    }
    return cx + 1;  // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
  }
};
inline void solve(){
	cin>>N;
	priority_queue<ll,vector<ll>,greater<ll>> pqOdd,pqEven;
	BIT oddTree(N),evenTree(N);
	ll revOdd=0,revEven=0;
	FOR(i,1,N){
		cin>>A[i];
		if(i%2==0){
			pqEven.push(A[i]);
			revEven+=evenTree.query(A[i]+1,N);
			evenTree.add(A[i],1);
		}else{
			pqOdd.push(A[i]);
			revOdd+=oddTree.query(A[i]+1,N);
			oddTree.add(A[i],1);
		}
	}
	FOR(i,1,N){
		if(i%2==0){
			Ans[i]=pqEven.top();
			pqEven.pop();
		}else{
			Ans[i]=pqOdd.top();
			pqOdd.pop();
		}
	}
	if((revOdd-revEven)%2!=0){
		swap(Ans[N],Ans[N-2]);
	}
	FOR(i,1,N){
		cout<<Ans[i]<<" ";
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2101/submission/319512581
*/

心路历程（WA，TLE，MLE……）

CF-1024-C. Mex in the Grid（蛇形构造转圈矩阵）

Posted on 2025-05-12 Edited on 2026-02-16

思路讲解

从外往里转会好很多。

AC代码

https://codeforces.com/contest/2102/submission/319351416

源代码

// Problem: C. Mex in the Grid
// Contest: Codeforces - Codeforces Round 1024 (Div. 2)
// URL: https://codeforces.com/contest/2102/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T;
ll maze[MAXN][MAXN];
ll vis[MAXN][MAXN];
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
/*
678  0->1->2->3,...,->8
501
432
从外往里转会好很多。
*/
inline void solve(){
	cin>>N;
	FOR(i,0,N+5){
		FOR(j,0,N+5){
			maze[i][j]=-1;
		}
	}
	ll idx=N*N-1;
	ll x=N,y=N,dir=3;
	while(idx>=0){
#ifdef LOCAL
    if(idx==1){
		debug(dir)
	}
#endif
		maze[x][y]=idx;
		--idx;
#ifdef LOCAL
    FOR(i,1,N){
		FOR(j,1,N){
			cerr<<maze[i][j]<<" ";
		}
		cerr<<"\n";
	}
	cerr<<"\n";
#endif
		if(x+dx[dir]>N || x+dx[dir]<1){
			dir--;
		}else if(y+dy[dir]>N || y+dy[dir]<1){
			--dir;
		}else if(maze[x+dx[dir]][y+dy[dir]]!=-1){
			--dir;
		}
		dir%=4;
		if(dir<0) dir+=4;
		x+=dx[dir];
		y+=dy[dir];
	}
	FOR(i,1,N){
		FOR(j,1,N){
			cout<<maze[i][j]<<" ";
		}
		cout<<"\n";
	}
#ifdef LOCAL
    FOR(i,0,N+5){
		FOR(j,0,N+5){
			cerr<<maze[i][j]<<" ";
		}
		cerr<<"\n";
	}
	cerr<<"\n";
#endif
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
#ifdef LOCAL
    cerr << "-----------" << '\n';
#endif
	}
	// solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

从里往外转比较烦。

源代码

// Problem: C. Mex in the Grid
// Contest: Codeforces - Codeforces Round 1024 (Div. 2)
// URL: https://codeforces.com/contest/2102/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T;
ll maze[MAXN][MAXN];
ll vis[MAXN][MAXN];
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
/*
678  0->1->2->3,...,->8
501
432
*/
ll idx=0;
void dfs(ll x,ll y,ll step,ll cnt,ll dir){
	if(idx>N*N-1){
		return;
	}
	dir%=4;
	if(cnt>3){
		cnt=1;
		step+=1;
		ll dir_1=(dir-1)%4;
		if(dir_1<0) dir_1+=4;
		maze[x][y]=idx;
		++idx;
		x+=dx[dir_1];
		y+=dy[dir_1];
	}
	
	if(dir==0){
		FOR(i,y,y+step-2){
			maze[x][i]=idx;
			++idx;
		}
		dfs(x,y+step-1,step,cnt+1,dir+1);
	}else if(dir==1){
		FOR(i,x,x+step-2){
			maze[i][y]=idx;
			++idx;
		}
		dfs(x+step-1,y,step,cnt+1,dir+1);
	}else if(dir==2){
		ROF(i,y,y-step+2){
			maze[x][i]=idx;
			++idx;
		}
		dfs(x,y-step+1,step,cnt+1,dir+1);
	}else{
		ROF(i,x,x-step+2){
			maze[i][y]=idx;
			++idx;
		}
		dfs(x-step+1,y,step,cnt+1,dir+1);
	}
	
}
inline void solve(){
	cin>>N;
	ll n2=ceil(N*1.0/2);
	FOR(i,0,N+5){
		FOR(j,0,N+5){
			maze[i][j]=-1;
			vis[i][j]=false;
		}
	}
	idx=0;
	dfs(n2,n2,2,1,0);
#ifdef LOCAL
    FOR(i,0,N+5){
		FOR(j,0,N+5){
			cerr<<maze[i][j]<<" ";
		}
		cerr<<"\n";
	}
	cerr<<"\n";
#endif
	FOR(i,1,N){
		FOR(j,1,N){
			cout<<maze[i][j]<<" ";
		}
		cout<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/