自动搬运

查看原文

来自洛谷，原作者为

	XZhuRen 骄子风采，青春闪耀

搬运于2025-08-24 23:11:36，当前版本为作者最后更新于2025-03-26 20:53:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

图床挂了，重传。

这场的简单题……你谷评紫真就全员小学生？

考虑不操作，就是求网格图最短路。

断边，做两遍最短路。

操作情况下，即正反求一遍，发现最短路形如暴力把网格断开处 $\text{L}$ 形状的断边求一遍。

这里手动分讨一下就可以 $\mathcal{O}(nq)$，拿到 $70 \text{pts}$ 了。

注意到转移是后缀形式，两个后缀最小就好。

场上是可以新开数组的，洛谷这里卡了一下，直接把 $ea,eb$ 覆盖就好。

远古代码，码风较为“优美”。

#include <bits/stdc++.h>
using namespace std;
const int N=5005,Q=100005;
typedef long long ll1;
ll1 n,q,B;
ll1 f[N][N],f1[N][N],ans;
ll1 ea[N][N],eb[N][N];
// ll1 sufmn1[N][N],sufmn2[N][N];
unsigned long long seed;
void xorshift64() {
	seed ^= seed << 13;
	seed ^= seed >> 7;
	seed ^= seed << 17;
}
const ll1 inf=1e16+8;
void init(){
	f[1][1]=0;
	f1[n][n]=0;
	for(int i=2;i<=n;i++)f[1][i]=f[1][i-1]+ea[1][i-1];
	for(int j=2;j<=n;j++)f[j][1]=f[j-1][1]+eb[j-1][1];
	for(int i=n-1;i>=1;i--)f1[n][i]=f1[n][i+1]+ea[n][i];
	for(int j=n-1;j>=1;j--)f1[j][n]=f1[j+1][n]+eb[j][n];
	for(int i=2;i<=n;i++)for(int j=2;j<=n;j++)f[i][j]=min(f[i][j-1]+ea[i][j-1],f[i-1][j]+eb[i-1][j]);
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=n+1;j++){
			if(i<1||j<1||j>=n||i>n)ea[i][j]=inf;
			if(i<1||j<1||j>n||i>=n)eb[i][j]=inf;
		}
	for(int i=n-1;i>=1;i--)for(int j=n-1;j>=1;j--)f1[i][j]=min(f1[i][j+1]+ea[i][j],f1[i+1][j]+eb[i][j]);
	for(int j=1;j<=n;j++)
	for(int i=n;i>=1;i--)
	ea[i][j]=min(ea[i+1][j],f[i][j]+f1[i][j+1]+ea[i][j]);
	for(int i=1;i<=n;i++)
	for(int j=n;j>=1;j--)
	eb[i][j]=min(eb[i][j+1],f[i][j]+f1[i+1][j]+eb[i][j]);
}
int main(){
	// freopen("1.in","r",stdin);
	scanf("%lld%lld",&n,&q);
	scanf("%llu%llu",&seed,&B);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j != n; j++) {
			xorshift64();
			ea[i][j] = seed & ((1 << B) - 1);
		}
	}
	for(int i = 1; i != n; i++) {
		for(int j = 1; j <= n; j++) {
			xorshift64();
			eb[i][j] = seed & ((1 << B) - 1);
		}
	}
	int i,j,qx1,qy1,qx2,qy2;
	init();
	while(q--){
		scanf("%d%d%d%d",&qx1,&qy1,&qx2,&qy2);
		ans=inf;
		if(qx1==qx2){
			j=qy1;
			ans=min(ans,ea[qx1+1][j]);
			i=qx1-1;
			ans=min(ans,eb[i][qy1+1]);
		}else{
			j=qy1-1;
			ans=min(ans,ea[qx1+1][j]);
			i=qx1;
			ans=min(ans,eb[i][qy1+1]);
		}
		printf("%lld\n",ans);
	}
}