CF 2004 D. Colored Portals （*1600）二分

showball / 2024-09-02 / 原文

CF 2004 D. Colored Portals （*1600）二分

题目链接

题意：

有 $n$ 座城市，编号从 $1$ 到 $n$ 。传送门一共有 $4$ 种颜色，每个城市有两种不同颜色的传送门。若城市 $i$ 和城市 $j$ 有相同颜色的传送门。那么就可以花费 $|i-j|$ 枚金币从城市 $i$ 到城市 $j$ 。

$q$ 次询问，计算从 $x$ 到 $y$ 的最小花费。

思路：

如果 $x$ 和 $y$ 有相容颜色的传送门，那么直接一步到达即可。否则，我们一定只需要到达一个中间点，然后再到达 $y$ 即可。其他多走不会使结果更优。接下来考虑中间点如何选取。

那么只需要找到离 $x$ 最近的即可。本题思维很简单，难点在于实现上，这里参考 cuppyy 大佬的写法，采用 $2$ 进制表示状态，让代码清晰很多。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

void Showball(){
   int n,q;
   cin>>n>>q;

   auto get=[&](char c){
     if(c=='B') return 0;
     if(c=='G') return 1;
     if(c=='R') return 2;
     if(c=='Y') return 3;
     return -1;
   };

   vector<int> st(n);
   vector<int> pos[16];
   vector<int> cand;
   for(int i=0;i<16;i++){
    if(__builtin_popcount(i)==2) cand.pb(i);
   }

   for(int i=0;i<n;i++){
      string s;
      cin>>s;
      for(auto c:s) st[i]|=1<<get(c);
      pos[st[i]].pb(i);
   }

   while(q--){
    int x,y;
    cin>>x>>y;
    if(x>y) swap(x,y);
    x--,y--;
    if(st[x]&st[y]) cout<<abs(x-y)<<endl;
    else{
      int ans=inf;
      for(auto u:cand){
        if((u&st[x])&&(u&st[y])){
          auto it=lower_bound(all(pos[u]),x);
          if(it!=pos[u].end()){
            ans=min(ans,abs(x-*it)+abs(y-*it));
          }
          if(it!=pos[u].begin()){
            it--;
            ans=min(ans,abs(x-*it)+abs(y-*it));
          }
        }
      }
      if(ans==inf) ans=-1;
      cout<<ans<<endl;
    }
   }

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}