THUSC2017 Day1题解
巧克力
题目描述
“人生就像一盒巧克力，你永远不知道吃到的下一块是什么味道。”
明明收到了一大块巧克力，里面有若干小块，排成n行m列。每一小块都有自己特别的图案ci,j，它们有的是海星，有的是贝壳，有的是海螺......其中还有一些因为挤压，已经分辨不出是什么图案了。明明给每一小块巧克力标上了一个美味值\(a_{i,j }( 0 \le a_{i,j} \le 10^6 )\)，这个值越大，表示这一小块巧克力越美味。
正当明明咽了咽口水，准备享用美味时，舟舟神奇地出现了。看到舟舟恳求的目光，明明决定从中选出一些小块与舟舟一同分享。
舟舟希望这些被选出的巧克力是连通的（两块巧克力连通当且仅当他们有公共边），而且这些巧克力要包含至少\(k ( 1 \le k \le 5 )\)种。而那些被挤压过的巧克力则是不能被选中的。
明明想满足舟舟的愿望，但他又有点“抠”，想将美味尽可能多地留给自己。所以明明希望选出的巧克力块数能够尽可能地少。如果在选出的块数最少的前提下，美味值的中位数（我们定义\(n\)个数的中位数为第\(⌊\frac{n+1}{2}⌋\)小的数）能够达到最小就更好了。
你能帮帮明明吗？
输入格式
从标准输入读入数据。
每个测试点包含多组测试数据。
输入第一行包含一个正整数 \(T (1 \le T \le 5)\)，表示测试数据组数。
对于每组测试数据：
输入第一行包含三个正整数\(n,m\)和\(k\)；
接下来\(n\)行，每行\(m\)个整数，表示每小块的图案\(c_{i,j}\)。若\(c_{i,j}=−1\)表示这一小块受到过挤压，不能被选中；
接下来\(n\)行，每行\(m\)个整数，表示每个小块的美味值\(a_{i,j}\)。
输出格式
输出到标准输出。
输出共包括\(T\)行，每行包含两个整数，用空格隔开，即最少的块数和最小的美味值中位数。
若对于某组测试数据，不存在任意一种合法的选取方案，请在对应行输出两个\(−1\)。
数据范围
\(n \times m \le 233\)
题解
我们发现这个至少有\(k\)种颜色非常不好处理，我们就把所有颜色随机分到\(k\)个块里，只要每个块的颜色都被取到，那就说明至少有\(k\)个颜色
直接二分中位数，每次随机颜色块，做一遍斯坦纳树即可。这里有个技巧就是把大于中位数的赋值成\(1001\)，其他的赋成的\(999\)，设求出来的最小值为\(Min\)，则最少块数为\(\frac{Min+500}{1000}\)，同时也可以通过与答案\(\times 1000\)的大小比较来check中位数
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') f=-1,c=getchar();
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') f=-1,c=getchar();
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxn=233+10,inf=0x3f3f3f3f;
int N,id[maxn][maxn],dp[1<<5][maxn],vis[1<<5][maxn];
int col[maxn],c[maxn][maxn],val[maxn],a[maxn][maxn];
int idx[maxn],idx_cnt,Min;
int num[maxn],k;
int Begin[maxn],Next[maxn*10],to[maxn*10],e;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
inline void add_edge(int x,int y){
to[++e]=y;
Next[e]=Begin[x];
Begin[x]=e;
}
struct point{
int x,y;
};
inline void spfa(int Nw){
queue<point> q;
REP(i,1,N) vis[Nw][i]=1,q.push((point){Nw,i});
while(!q.empty()){
point u=q.front();q.pop();
for(int i=Begin[u.y];i;i=Next[i]){
point v;
v.y=to[i],v.x=u.x;
if(col[to[i]]==-1) continue;
v.x|=(1<<col[to[i]]);
if(chkmin(dp[v.x][v.y],dp[u.x][u.y]+val[to[i]]))
if(!vis[v.x][v.y]){
vis[v.x][v.y]=1;
q.push(v);
}
vis[u.x][u.y]=0;
}
}
}
inline void Steiner_tree(){
memset(dp,inf,sizeof(dp));
REP(i,1,N)
if(col[i]!=-1) dp[1<<col[i]][i]=val[i];
REP(i,1,(1<<k)-1){
REP(j,1,N){
int x,y;
if(col[j]!=-1) y=(1<<col[j]);
else y=0;
if(!y) continue;
if((i&y)!=y) continue;
x=(i^y);
for(int u=x;u;u=(u-1)&x) chkmin(dp[i][j],dp[u|y][j]+dp[(u^x)|y][j]-val[j]);
}
spfa(i);
REP(j,1,N) for(int u=(i-1)&i;u;u=(u-1)&i) chkmin(dp[u][j],dp[i][j]);
}
REP(i,1,N) chkmin(Min,dp[(1<<k)-1][i]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
srand(234111);
int T=read();
while(T--){
int n=read(),m=read();
k=read();
N=idx_cnt=0;
REP(i,1,n) REP(j,1,m) id[i][j]=++N;
REP(i,1,n) REP(j,1,m) c[i][j]=read();
REP(i,1,n) REP(j,1,m) a[i][j]=read(),idx[++idx_cnt]=a[i][j];
e=0;
REP(i,1,N) Begin[i]=0;
sort(idx+1,idx+idx_cnt+1);
idx_cnt=unique(idx+1,idx+idx_cnt+1)-idx-1;
REP(i,1,n) REP(j,1,m) REP(x,0,3){
int u=i+dir[x][0],v=j+dir[x][1];
if(u>n || u<1 || v>m || v<1) continue;
// cout<<i<<' '<<j<<' '<<u<<' '<<v<<endl;
add_edge(id[i][j],id[u][v]);
}
int L=1,R=idx_cnt;
int ans=inf;
while(L<=R){
int Mid=(L+R)>>1;
Min=inf;
REP(i,1,n) REP(j,1,m)
if(a[i][j]>idx[Mid]) val[id[i][j]]=1001;
else val[id[i][j]]=999;
REP(_,1,200){
REP(i,1,N) num[i]=rand()%k;
REP(i,1,n) REP(j,1,m)
if(c[i][j]==-1) col[id[i][j]]=-1;
else col[id[i][j]]=num[c[i][j]];
Steiner_tree();
}
ans=(Min+500)/1000;
// cerr<<Mid<<' '<<Min<<endl;
if(Min<=ans*1000) R=Mid-1;
else L=Mid+1;
}
if(ans>N) printf("-1\n");
else printf("%d %d\n",ans,idx[R+1]);
}
return 0;
}
杜老师
题目描述
杜老师可是要打\(+\infty\)年\(World Final\)的男人，虽然规则不允许，但是可以改啊！
但是今年\(WF\)跟\(THUSC\)的时间这么近，所以他造了一个\(idea\)就扔下不管了……
给定\(L,R\)，求从\(L\)到\(R\)的这\(R−L+1\)个数中能选出多少个不同的子集，满足子集中所有的数的乘积是一个完全平方数。特别地，空集也算一种选法，定义其乘积为\(1\)。
由于杜老师忙于跟陈老师和鏼老师一起打ACM竞赛，所以，你能帮帮杜老师写写标算吗？
输入格式
从标准输入读入数据。
每个测试点包含多组测试数据。
输入第一行包含一个正整数 \(T (1 \le T \le 100)\)，表示测试数据组数。
接下来\(T\)行，第\(i+1\)行两个正整数\(L_i,R_i\)表示第 i 组测试数据的 \(L,R\) ，保证\(1 \le L_i \le R_i \le 10^7\)。
输出格式
输出到标准输出。
输出\(T\)行，每行一个非负整数，表示一共可以选出多少个满足条件的子集，答案对\(998244353\)取模。
数据范围
\(R_i \le 10^7, \sum R_i-L_i \le 6 \times 10 ^7\)
题解
首先很容易想到分解质因数，然后对于每一个数\(x\)，可以变成一个二进制数，二进制数的第\(i\)位代表\(x\)包含奇数还是偶数个\(p_i\)的质因子。之后就求出线性基，那么答案即为\(*元个数2^{*元个数}\).这样可以拿到\(50\)分
然后我一开始在看这道题的时候，我发现了两个结论：
1.当\(\frac{R}{L} \ge p_i\)时\(i\)这一位一定有基
2.当\(p_i > \sqrt{R}\)是\(i\)这一位一定有基
我一开始判掉两个结论，然后剩下的直接暴力高斯消元有\(80\)分
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') f=-1,c=getchar();
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') f=-1,c=getchar();
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxm=1e7+10,maxn=1000+10,mod=998244353;
int prime[maxm],isprime[maxm],Max[maxm],cnt;
inline void init(int n){
REP(i,2,n){
if(!isprime[i]) prime[++cnt]=i,Max[i]=cnt;
REP(j,1,cnt){
int u=i*prime[j];
if(u>n) break;
isprime[u]=1;
Max[u]=max(Max[i],j);
if(i%prime[j]==0) break;
}
}
}
ll bit[maxn][maxn],a[maxn],num[maxn];
int tmp,tot,All;
bool p[maxn];
int ans,Begin[maxm],to[maxm*10],Next[maxm*10],e;
inline void add_edge(int x,int y){
to[++e]=y;
Next[e]=Begin[x];
Begin[x]=e;
}
inline int ksm(int x,int y){
int res=1;
while(y){
if(y&1) res=(ll)res*x%mod;
y>>=1;
x=(ll)x*x%mod;
}
return res;
}
inline void add(){
REP(i,0,tot) if(a[i/64]&(1ll<<(ll)(i%64))){
if(p[i]){
REP(j,0,tmp) a[j]^=bit[i][j];
}
else{
REP(j,0,tmp) bit[i][j]=a[j];
// cerr<<i<<' '<<All<<endl;
p[i]=1;
--ans;
--All;
break;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
init(maxm-10);
int T=read();
while(T--){
int L=read(),R=read();
int t1=upper_bound(prime+1,prime+cnt+1,R/L)-prime;
int t2;
for(t2=0;prime[t2+1]*prime[t2+1]<=R;++t2);
int t3=upper_bound(prime+1,prime+cnt+1,R)-prime-1;
REP(i,L,R) Begin[i]=0;
e=0;
ans=(R-L+1);
ans-=t1-1;
// cerr<<t1<<' '<<t2<<' '<<t3<<endl;
REP(i,t1,t2) REP(j,(L-1)/prime[i]+1,R/prime[i]){
int u=j,x=1;
while(u%prime[i]==0) u/=prime[i],x^=1;
if(x) add_edge(prime[i]*j,i-t1);
}
tmp=(t2-t1)/64;
tot=t2-t1;
REP(i,0,tot){
REP(j,0,tmp) bit[i][j]=0;
p[i]=0;
}
All=tot;
REP(i,max(t2+1,t1),t3){
int l=(L-1)/prime[i]+1,r=R/prime[i];
if(l>r) continue;
ans--;
if(All<0) continue;
if(l==r) continue;
REP(j,0,tmp) num[j]=0;
for(int j=Begin[l*prime[i]];j;j=Next[j]) num[to[j]/64]^=(1ll<<(ll)(to[j]%64));
REP(j,l+1,r){
REP(k,0,tmp) a[k]=num[k];
for(int k=Begin[j*prime[i]];k;k=Next[k]) a[to[k]/64]^=(1ll<<(ll)(to[k]%64));
add();
if(All<0) break;
}
}
REP(i,L,R) if(Max[i]<=t2){
if(All<0) break;
REP(j,0,tmp) a[j]=0;
for(int j=Begin[i];j;j=Next[j]) a[to[j]/64]^=(1ll<<(ll)(to[j]%64));
add();
}
printf("%d\n",ksm(2,ans));
}
return 0;
}
正解好迷啊，有个结论，当\(R-L \ge 6000\)时只要区间内出现了这个质因子就一定有基。大于\(6000\)的直接判，剩下的暴力高斯消元。
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') f=-1,c=getchar();
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') f=-1,c=getchar();
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxm=1e7+10,maxn=1000+10,mod=998244353;
int prime[maxm],isprime[maxm],Max[maxm],cnt;
inline void init(int n){
REP(i,2,n){
if(!isprime[i]) prime[++cnt]=i,Max[i]=cnt;
REP(j,1,cnt){
int u=i*prime[j];
if(u>n) break;
isprime[u]=1;
Max[u]=max(Max[i],j);
if(i%prime[j]==0) break;
}
}
}
ll bit[maxn][maxn],a[maxn],num[maxn];
int tmp,tot,All;
bool p[maxn];
int ans,Begin[maxm],to[maxm*10],Next[maxm*10],e;
inline void add_edge(int x,int y){
to[++e]=y;
Next[e]=Begin[x];
Begin[x]=e;
}
inline int ksm(int x,int y){
int res=1;
while(y){
if(y&1) res=(ll)res*x%mod;
y>>=1;
x=(ll)x*x%mod;
}
return res;
}
inline void add(){
REP(i,0,tot) if(a[i/64]&(1ll<<(ll)(i%64))){
if(p[i]){
REP(j,0,tmp) a[j]^=bit[i][j];
}
else{
REP(j,0,tmp) bit[i][j]=a[j];
// cerr<<i<<' '<<All<<endl;
p[i]=1;
--ans;
--All;
break;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
init(maxm-10);
int T=read();
while(T--){
int L=read(),R=read();
int t1=upper_bound(prime+1,prime+cnt+1,R/L)-prime;
int t2;
for(t2=0;prime[t2+1]*prime[t2+1]<=R;++t2);
int t3=upper_bound(prime+1,prime+cnt+1,R)-prime-1;
REP(i,L,R) Begin[i]=0;
e=0;
ans=(R-L+1);
ans-=t1-1;
if(R-L>=6000){
REP(i,t1,t3) if(R/prime[i]>(L-1)/prime[i]) --ans;
printf("%d\n",ksm(2,ans));
continue;
}
// cerr<<t1<<' '<<t2<<' '<<t3<<endl;
REP(i,t1,t2) REP(j,(L-1)/prime[i]+1,R/prime[i]){
int u=j,x=1;
while(u%prime[i]==0) u/=prime[i],x^=1;
if(x) add_edge(prime[i]*j,i-t1);
}
tmp=(t2-t1)/64;
tot=t2-t1;
REP(i,0,tot){
REP(j,0,tmp) bit[i][j]=0;
p[i]=0;
}
All=tot;
REP(i,max(t2+1,t1),t3){
int l=(L-1)/prime[i]+1,r=R/prime[i];
if(l>r) continue;
ans--;
if(All<0) continue;
if(l==r) continue;
REP(j,0,tmp) num[j]=0;
for(int j=Begin[l*prime[i]];j;j=Next[j]) num[to[j]/64]^=(1ll<<(ll)(to[j]%64));
REP(j,l+1,r){
REP(k,0,tmp) a[k]=num[k];
for(int k=Begin[j*prime[i]];k;k=Next[k]) a[to[k]/64]^=(1ll<<(ll)(to[k]%64));
add();
if(All<0) break;
}
}
REP(i,L,R) if(Max[i]<=t2){
if(All<0) break;
REP(j,0,tmp) a[j]=0;
for(int j=Begin[i];j;j=Next[j]) a[to[j]/64]^=(1ll<<(ll)(to[j]%64));
add();
}
printf("%d\n",ksm(2,ans));
}
return 0;
}
座位
题目描述
有 \(n\) 张圆桌排成一排（从左到右依次编号为 $ 0 $ 到 $ n−1 $ ），每张桌子有 $ m $ 个座位（按照逆时针依次编号为$ 0$ 到 \(m−1\) ），在吃饭时每个座位上都有一个人；在吃完饭后的时候，每个人都需要选择一个新的座位（新座位可能和原来的座位是同一个），具体来说，第 $ i $ 桌第 $ j $ 个人的新座位只能在第 $ L_{i,j} $ 桌到第 $ R_{i,j} $ 桌中选，可以是这些桌中的任何一个座位。确定好新座位之后，大家开始移动，移动的体力消耗按照如下规则计算：
移动座位过程分为两步：
- 从起始桌移动到目标桌对应座位，这个过程中的体力消耗为两桌距离的两倍，即从第 $ i $ 桌移动到第 $ j $ 桌对应座位的体力消耗为$ 2\times |i−j|$；
2.从目标桌的对应座位绕着桌子移动到目标座位，由于桌子是圆的，所以客人会选择最近的方向移动，体力消耗为移动距离的一倍，即从编号为 $ x $ 的座位移动的编号为 $ y$ 的座位的体力消耗为 $ min(|x−y|,m−|x−y|)$；
详情如下图：
现在，给定每个客人的限制（即每个人的新座位所在的区间），需要你设计一个方案，使得所有客人消耗的体力和最小；本题中假设客人在移动的时候互不影响。
输入格式
从标准输入读入数据。
第一行输入两个数 $ n $和 $ m$ ；
接下来输入 $ n$ 行，每行 $ m $ 个空格隔开的整数描述矩阵 $ L$ ：其中，第 $ i $ 行的第 $ j $ 个数表示 $ L_{i,j}$；
接下来输入 $ n$ 行，每行 $ m $ 个空格隔开的整数描述矩阵 $ R$ ：其中，第 $ i $ 行的第 $ j $ 个数表示 $ R_{i,j}$。
数据是随机生成的
输出格式
输出到标准输出。
输出总体力消耗的最小值，如果没有合法的方案输出no solution。
数据范围
$1≤n≤300 , 1≤m≤10 , 0≤L_{i,j}≤R_{i,j}≤n−1 $
题解
这道题应该是这一场里最简单的题，很容易想到费用流，每个桌子里的相邻两个座位连边，桌子之间的连边的话就线段树优化建边即可，注意对于向左和向右要开两个线段树。
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') f=-1,c=getchar();
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') f=-1,c=getchar();
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int inf=0x3f3f3f3f,maxn=1e5+10,maxm=1e6+10;
int ans,Flow,n,S,T;
struct Min_cost_Max_Flow{
int vis[maxn],cur[maxn],Begin[maxn],Next[maxm],to[maxm],w[maxm],e,d[maxn],v[maxm];
inline void add_edge(int x,int y,int f,int z){
to[++e]=y;
Next[e]=Begin[x];
Begin[x]=e;
w[e]=f;
v[e]=z;
}
inline void add(int x,int y,int f,int z){
// cout<<x<<' '<<y<<' '<<f<<' '<<z<<endl;
add_edge(x,y,f,z),add_edge(y,x,0,-z);
}
inline bool spfa(){
deque<int> q;
REP(i,1,n) d[i]=inf;
d[T]=0;q.push_back(T);
while(!q.empty()){
int u=q.front();q.pop_front();
for(int i=Begin[u];i;i=Next[i])
if(w[i^1]>0 && chkmin(d[to[i]],d[u]+v[i^1]))
if(!vis[to[i]]){
vis[to[i]]=1;
if(!q.empty() && d[q.front()]>d[to[i]]) q.push_front(to[i]);
else q.push_back(to[i]);
}
vis[u]=0;
}
return d[S]<inf;
}
int dfs(int x,int Min){
if(!Min || x==T) return Min;
int num,flow=0;
vis[x]=1;
for(int &i=cur[x];i;i=Next[i])
if(!vis[to[i]] && w[i]>0 && d[to[i]]+v[i]==d[x] && (num=dfs(to[i],min(Min,w[i])))){
ans+=num*v[i];
w[i]-=num,w[i^1]+=num;
flow+=num,Min-=num;
if(!Min) break;
}
vis[x]=0;
return flow;
}
inline void work(){
while(spfa()){
REP(i,1,n) cur[i]=Begin[i];
Flow+=dfs(S,inf);
}
}
}MCMF;
int num[1010][11],Nw;
struct Segment_tree{
int id[4010];
void build_tree(int x,int L,int R,int ty){
id[x]=++n;
if(L==R){
MCMF.add(n,num[L][Nw],inf,0);
return;
}
int Mid=(L+R)>>1;
build_tree(x<<1,L,Mid,ty),build_tree(x<<1|1,Mid+1,R,ty);
if(ty) MCMF.add(id[x],id[x<<1],inf,2*(R-Mid)),MCMF.add(id[x],id[x<<1|1],inf,0);
else MCMF.add(id[x],id[x<<1],inf,0),MCMF.add(id[x],id[x<<1|1],inf,2*(Mid-L+1));
}
void query(int x,int L,int R,int ql,int qr,int ty,int fr){
if(ql<=L && R<=qr){
if(ty) MCMF.add(fr,id[x],1,2*(Nw-R));
else MCMF.add(fr,id[x],1,2*(L-Nw));
return;
}
int Mid=(L+R)>>1;
if(ql<=Mid) query(x<<1,L,Mid,ql,qr,ty,fr);
if(qr>Mid) query(x<<1|1,Mid+1,R,ql,qr,ty,fr);
}
}Seg0[11],Seg1[11];
int L[1010][11],R[1010][11];
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int N=read(),M=read();
S=++n,T=++n;
MCMF.e=1;
REP(i,1,N) REP(j,1,M) num[i][j]=++n,MCMF.add(n,T,1,0);
REP(i,1,M) Nw=i,Seg0[i].build_tree(1,1,N,0),Seg1[i].build_tree(1,1,N,1);
if(M>1) REP(i,1,N){
REP(j,1,M-1) MCMF.add(num[i][j],num[i][j+1],inf,1),MCMF.add(num[i][j+1],num[i][j],inf,1);
MCMF.add(num[i][1],num[i][M],inf,1),MCMF.add(num[i][M],num[i][1],inf,1);
}
REP(i,1,N) REP(j,1,M) L[i][j]=read()+1;
REP(i,1,N) REP(j,1,M) R[i][j]=read()+1;
REP(i,1,N) REP(j,1,M){
++n;
MCMF.add(S,n,1,0);
Nw=i;
if(R[i][j]<=i) Seg1[j].query(1,1,N,L[i][j],R[i][j],1,n);
else if(L[i][j]>=i) Seg0[j].query(1,1,N,L[i][j],R[i][j],0,n);
else{
Seg1[j].query(1,1,N,L[i][j],i,1,n);
Seg0[j].query(1,1,N,i+1,R[i][j],0,n);
}
}
MCMF.work();
if(Flow!=N*M) printf("no solution\n");
else printf("%d\n",ans);
return 0;
}