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

zhouzihang1 · 2025-11-25 18:53:02 · 题解

马上退役了，来水个题解。

我们用 0 表示字符 \texttt{A}，1 表示字符 \texttt{B}，2 表示字符 \texttt{C}，这样可以用三进制高效的表示一个字符串状态。我们不难爆搜出所有的合法状态，然后我们发现前缀翻转的操作可逆，于是我们将所有的合法状态作为起点，bfs 预处理出所有状态的答案。然后可以做到 O(3^n) 预处理，O(1) 查询。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=14,P=3,M=3e6+10;
inline void read(string &S)
{
    S="";
    char ch=getchar();
    while(ch<'A'||ch>'C') ch=getchar();
    while(ch>='A'&&ch<='C') S+=ch,ch=getchar();
}
int n,Q,dis[M];
inline int getHash(string &S)
{
    int ans=0;
    for(char c:S) ans=ans*3+c-'A';
    return ans;
}
inline string getstr(int x)
{
    string S="";
    while(x) S+=x%3+'A',x/=3;
    while((int)S.size()<n) S+='A';
    assert((int)S.size()==n);
    reverse(S.begin(),S.end());
    return S;
}
bool vis[M];
queue<int> q;
void dfs(int stp,int now,int H)
{
    if(stp==n) return vis[H]=1,q.push(H),void();
    for(int i=now;i<3;++i) dfs(stp+1,i,H*3+i);
}
int main()
{
    scanf("%d%d",&n,&Q);
    dfs(1,0,0);dfs(1,1,1);dfs(1,2,2);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        string s=getstr(x);
        for(int i=2,y;i<=n;i++)
        {
            string t=s;
            for(int j=0;j<i/2;j++) swap(t[j],t[i-j-1]);
            y=getHash(t);
            if(!vis[y]) vis[y]=1,dis[y]=dis[x]+1,q.push(y);
        }
    }
    while(Q--)
    {
        string S;read(S);
        int x=getHash(S);
        printf("%d\n",dis[x]);
    }
    return 0;
}