题解：CF2004D Colored Portals

· · 题解

思路

我们研究颜色，发现最多只有四个不同的颜色，于是跳转时，我们的路程中只要有之前出现过的颜色（除入点），那么就可以省去入点，直接从之前出现过那个颜色的地方跳过来。于是我们得出了一个结论，路程中最多只会经过 4 个颜色。

考虑起始点 x 与终点 y，首先如果它们颜色有重合，那么一定可以直接跳，这样绝对是最短路。考虑它们颜色互不相同，如果想从 x 到 y 点，一定需要有一个点，既有 x 上的一个颜色，也有 y 上的一个颜色。所以考虑枚举 x 上的颜色与 y 上的颜色。这个点可以直接到 x 与 y，这样颜色的点可能有很多个对吧，所以考虑找出一个点两个颜色固定，使它到 x 的距离加上它到 y 的距离最小。

首先考虑它与 y 点在 x 的同一边，如果我们选 x 与 y 之间的点，那么再到 y 的距离都是一样的对吧，都是 x 到 y 的曼哈顿距离，考虑在 y 之后了，那么还要加上到 y 的两倍距离，这时离 y 最近的点就更优对吧（同时也最靠近 x，因为所选点在 y 之后，x 与 y 在选点的同一边）。

如果有 x 与 y 之间的点，那么一定选那些点，优于 y 之后的点。所以考虑选 y 那边的点，只需要选择离 x 近的即可。

考虑 y 对边的点，同样的，离 x 越远意味着离 y 越远（同上，所选点在 x 与 y 的同一边），所以考虑选离 x 最近的点。

所以最后选离 x 最近的与 y 同边与对边的点，即 x 点最近的左右边点，取路程最少的，预处理即可。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
string ver[]={"BG","BR","BY","GR","GY","RY"};
int las[N][6],nex[N][6],a[N],n,q;
string putin[N];
signed main() {
    int tt;cin>>tt;
    while(tt--) {
        cin>>n>>q;
        for(int i=1;i<=n;i++) {
            cin>>putin[i];
            a[i]=find(ver,ver+6,putin[i])-ver;
        }
        for(int i=0;i<=n;i++)
          for(int j=0;j<6;j++) las[i][j]=-0x3f3f3f3f3f3f3f3f;
        for(int i=1;i<=n;i++) {
            for(int j=0;j<6;j++) las[i][j]=las[i-1][j];
            las[i][a[i]]=i;
        }
        for(int i=1;i<=n+1;i++)
          for(int j=0;j<6;j++) nex[i][j]=0x3f3f3f3f3f3f3f3f;
        for(int i=n;i>=1;i--) {
            for(int j=0;j<6;j++) nex[i][j]=nex[i+1][j];
            nex[i][a[i]]=i;
        }
        while(q--) {
            int x,y;cin>>x>>y;
            bool flag=0;
            for(int i=0;i<2;i++)
                for(int j=0;j<2;j++)
                    if(putin[x][i]==putin[y][j]) {
                        flag=1;
                        goto ok;
                    }
            ok:
            if(flag) {
                cout<<abs(y-x)<<endl;
                continue;
            }
            int minn=1e9;
            for(int i=0;i<2;i++)
                for(int j=0;j<2;j++) {
                    char xx=putin[x][i],yy=putin[y][j];
                    if(xx>yy) swap(xx,yy);
                    string s;s+=xx;s+=yy;
                    int value=find(ver,ver+6,s)-ver;
                    minn=min(minn,abs(x-las[x][value])+abs(y-las[x][value]));
                    minn=min(minn,abs(x-nex[x][value])+abs(y-nex[x][value]));
                }
            cout<<(minn==(int)1000000000?-1:minn)<<endl;
        }
    }
    return 0;
}