题解：P11952 [科大国创杯初中组 2023] 行走

· · 题解

图床挂了，重传。

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

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

断边，做两遍最短路。

操作情况下，即正反求一遍，发现最短路形如暴力把网格断开处 \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);
    }
}