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

#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;
}