验题人题解 | 花火大会

这是一种与出题人不同的做法。

如果一个烟花爆炸后每秒可以散开 $1$ 格，那么在 $i$ 秒到达的格子都有 $i$ 格距离。这个距离是曼哈顿距离。

也就是说，一个烟花会在爆炸后第 $x$ 秒到达所有曼哈顿距离为 $x$ 的格子。

那么，考虑到这个烟花的爆炸时间 $z_i$，也就是第 $z_i+x$ 秒到达所有曼哈顿距离为 $x$ 的点。

设烟花位置在 $(x,y)$，当前点在 $(i,j)$，那么 $(i,j)$ 会在 $(z_i+|x-i|+|y-j|)$ 时刻看到烟花。

也就是对于格子 $(i,j)$，第一次看到烟花的时刻即为【原谅我使用了很撇脚的 $o$ 作为下标，因为 $i,j,k$ 都用掉了】

$$\min^k_{o=1}(z_o+|x_o-i|+|y_o-j|)$$

绝对值并不优雅，考虑拆绝对值。

<img src="https://cdn.luogu.com.cn/upload/image_hosting/p5opeapq.png" style="zoom:50%;" />

我们如果能快速计算四种情况分别最优的点当作这种情况的代表，就可以只比较这四个点的优劣。

• 情况一

  此时 $x\le i,y\le j$，上式的值为 $z+i-x+j-y$。

  在这种情况内部，$i+j$ 的值恒定，我们需要 $z-x-y$ 最小的点。

• 情况二

  此时 $x\ge i,y\le j$，上式的值为 $z+x-i+j-y$。

  在这种情况内部，$-i+j$ 的值恒定，我们需要 $z+x-y$ 最小的点。

• 情况三

  此时 $x\le i,y\ge j$，上式的值为 $z+i-x+y-j$。

  在这种情况内部，$i-j$ 的值恒定，我们需要 $z-x+y$ 最小的点。

• 情况四

  此时 $x\ge i,y\ge j$，上式的值为 $z+x-i+y-j$。

  在这种情况内部，$-i-j$ 的值恒定，我们需要 $z+x+y$ 最小的点。

我们可以通过二维前缀最值的方式预处理出各种情况下最小的点，然后比较这四个点的优劣即可。

相比于正解，这个做法不依赖 $k$ 的大小，时间复杂度为 $O(nm)$。空间复杂度也是 $O(nm)$，但带有的五倍常数较大，感谢出题人不杀之恩。

这道题可能讲的有点玄乎，没看懂可以看代码或者群里找我。

void solve(){
	cin>>n>>m>>k;
	for(ll i=1;i<=k;i++){
		cin>>x[i]>>y[i]>>z[i];
		f[x[i]][y[i]]=z[i];
	}
	for(ll i=0;i<=n+1;i++) for(ll j=0;j<=m+1;j++){
		g1[i][j]=g2[i][j]=g3[i][j]=g4[i][j]=1e18;
	}
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++){
			if(f[i][j]) g1[i][j]=f[i][j]-i-j;
			g1[i][j]=min(g1[i][j],min(g1[i-1][j],g1[i][j-1]));
		}
	for(ll i=n;i>=1;i--)
		for(ll j=1;j<=m;j++){
			if(f[i][j]) g2[i][j]=f[i][j]+i-j;
			g2[i][j]=min(g2[i][j],min(g2[i+1][j],g2[i][j-1]));
		}
	for(ll i=1;i<=n;i++)
		for(ll j=m;j>=1;j--){
			if(f[i][j]) g3[i][j]=f[i][j]-i+j;
			g3[i][j]=min(g3[i][j],min(g3[i][j+1],g3[i-1][j]));
		}
	for(ll i=n;i>=1;i--)
		for(ll j=m;j>=1;j--){
			if(f[i][j]) g4[i][j]=f[i][j]+i+j;
			g4[i][j]=min(g4[i][j],min(g4[i][j+1],g4[i+1][j]));
		}
	ll now=1;
	ll ans=0;
	for(ll i=0;i<=n;i++){
		for(ll j=1;j<=m;j++){
			now*=233ll; now%=mod;
			if(!i) continue;
			ll res=min(g1[i][j]+i+j,min(g2[i][j]-i+j,min(g3[i][j]+i-j,g4[i][j]-i-j)));
			ans+=res*now%mod;
			ans%=mod;
		}
	}
	cout<<ans<<endl;
}