题解：P14331 [JOI2021 预选赛 R2] 煎饼 / Pancake

Beijing_duck_ · 2025-10-31 13:56:43 · 题解

[JOI2021 预选赛 R2] 煎饼 / Pancake

by Beijing_duck_ 2025/10/31
蒟蒻题解 2^{nd}

题意简述

• 称一个字符串串为“烤串”当且仅当这个串 AA...ABB...BCC...C 的形式（即 A 全部在最前面， C 全部在最后面， B 全部在中间）。
• 给定一个由 A、B、C 三种字符组成的字符串，你需要通过最少次数的操作将这个串变成“烤串”。
• 操作：将原串从 1 到 n 的位置反转。
• 输出最少的次数。

思路

• 首先看范围 2 \le N \le 13 时限 2.5s ，那么 3 ^ N 的复杂度是可接受的。
• 可以将原串变为烤串的过程逆推（发现给定操作的逆操作依然是这个操作）。
• 从最终的烤串出发，最多有 3^N 种状态，可以 BFS 预处理所有状态最少的操作步数。

::::success[AC代码]

#include "bits/stdc++.h"
using namespace std;

int n, q;        // n: 煎饼数量，q: 查询数量
int tot;         // 总状态数 = 3^n
vector<int> d;   // 存储每个状态到目标状态的最短距离

// 将字符串转换为状态ID
int sid(const string& s) {
    int id = 0;
    for (char c : s) {
        id = id * 3 + (c - 'A');  // A=0, B=1, C=2
    }
    return id;
}

// 检查是否是目标状态A...A B...B C...C）
bool isd(const string& s) {
    for (int i = 0; i + 1 < s.size(); i++) {
        if (s[i] > s[i + 1]) return false;  // 如果发现逆序，不是目标状态
    }
    return true;
}

// 将状态ID转换为字符串
string id_str(int id) {
    string s(n, ' ');
    int x = id;
    for (int i = n - 1; i >= 0; i--) {
        s[i] = 'A' + (x % 3);
        x /= 3;
    }
    return s;
}

int main() {
    cin >> n >> q;

    tot = 1;
    for (int i = 0; i < n; i++) tot *= 3;
    d.resize(tot, -1);  // 初始化，-1表示未访问

    // BFS预处理：从所有目标状态开始反向搜索
    queue<int> qu;
    for (int id = 0; id < tot; id++) {
        string s = id_str(id);
        if (isd(s)) {      // 如果是目标状态
            d[id] = 0;     // 距离为0
            qu.push(id);   // 加入队列
        }
    }

    // BFS主循环
    while (!qu.empty()) {
        int u = qu.front();  // 当前状态ID
        qu.pop();

        string s = id_str(u);  // 当前状态对应的字符串

        // 尝试所有可能的操作k：翻转前k个煎饼
        for (int k = 2; k <= n; k++) {
            string t = s;
            reverse(t.begin(), t.begin() + k);  // 翻转前k个字符

            int vid = sid(t);  // 新状态ID
            if (d[vid] == -1) {  // 如果新状态未被访问
                d[vid] = d[u] + 1;  // 更新距离
                qu.push(vid);       // 加入队列
            }
        }
    }

    // 处理查询
    for (int i = 0; i < q; i++) {
        string s;
        cin >> s;
        int id = sid(s);      // 将输入字符串转换为状态ID
        cout << d[id] << "\n"; // 输出最短操作次数
    }

    return 0;
}

::::