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），比太郎可以使用如下传送方案：
- 从魔法阵 5 传送到相邻的魔法阵 1，花费 1 秒；
- 从魔法阵 1 传送到颜色相同的魔法阵 3，花费 1 秒。
最少需要花费的时间为 2 秒。可以证明不可能在小于 2 秒的时间内从魔法阵 5 传送到魔法阵 3。
对于第二组计划（4→5），比太郎可以使用如下传送方案：
- 从魔法阵 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≤�≤�)。
【子任务】
- （6 分）�=3，�≤100；
- （13 分）�1 为
b，� 的其他字符均为r； - （18 分）� 为偶数，� 奇数位置的字符为
b，偶数位置的字符为r； - （23 分）� 为偶数，� 的前 �2 个字符为
b，后 �2 个字符为r； - （21 分）�,�≤100；
- （19 分）无附加限制。
题解
题意
给出一个含有 N 个点的圆，每个点为红色或蓝色，使用相邻传送和同色传送，求出从点 x 至点 y 的最少传送次数。
思路
- ��≠��(1≤�≤�)。
至少也要传送一次
所以有两种情况：
- 颜色相同 || 魔法阵��和魔法阵��相邻
那么直接同色传送就行，输出1。 - 颜色不同 && 魔法阵��和魔法阵��不相邻
那么在圆上必定存在两种不同颜色相邻，可以从魔法阵��同色传送到其中一个，相邻传送到另一个，再同色传送到魔法阵��。所以最多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; }