题解：P15674 [ICPC 2024 Jakarta R] X Aura

· · 题解

当 X 为 1 时，答案显然为 H_{R_s,C_s}-H_{R_f,C_f}。所以接下来讨论 X>1 的情况。

如果图中存在一个环，沿着环走一圈后惩罚值变了，那么所有询问都是 INVAILD 的。如果惩罚值变大了，那么倒着走就变小了。

直接去找满足条件的环比较难，发现一个大环可以由多个 2\times 2 的小环拼成。

例如走 (1,1)\rightarrow(2,1)\rightarrow(3,1)\rightarrow(3,2)\rightarrow(2,2)\rightarrow(1,2)\rightarrow(1,1) 相当于走了 (1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(1,2)\rightarrow(1,1) 和 (2,1)\rightarrow(3,1)\rightarrow(3,2)\rightarrow(2,2)\rightarrow(2,1)。两个小环多出来的路径惩罚值相加为 0。

所以只需要判断每个小环走一圈后惩罚值有没有变化即可，如果都没有就说明答案是两点到 (1,1) 的距离相减，因为这两点间的任意一条路径惩罚值都相同，否则沿不同惩罚值的两条路径走一个环惩罚值就会变化，矛盾。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,q,fl,dis[1145][1145];
char mp[1145][1145];
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
signed main(){
    n=read();m=read();x=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>mp[i][j];
    for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)if(pow(mp[i][j]-mp[i-1][j],x)+pow(mp[i-1][j]-mp[i-1][j-1],x)+pow(mp[i-1][j-1]-mp[i][j-1],x)+pow(mp[i][j-1]-mp[i][j],x))fl=1;
    if(!fl)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis[i][j]=(i>1?dis[i-1][j]+pow(mp[i-1][j]-mp[i][j],x):dis[i][j-1]+pow(mp[i][j-1]-mp[i][j],x));
    q=read();
    for(int o1,o2,o3,o4;q;q--){
        o1=read();o2=read();o3=read();o4=read();
        if(fl)cout<<"INVALID\n";
        else cout<<dis[o3][o4]-dis[o1][o2]<<'\n';
    }
    return 0;
}
/*
*/