Educational Codeforces Round 169 (Rated for Div. 2) D. Colored Portals
D. Colored Portals
time limit per test: 2 seconds
memory limit per test: 256 megabytes
There are n cities located on a straight line. The cities are numbered from 1 to n.
Portals are used to move between cities. There are 4 colors of portals: blue, green, red, and yellow. Each city has portals of two different colors. You can move from city i to city j if they have portals of the same color (for example, you can move between a "blue-red" city and a "blue-green" city). This movement costs |i−j| coins.
Your task is to answer q independent queries: calculate the minimum cost to move from city x to city y.
Input
The first line contains a single integer t (1≤t≤10^4) — the number of test cases.
The first line of each test case contains two integers n and q (1≤n,q≤2⋅10^5) — the number of cities and the number of queries, respectively.
The second line contains n strings of the following types: BG, BR, BY, GR, GY, or RY; the i-th of them describes the portals located in the i-th city; the symbol B indicates that there is a blue portal in the city, G — green, R — red, and Y — yellow.
The j-th of the next q lines contains two integers xj and yj (1≤xj,yj≤n) — the description of the j-th query.
Additional constraints on the input:
the sum of n over all test cases does not exceed 2⋅10^5;
the sum of q over all test cases does not exceed 2⋅10^5.
Output
For each query, print a single integer — the minimum cost to move from city x to city y (or −1 if it is impossible).
Example
Input
2
4 5
BR BR GY GR
1 2
3 1
4 4
1 4
4 2
2 1
BG RY
1 2
Output
1
4
0
3
2
-1
【思路分析】
二分+模拟。目标点和当前点如果没有相同的颜色,则二分其余4种颜色组合。如果二分结果的编号在目标点和当前点区间以内,则直接输出|y-x|,否则要贪心地取最靠近该区间的编号。
#include<bits/stdc++.h>
#define i64 long long
using namespace std;
void solve() {
i64 n, q;
cin >> n >> q;
vector<i64> v[6];
string arr[n + 1];
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
if (arr[i] == "BG") v[0].emplace_back(i);
else if (arr[i] == "BR") v[1].emplace_back(i);
else if (arr[i] == "BY") v[2].emplace_back(i);
else if (arr[i] == "GR") v[3].emplace_back(i);
else if (arr[i] == "GY") v[4].emplace_back(i);
else if (arr[i] == "RY") v[5].emplace_back(i);
}
for (int i = 0; i < 6; ++i) {
sort(v[i].begin(), v[i].end());
}
for (int i = 0; i < q; ++i) {
i64 x, y;
cin >> x >> y;
if (x > y) swap(x, y);
bool flag = false;
for (const auto &item: arr[x]) {
if (arr[y].find(item) != string::npos) {
cout << y - x << endl;
flag = true;
break;
}
}
if (flag) continue;
i64 minr = LLONG_MAX / 2, maxl = LLONG_MIN / 2;
if (arr[x] == "BG" || arr[x] == "RY") {
for (int j = 1; j <= 4; ++j) {
auto res = lower_bound(v[j].begin(), v[j].end(), x);
if (res == v[j].end()) continue;
minr = min(*res, minr);
}
for (int j = 1; j <= 4; ++j) {
auto res = lower_bound(v[j].begin(), v[j].end(), x);
if (res == v[j].begin() || v[j].empty()) continue;
maxl = max(maxl, *(res-1));
}
} else if (arr[x] == "BR" || arr[x] == "GY") {
for (int j = 0; j <= 5; ++j) {
if (j == 1 || j == 4) continue;
auto res = lower_bound(v[j].begin(), v[j].end(), x);
if (res == v[j].end()) continue;
minr = min(*res, minr);
}
for (int j = 0; j <= 5; ++j) {
if (j == 1 || j == 4) continue;
auto res = lower_bound(v[j].begin(), v[j].end(), x);
if (res == v[j].begin() || v[j].empty()) continue;
maxl = max(maxl, *(res-1));
}
} else if (arr[x] == "BY" || arr[x] == "GR") {
for (int j = 0; j <= 5; ++j) {
if (j == 2 || j == 3) continue;
auto res = lower_bound(v[j].begin(), v[j].end(), x);
if (res == v[j].end()) continue;
minr = min(*res, minr);
}
for (int j = 0; j <= 5; ++j) {
if (j == 2 || j == 3) continue;
auto res = lower_bound(v[j].begin(), v[j].end(), x);
if (res == v[j].begin() || v[j].empty()) continue;
maxl = max(maxl, *(res-1));
}
}
if (minr >= x && minr <= y) {
cout << y - x << endl;
continue;
}
if (minr == LLONG_MAX / 2 && maxl == LLONG_MIN / 2) {
cout << -1 << endl;
continue;
}
i64 e = min(x - maxl, minr - y);
cout << y - x + 2 * e << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
原文地址:https://blog.csdn.net/qq_36789020/article/details/142683041
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!