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

目描述比太郎所在的魔法学校即将举办运动会。运动会中有一个项目称为“魔法阵”。有 个魔法阵依次排列在一个圆上顺时针编号为 1 到 。每个魔法阵为红色或蓝色中的一种使用长度为 且仅包含小写字母b和r字符串 表示(1≤≤) 为r则表示魔法阵 为红色否则为蓝色。比太郎可以通过如下的两种方式在魔法阵中传送选择一个相邻的魔法阵花费 1 秒传送过去。换句话说可以在魔法阵 (1≤≤−1) 和 1 间传送两个方向均可也可以在魔法阵 1 和 间传送两个方向均可选择一个与当前所在魔法阵颜色相同的魔法阵不一定要相邻花费 1 秒传送过去。目前他仅得知每个魔法阵的颜色但并不知道运动会当天具体的传送计划。于是他决定考虑 个传送计划在第 个计划中他要从魔法阵 开始花费最少的时间传送到魔法阵 。请你对于每一个传送计划求出最少需要花费的时间。输入格式第一行输入两个整数 ,。第二行输入一个字符串 。接下来 行每行输入两个整数 ,。输出格式输出 行在第 行输出一个整数表示第 个传送计划最少需要花费的传送时间单位秒。输入输出样例 #1输入 #15 2 rbrbb 5 3 4 5输出 #12 1输入输出样例 #2输入 #24 3 brrr 2 4 1 3 3 1输出 #21 2 2输入输出样例 #3输入 #36 3 brbrbr 1 2 2 5 2 4输出 #31 2 1输入输出样例 #4输入 #46 5 bbbrrr 2 3 2 4 2 5 2 6 2 1输出 #41 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×1051≤≤5×105 为仅包含小写字母b和r的长度为 的字符串1≤,≤(1≤≤)≠(1≤≤)。【子任务】6 分3≤10013 分1 为b 的其他字符均为r18 分 为偶数 奇数位置的字符为b偶数位置的字符为r23 分 为偶数 的前 2 个字符为b后 2 个字符为r21 分,≤10019 分无附加限制。题解题意给出一个含有 N 个点的圆每个点为红色或蓝色使用相邻传送和同色传送求出从点 x 至点 y 的最少传送次数。思路≠(1≤≤)。至少也要传送一次所以有两种情况颜色相同 || 魔法阵和魔法阵相邻那么直接同色传送就行输出1。颜色不同 魔法阵和魔法阵不相邻那么在圆上必定存在两种不同颜色相邻可以从魔法阵同色传送到其中一个相邻传送到另一个再同色传送到魔法阵。所以最多3次。直接用if大法分类讨论一下就行。魔法阵或魔法阵与不同颜色魔法阵相邻就输出2否则输出3AC代码#includebits/stdc.h using namespace std; int main(){ int n,q,i,x,y,s,b,sum; string a; cinnq; cina; a a; for(;q0;q--){ cinxy; if(a[x]a[y]||abs(x-y)1||abs(x-y)n-1){ cout1\n; continue; } sy-1,by1; if(s1) sn;///////注意魔法阵依次排列在一个圆上首尾相连要注意边界 if(bn) b1; if(a[s]a[x]||a[b]a[x]){ cout2\n; continue; } sx-1,bx1; if(s1) sn; if(bn) b1; if(a[s]a[y]||a[b]a[y]){ cout2\n; continue; } cout3\n; } return 0; }