AT_agc061_d [AGC061D] Almost Multiplication Table。

大体思路：二分答案然后构造可行解。

利用一个思想就是题目如果有两个变量令一个大于另一个，可以进行分类讨论。

我们先进行二分答案，判断这个 midmid 能不能被构造。我们计算每一个 ai,ja_{i,j} 可以的范围 li,j→ri,jl_{i,j}\to r_{i,j}。

观察到 nn 和 mm 很小，所以我们尝试循环构造，进行调整。

我们先假设 xn≤ymx_n\le y_m（分情况讨论，之后再反过来），这样能保证小的那一个在根号级别。

  • 从前往后调整 xix_i，如果比 ≤xi−1\le x_{i-1} 就变成 xi−1+1x_{i-1}+1，然后和每一个 ⌈li,jyj⌉\lceil \frac{l_{i,j}}{y_j} \rceil 取 max⁡\max。

  • 从后往前调整 yiy_i，如果比 ≥yi+1\ge y_{i+1} 就变成 yi+1−1y_{i+1}-1，然后和每一个 ⌈ri,jxj⌉\lceil \frac{r_{i,j}}{x_j} \rceil 取 min⁡\min。

合法或无解就可以结束了。怎么证明时间复杂度正确性？

设 C=+∞C=+\infty，首先 xi≤Cx_i\le \sqrt{C}，所以 xix_i 增加的次数 ≤C\le \sqrt{C}，yy 减少的次数 ≤C\le \sqrt{C}。所以时间复杂度就是正确的了。

代码中由于 nn 和 mm 不同，所以需要交换 xx 和 yy 再做一次。

注意细节，特别是复制代码的时候忘改的地方。

代码
C++
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int a[11][11],L[11][11],R[11][11],x[11],y[11];
bool ck(){
	for(int i=2;i<=n;i++)if(x[i]<=x[i-1])return 0;
	for(int i=2;i<=m;i++)if(y[i]<=y[i-1])return 0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		if(x[i]*y[j]>R[i][j]||x[i]*y[j]<L[i][j])return 0;
	}
	return 1;
}
bool check(int mid){
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
		L[i][j]=a[i][j]-mid,R[i][j]=a[i][j]+mid;
	}
	
	y[m+1]=2e9+1;
	for(int i=1;i<=n;i++)x[i]=1;
	for(int i=1;i<=m;i++)y[i]=2e9;
	while(1){
		for(int i=1;i<=n;i++){
			x[i]=max(x[i],x[i-1]+1);
			for(int j=1;j<=m;j++)x[i]=max(x[i],(int)ceil(1.0*L[i][j]/y[j]));
//			for(int j=1;j<=m;j++)x[i]=max(x[i],((L[i][j]+y[j]-1)/y[j]));
		}
		for(int i=m;i>=1;i--){
			y[i]=min(y[i],y[i+1]-1);
			for(int j=1;j<=n;j++)y[i]=min(y[i],R[j][i]/x[j]);
		}
//		cout<<x[n]<<' '<<y[m]<<endl;
		if(x[n]>y[m]||y[1]<=0)break;
		if(ck())return 1;
	}
	
	x[n+1]=2e9+1;
	for(int i=1;i<=n;i++)x[i]=2e9;
	for(int i=1;i<=m;i++)y[i]=1;
	while(1){
		for(int i=1;i<=m;i++){
			y[i]=max(y[i],y[i-1]+1);
			for(int j=1;j<=n;j++)y[i]=max(y[i],(int)ceil(1.0*L[j][i]/x[j]));
//			for(int j=1;j<=n;j++)y[i]=max(y[i],((L[j][i]+x[j]-1)/x[j]));
		}
		for(int i=n;i>=1;i--){
			x[i]=min(x[i],x[i+1]-1);
			for(int j=1;j<=m;j++)x[i]=min(x[i],R[i][j]/y[j]);
		}
		if(x[n]<y[m]||x[1]<=0)break;
		if(ck())return 1;
	}
	return 0;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	int l=0,r=1e9;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	check(l);
	cout<<l<<endl;
	for(int i=1;i<=n;i++)cout<<x[i]<<' ';
	cout<<endl;
	for(int i=1;i<=m;i++)cout<<y[i]<<' ';
	cout<<endl;
	return 0;
}