比太郎所在的魔法学校即将举办运动会。运动会中有一个项目，称为“魔法阵”。
有 \(N\) 个魔法阵依次排列在一个圆上，顺时针编号为 \(1\) 到 \(N\)。每个魔法阵为红色或蓝色中的一种，使用长度为 \(N\) 且仅包含小写字母 b 和 r 字符串 \(S\) 表示：\(S_j(1\le j\le N)\) 为 r 则表示魔法阵 \(j\) 为红色，否则为蓝色。
比太郎可以通过如下的两种方式在魔法阵中传送：
目前他仅得知每个魔法阵的颜色，但并不知道运动会当天具体的传送计划。于是他决定考虑 \(Q\) 个传送计划：在第 \(i\) 个计划中，他要从魔法阵 \(X_i\) 开始，花费最少的时间传送到魔法阵 \(Y_i\)。
请你对于每一个传送计划，求出最少需要花费的时间。
第一行输入两个整数 \(N,Q\)。
第二行输入一个字符串 \(S\)。
接下来 \(Q\) 行，每行输入两个整数 \(X_i,Y_i\)。
输出 \(Q\) 行，在第 \(i\) 行输出一个整数，表示第 \(i\) 个传送计划最少需要花费的传送时间（单位：秒）。
5 2
rbrbb
5 3
4 5
2
1
4 3
brrr
2 4
1 3
3 1
1
2
2
6 3
brbrbr
1 2
2 5
2 4
1
2
1
6 5
bbbrrr
2 3
2 4
2 5
2 6
2 1
1
2
3
2
1
在此样例中，魔法阵的颜色分别为红色、蓝色、红色、蓝色、蓝色。
对于第一组计划（\(5\to 3\)），比太郎可以使用如下传送方案：
最少需要花费的时间为 \(2\) 秒。可以证明不可能在小于 \(2\) 秒的时间内从魔法阵 \(5\) 传送到魔法阵 \(3\)。
对于第二组计划（\(4\to 5\)），比太郎可以使用如下传送方案：
最少需要花费的时间为 \(1\) 秒。
该样例满足子任务 \(5,6\) 的限制。
该样例满足子任务 \(2,5,6\) 的限制。
该样例满足子任务 \(3,5,6\) 的限制。
该样例满足子任务 \(4,5,6\) 的限制。
b 和 r 的长度为 \(N\) 的字符串；b，\(S\) 的其他字符均为 r；b，偶数位置的字符为 r；b，后 \(\frac{N}{2}\) 个字符为 r；给出一个含有 N 个点的圆，每个点为红色或蓝色，使用相邻传送和同色传送，求出从点 x 至点 y 的最少传送次数。
- \(X_i\ne Y_i(1\le i\le Q)\)。
至少也要传送一次
所以有两种情况：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,q,i,x,y,s,b,sum;
string a;
cin>>n>>q;
cin>>a;
a=" "+a;
for(;q>0;q--){
cin>>x>>y;
if(a[x]==a[y]||abs(x-y)==1||abs(x-y)==n-1){
cout<<1<<'\n';
continue;
}
s=y-1,b=y+1;
if(s<1)
s=n;///////注意魔法阵依次排列在一个圆上，首尾相连，要注意边界
if(b>n)
b=1;
if(a[s]==a[x]||a[b]==a[x]){
cout<<2<<'\n';
continue;
}
s=x-1,b=x+1;
if(s<1)
s=n;
if(b>n)
b=1;
if(a[s]==a[y]||a[b]==a[y]){
cout<<2<<'\n';
continue;
}
cout<<3<<'\n';
}
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。