P13735 [JOIGST 2025] 魔法阵 / Magic Circle 题解

目描述

比太郎所在的魔法学校即将举办运动会。运动会中有一个项目，称为“魔法阵”。

有 � 个魔法阵依次排列在一个圆上，顺时针编号为 1 到 �。每个魔法阵为红色或蓝色中的一种，使用长度为 � 且仅包含小写字母b和r字符串 � 表示：��(1≤�≤�) 为r则表示魔法阵 � 为红色，否则为蓝色。

比太郎可以通过如下的两种方式在魔法阵中传送：

• 选择一个相邻的魔法阵，花费 1 秒传送过去。换句话说，可以在魔法阵 �(1≤�≤�−1) 和 �+1 间传送（两个方向均可），也可以在魔法阵 1 和 � 间传送（两个方向均可）；
• 选择一个与当前所在魔法阵颜色相同的魔法阵（不一定要相邻），花费 1 秒传送过去。

目前他仅得知每个魔法阵的颜色，但并不知道运动会当天具体的传送计划。于是他决定考虑 � 个传送计划：在第 � 个计划中，他要从魔法阵 �� 开始，花费最少的时间传送到魔法阵 ��。

请你对于每一个传送计划，求出最少需要花费的时间。

输入格式

第一行输入两个整数 �,�。

第二行输入一个字符串 �。

接下来 � 行，每行输入两个整数 ��,��。

输出格式

输出 � 行，在第 � 行输出一个整数，表示第 � 个传送计划最少需要花费的传送时间（单位：秒）。

输入输出样例 #1

输入 #1

5 2 rbrbb 5 3 4 5

输出 #1

2 1

输入输出样例 #2

输入 #2

4 3 brrr 2 4 1 3 3 1

输出 #2

1 2 2

输入输出样例 #3

输入 #3

6 3 brbrbr 1 2 2 5 2 4

输出 #3

1 2 1

输入输出样例 #4

输入 #4

6 5 bbbrrr 2 3 2 4 2 5 2 6 2 1

输出 #4

1 2 3 2 1

说明/提示

【样例解释 #1】

在此样例中，魔法阵的颜色分别为红色、蓝色、红色、蓝色、蓝色。

对于第一组计划（5→3），比太郎可以使用如下传送方案：

1. 从魔法阵 5 传送到相邻的魔法阵 1，花费 1 秒；
2. 从魔法阵 1 传送到颜色相同的魔法阵 3，花费 1 秒。

最少需要花费的时间为 2 秒。可以证明不可能在小于 2 秒的时间内从魔法阵 5 传送到魔法阵 3。

对于第二组计划（4→5），比太郎可以使用如下传送方案：

1. 从魔法阵 4 传送到颜色相同的魔法阵 5，花费 1 秒。

最少需要花费的时间为 1 秒。

该样例满足子任务 5,6 的限制。

【样例解释 #2】

该样例满足子任务 2,5,6 的限制。

【样例解释 #3】

该样例满足子任务 3,5,6 的限制。

【样例解释 #4】

该样例满足子任务 4,5,6 的限制。

【数据范围】

• 3≤�≤5×105；
• 1≤�≤5×105；
• � 为仅包含小写字母b和r的长度为 � 的字符串；
• 1≤��,��≤�(1≤�≤�)；
• ��≠��(1≤�≤�)。

【子任务】

1. （6 分）�=3，�≤100；
2. （13 分）�1 为b，� 的其他字符均为r；
3. （18 分）� 为偶数，� 奇数位置的字符为b，偶数位置的字符为r；
4. （23 分）� 为偶数，� 的前 �2 个字符为b，后 �2 个字符为r；
5. （21 分）�,�≤100；
6. （19 分）无附加限制。

题解

题意

给出一个含有 N 个点的圆，每个点为红色或蓝色，使用相邻传送和同色传送，求出从点 x 至点 y 的最少传送次数。

思路

• ��≠��(1≤�≤�)。

至少也要传送一次
所以有两种情况：

1. 颜色相同 || 魔法阵��和魔法阵��相邻
   那么直接同色传送就行，输出1。
2. 颜色不同 && 魔法阵��和魔法阵��不相邻
   那么在圆上必定存在两种不同颜色相邻，可以从魔法阵��同色传送到其中一个，相邻传送到另一个，再同色传送到魔法阵��。所以最多3次。
   直接用if大法分类讨论一下就行。（魔法阵��或魔法阵��与不同颜色魔法阵相邻就输出2，否则输出3）

AC代码：

#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; }