Znzryb's Blog

CF-1009-D. Counting Points

Posted on 2025-05-09 Edited on 2026-04-06

思路讲解

其实不难，挺简单的。

我的思路是由于限制了半径的大小的总和，所以说可以把每个圆的每个x都扫一遍，扫到这个x了这个圆在这个x上包含了几个点就很容易知道了。然后把x上有多少个点被包含存在Cnt里就好了，最后扫一遍加起来就好。

FOR(i,1,N){
	ll r=xr[i][1],x=xr[i][0];
	FOR(j,x-r,x+r){
		ll len=abs(j-x);
		ll yCanChoose=sqrtl(r*r-len*len);
		yCanChoose*=2,yCanChoose+=1;
		if(Cnt.find(j)==Cnt.end()){
			Cnt[j]=yCanChoose;
		}else{
			Cnt[j]=max(yCanChoose,Cnt[j]);
		}
	}
}
ll ans=0;
for(auto ele:Cnt){
	ans+=ele.se;
}

AC代码

https://codeforces.com/contest/2074/submission/318915158

源代码

// Problem: D. Counting Points
// Contest: Codeforces - Codeforces Round 1009 (Div. 3)
// URL: https://codeforces.com/contest/2074/problem/D
// 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,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+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; // X[MAXN],R[MAXN];
arr xr[MAXN];
ll rToNum[MAXN];

inline void solve(){
	cin>>N>>M;
	map<ll,ll> Cnt;
	FOR(i,1,N){
		cin>>xr[i][0];
	}
	FOR(i,1,N){
		cin>>xr[i][1];
	}
	// sort(xr+1,xr+1+N);
	// ll ans=0;
	// FOR(i,1,N){
		// ll r=xr[i][1];
		// ans+=r;
	// }
	FOR(i,1,N){
		ll r=xr[i][1],x=xr[i][0];
		FOR(j,x-r,x+r){
			ll len=abs(j-x);
			ll yCanChoose=sqrtl(r*r-len*len);
			yCanChoose*=2,yCanChoose+=1;
			if(Cnt.find(j)==Cnt.end()){
				Cnt[j]=yCanChoose;
			}else{
				Cnt[j]=max(yCanChoose,Cnt[j]);
			}
		}
	}
	ll ans=0;
	for(auto ele:Cnt){
		ans+=ele.se;
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	FOR(i,1,MAXN-5){
		
	}
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2074/submission/318915158
*/

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

CF-1011-D. Serval and Kaitenzushi Buffet

Posted on 2025-05-08 Edited on 2026-04-06

思路讲解

K其实就是吃掉一个寿司所需要花费的时间。
你可以不停拿，但是最后要吃完，拿的时候不能吃。

这个其实是个贪心，这个把题目完全读完就可以得出。

https://www.luogu.com.cn/article/flnzpg4m 这个题解写的很清楚。

总的来说，其实就是这么选一定是合法的，但不一定最优。

而且可以证明所有的O是不能再往后移了，只能往前移。当然，往前移一定是合法的。

具体而言是这样的。

ll idx=0;
ROF(i,N,1){
	++idx;
	if(idx%(K+1)==0){
		spec[i]=true;
	}
}
priority_queue<ll> pq;
ll ans=0;
FOR(i,1,N){
	pq.push(D[i]);
	if(spec[i]){
		ans+=pq.top();
		pq.pop(); // 记得要弹出，不用清空，往前移比较多也是可以接受的。
	}
}

AC代码

https://codeforces.com/contest/2085/submission/319924135

源代码

// Problem: D. Serval and Kaitenzushi Buffet
// Contest: Codeforces - Codeforces Round 1011 (Div. 2)
// URL: https://codeforces.com/contest/2085/problem/D
// 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)
#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,D[MAXN];
bool spec[MAXN];
/*
K其实就是吃掉一个寿司所需要花费的时间。
你可以不停拿，但是最后要吃完，拿的时候不能吃。

*/
inline void solve(){
	cin>>N>>K;
	FOR(i,0,N+5){
		D[i]=0;
		spec[i]=false;
	}
	FOR(i,1,N){
		cin>>D[i];
	}
	ll idx=0;
	ROF(i,N,1){
		++idx;
		if(idx%(K+1)==0){
			spec[i]=true;
		}
	}
	priority_queue<ll> pq;
	ll ans=0;
	FOR(i,1,N){
		pq.push(D[i]);
		if(spec[i]){
			ans+=pq.top();
			pq.pop();
		}
	}
#ifdef LOCAL
    debugN(spec,N);
#endif
	cout<<ans<<"\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/2085/submission/319924135
*/

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

CF-1011-C. Serval and The Formula

Posted on 2025-05-08 Edited on 2026-04-06

思路讲解

$(x+k) + (y+k) = (x+k)\oplus (y+k) $ 等价于 $ (x+k)&(y+k)=0 $，其实就是不允许$ x+k$和 $y+k$ 这位都是 $1$ 的情况。

然后呢，这种题虽然主要的思想是按位分析，但是还是需要构造的，而且不要试图构造一些不特殊的，而是构造一些特殊的（如上所示）。

AC代码

https://codeforces.com/contest/2085/submission/318796295

源代码

// Problem: C. Serval and The Formula
// Contest: Codeforces - Codeforces Round 1011 (Div. 2)
// URL: https://codeforces.com/contest/2085/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>(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 X,Y;
ll bitX[35],bitY[35];
ll pow2[40];

inline void solve(){
	cin>>X>>Y;
	if(X==Y){
		cout<<-1<<"\n";
		return;
	}
	ll needPow=ceil(log2(max(X,Y)));
	ll ans=pow2[needPow]-max(X,Y);
#ifdef LOCAL
    cerr<<((X+ans)&(Y+ans))<<"\n";
#endif
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,35){
		pow2[i]=pow2[i-1]*2;
	}
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2085/submission/318796295
*/

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

之前陷入了错误思路中，认为是要按位分析，然后通过给每位+1避免出现11现象，其实这是很难的，因为进位会互相影响。

CF-1023-D. Apple Tree Traversing

Posted on 2025-05-07 Edited on 2026-04-06

思路讲解

题意就是所有点只能经过一次（选择一次），构造出字典序最大的 $(dis,u,v)$ 序列，输出这个序列。

注意到，距离是放在第一位的，所以我们肯定优先选择距离最大的。那在树上路径距离最大的是什么？树的直径呗。不过这个树的直径的取法需要优先选择大的起始点和终止点。

然后删除直径后，这张图就不联通了，只要在每个子图中我们遵循这种删除规律即可，最后形成的 ans 数组根据字典序规则排序即可。

以下是样例五的图示展示，第一层删完后，变为了两个子图，这两个子图仍然按照规则选择直径，删除直径上的点，整张图被删完后程序结束。

时间复杂度分析

枚举总量为 $n+(n-l_1)+(n-l_1-l_2)+\cdots+(n-l_c-\cdots-l_i-\cdots l_1)$ ，即 $n\times c -l_1 \times c-l_2 \times (c-1)-\cdots-l_c$ ，也就是，其中 $n$ 为点的数量， $l_i$ 为第 i 层的直径总数，c 为总层数。枚举总量在逐层下降是因为每层选择的直径上的点会被删除。

n 是给定的，那么我们假设 c 最大，那么 c 最大的情况是什么呢？

c 最大的情况，就是我们每层只能删除一条直径，也就是说该图在删除直径的过程中一直保持着联通状态。把层数卡满的图可以这样构造，注意到， $分枝直径的点的数量≤\lfloor直径的点的数量/2\rfloor$ ，如果大于这个限制，该分枝就要被删除了。

那么近似的，我们可以得到。

x+\frac{x}{2}+\frac{x}{2^2}+\cdots+\frac{x}{2^c}=n

由于 $\lfloor\frac{x}{2^c}\rfloor$ 必须大于 $0$ ，我们知道 $2^c≤x<2^{c+1}$ 。

那么不妨令 $x=2^{c+1}$ 。

2^{c+1}+2^c+\cdots+2=n

运用等比数列求和公式。

2\times(2^{c+1}-1)=n

因此， $c\approx \log(n)$ 。

故该算法的总体时间复杂度为 $O(nlogn)$ 。

AC代码

https://codeforces.com/contest/2107/submission/318737306

源代码

// Problem: D. Apple Tree Traversing
// Contest: Codeforces - Codeforces Round 1023 (Div. 2)
// URL: https://codeforces.com/contest/2107/problem/D
// Memory Limit: 512 MB
// Time Limit: 5000 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 deShow(var) cerr << #var <<":";
#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,2> 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;
vector<ll> g[MAXN];
bool vis[MAXN]/*,isVal[MAXN]*/;
vector<arr> disNode;
vector<ll> needDel;
ll st,ed,d;
set<ll> nodes;
bool removed[MAXN];

void dfs(ll x,ll d){
	disNode.pb({d,x});
	vis[x]=true;
	FOR(i,0,SZ(g[x])-1){
		ll node=g[x][i];
		if(vis[node]) continue;
		if(removed[node]) continue;
		dfs(node,d+1);
	}
}
bool dfsDia(ll x){	// 一个比较简单的树上dp？
	vis[x]=true;
	if(x==ed){
		needDel.pb(ed);
		return true;
	}
	bool rec=false;
	FOR(i,0,SZ(g[x])-1){
		ll node=g[x][i];
		if(vis[node]) continue;
		if(removed[node]) continue;
		rec|=dfsDia(node);
	}
	if(rec) needDel.pb(x);
	return rec;
}

inline void init(){
	disNode.clear(),needDel.clear();
	FOR(i,1,N){
		vis[i]=false;
	}
}

inline bool cmp(const array<ll,3> &a,const array<ll,3> &b){
	if(a[0]!=b[0]) return a[0]>b[0];
	if(a[1]!=b[1]) return a[1]>b[1];
	return a[2]>b[2];
}

inline void solve(){
	cin>>N;
	// 所有点只能经过一次（选择一次）
	// 构造出字典序最大的(d,u,v)序列，输出这个序列
	// d要大，u要大，v要大
	disNode.clear(),needDel.clear(),nodes.clear();
	FOR(i,1,N){
		vis[i]=false;
		nodes.insert(i);
		g[i].clear();
		removed[i]=false;
	}
	FOR(i,1,N-1){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	if(N==1){	// 特判
		cout<<"1 1 1\n";
		return;
	}
	dfs(1,0);
	sort(all(disNode));
	
#ifdef LOCAL
	deShow(disNode)
    FOR(i,0,SZ(disNode)-1){
    	cerr<<disNode[i][0]<<" "<<disNode[i][1]<<"\n";
    }
#endif

	st=disNode.back()[1];
	init();
	dfs(st,0);
	sort(all(disNode));
	ed=disNode.back()[1];
	d=disNode.back()[0];
	init();
	dfsDia(st);
	vector<array<ll,3>> ans;
	ans.pb({d+1,max(st,ed),min(st,ed)});
	for(const auto &node:needDel){
		nodes.erase(node);
		removed[node]=true;
	}
	for(const auto &node:nodes){
		vis[node]=false;
	}
	while(!nodes.empty()){
		disNode.clear(),needDel.clear();
		dfs(*nodes.begin(),0);
		sort(all(disNode));
		st=disNode.back()[1];
		FOR(i,0,SZ(disNode)-1){
			vis[disNode[i][1]]=false;
		}
		disNode.clear(),needDel.clear();
		dfs(st,0);
		sort(all(disNode));
		ed=disNode.back()[1];
		d=disNode.back()[0];
		ans.pb({d+1,max(st,ed),min(st,ed)});
		FOR(i,0,SZ(disNode)-1){
			vis[disNode[i][1]]=false;
		}
		dfsDia(st);
		FOR(i,0,SZ(disNode)-1){
			vis[disNode[i][1]]=false;
		}
		for(const auto &node:needDel){
			nodes.erase(node);
			removed[node]=true;
		}
	}
	sort(all(ans),cmp);
	FOR(i,0,SZ(ans)-1){
		cout<<ans[i][0]<<" "<<ans[i][1]<<" "<<ans[i][2]<<" ";
	}
	cout<<"\n";
#ifdef LOCAL
    DEBUG(needDel);
    cerr<<"\n";
#endif
}

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/2107/submission/318737306
*/

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

CF-1018-C. Wonderful City

Posted on 2025-05-06 Edited on 2026-04-06

思路讲解

唉，dp，你说没想到吧，也想到了一点，但没往下深想。

唉，主要想错了，这个行和列是相互独立的。

其实就是出现两者之间相差一的情况，那么这个比较小的列就无法加一了。

但其实上面这个说法不全面，导致我的算法设计有瑕疵，比如说下面这个例子

1
4
3 1 1 3    3 2    4 2
4 5 4 5 -> 4 6 -> 5 6
3 1 3 5    3 2    4 2
4 3 2 1    4 4    5 4
5 1 5 2
4 9 1 9

不难发现，上面这个例子还有可能传递，如第 $n$ 列需要 $+1$ 但是和第 $n-1$ 列相同了，所以第 $n-1$ 列也需要 $+1$ ，但 $n-1$ 列和第 $n-2$ 列相同了……。

当然，上面说了这么多，其实意思只有一个，就是不能以需要操作的行和列为主体，而应该以所有列为主体，因为操作行和列的操作可能导致其他行和列也需要操作。

不过，我们也发现行和列能怎么操作也只和相邻的行和列相关，那么如果按顺序转移也是可以的。

状态定义如下所列。

1
2
3

// dpC[i][0] 表示保留第i列所需的最小花费
// dpC[i][1] 表示对第i列+1所需的最小花费
ll dpC[MAXN][2],dpR[MAXN][2];

转移只要确定是否合法其实就很简单了。

AC代码

https://codeforces.com/contest/2096/submission/318683142

源代码

// Problem: C. Wonderful City
// Contest: Codeforces - Neowise Labs Contest 1 (Codeforces Round 1018, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2096/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>(1e14)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,A[MAXN],B[MAXN];
ll H[MAXN][MAXN];
// bool vaC[MAXN],vaR[MAXN];
ll dr[4]={1,0,-1,0};
ll dc[4]={0,-1,0,1};
// dpC[i][0] 表示保留第i列，dpC[i][1] 表示对第i列+1所需的最小花费
ll dpC[MAXN][2],dpR[MAXN][2];

inline void solve(){
	cin>>N;
	FOR(i,0,N+5){
		dpC[i][0]=INF,dpC[i][1]=INF;
		dpR[i][0]=INF,dpR[i][1]=INF;
		FOR(j,0,N+5){
			H[i][j]=INF;
			
		}
	}
	FOR(i,1,N){
		FOR(j,1,N){
			cin>>H[i][j];
		}
	}
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,N){
		cin>>B[i];
	}
	dpR[1][0]=0;
	dpR[1][1]=A[1];
	FOR(r,2,N){
		bool zeroTo0=true;
		FOR(c,1,N){
			if(H[r][c]==H[r-1][c]){
				zeroTo0=false;
				break;
			}
		}
		if(zeroTo0){
			dpR[r][0]=min(dpR[r][0],dpR[r-1][0]);
		}
		bool zeroTo1=true;
		FOR(c,1,N){
			if(H[r-1][c]-H[r][c]==1){
				zeroTo1=false;
				break;
			}
		}
		if(zeroTo1){
			dpR[r][1]=min(dpR[r][1],dpR[r-1][0]+A[r]);
		}
		bool oneTo0=true;
		FOR(c,1,N){
			if(H[r-1][c]+1-H[r][c]==0){
				oneTo0=false;
				break;
			}
		}
		if(oneTo0){
			dpR[r][0]=min(dpR[r][0],dpR[r-1][1]);
		}
		bool oneTo1=true;
		FOR(c,1,N){
			if(H[r-1][c]-H[r][c]==0){
				oneTo1=false;
				break;
			}
		}
		if(oneTo1){
			dpR[r][1]=min(dpR[r][1],dpR[r-1][1]+A[r]);
		}
	}
	dpC[1][0]=0;
	dpC[1][1]=B[1];
	FOR(c,2,N){
		bool zeroTo0=true;
		FOR(r,1,N){
			if(H[r][c]==H[r][c-1]){
				zeroTo0=false;
				break;
			}
		}
		if(zeroTo0){
			dpC[c][0]=min(dpC[c][0],dpC[c-1][0]);
		}
		bool zeroTo1=true;
		FOR(r,1,N){
			if(H[r][c-1]-H[r][c]==1){
				zeroTo1=false;
				break;
			}
		}
		if(zeroTo1){
			dpC[c][1]=min(dpC[c][1],dpC[c-1][0]+B[c]);
		}
		bool oneTo0=true;
		FOR(r,1,N){
			if(H[r][c-1]+1-H[r][c]==0){
				oneTo0=false;
				break;
			}
		}
		if(oneTo0){
			dpC[c][0]=min(dpC[c][0],dpC[c-1][1]);
		}
		bool oneTo1=true;
		FOR(r,1,N){
			if(H[r][c-1]-H[r][c]==0){
				oneTo1=false;
				break;
			}
		}
		if(oneTo1){
			dpC[c][1]=min(dpC[c][1],dpC[c-1][1]+B[c]);
		}
	}
	ll ans=min(dpR[N][1],dpR[N][0])+min(dpC[N][1],dpC[N][0]);
	cout<<(ans>=INF?-1:ans)<<"\n";
#ifdef LOCAL
    cerr<<"dpR:\n";
    FOR(i,0,N){
    	cerr<<dpR[i][0]<<" ";
    }
    cerr<<"\n";
    FOR(i,0,N){
    	cerr<<dpR[i][1]<<" ";
    }
    cerr<<"\n";
    cerr<<"dpC:\n";
    FOR(i,0,N){
    	cerr<<dpC[i][0]<<" ";
    }
    cerr<<"\n";
    FOR(i,0,N){
    	cerr<<dpC[i][1]<<" ";
    }
    cerr<<"\n";
    cerr<<"\n";
#endif
}

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/2096/submission/318683142
*/