CSP-S 提高级 · CSP 2020 提高级第一轮 第 18 题

3.

#include <iostream>
#include <queue>
using namespace std;

const int maxl = 20000000;

class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
  public:
    int find(string x) {
        for (int i = 0; i < cnt; ++i)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];

class Queue {
    string q[maxl];
    int head, tail;
  public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x;  }
} q[2];

string st0, st1;
int m;

string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}

st

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考双向BFS找最少步数。拿到题先看check函数：它检查当前串能否通过一次左旋或右旋变成目标串。若不能，就尝试生成新串并压入队列；若能在另一方向找到，直接输出总步数。双向BFS的核心是p^=1交替扩展，相遇时总步数=step[p]+step[other]。

最容易错在把LtoR和RtoL搞反，导致生成的串不对；其次是认为m=0时能产生所有循环移位，其实m=0时左旋是整体移、右旋是空操作，只能整体移；还有双向BFS里check函数里的step++后检查另一方向是否已访问，很多人会漏掉这个细节，导致重复搜索或漏掉相遇点。

考察知识点

• 双向广度优先搜索（Bidirectional BFS）
• 字符串旋转操作（左旋LtoR、右旋RtoL）
• Map与队列的配合
• 步数统计与相遇判定

概念定义

双向BFS：从起点和终点同时出发，交替扩展一层。当两个方向的搜索在某个状态相遇时，就找到了最短路径。相比单向BFS，搜索空间从b^d缩小到约2b^(d/2)。

左旋 LtoR(s, L, R)：把s[L]移到s[R]，中间元素左移。 右旋 RtoL(s, L, R)：把s[R]移到s[L]，中间元素右移。

核心数据结构：

• s[0]、s[1]：分别记录从st0、st1出发的访问表（key=串，value=步数）。
• q[0]、q[1]：对应队列。
• p ^= 1：交替从两个队列取头。