题解【JOI 2020/2021 二次予選】B

题面

好题。

因为 (3^{13}=1594323)，所以首要想法就是先打一个答案的表出来，最后在询问时直接输出。

考虑先爆搜出所有合法的字符串（即所有递增的字符串），然后将每个字符串看成一个三进制数（A 对应 (1)，B 对应 (2)，C 对应 (3)），把每个三进制数抽象成一个点。如果一个字符串能够通过一次翻转操作变成另一个字符串，就将这两个字符串对应的三进制数之间连一条边。

将所有合法的字符串先加进队列，直接跑一遍最短路即可。

但是本机跑 4s 的代码交到 AtCoder 上只要跑 1s 是怎么一回事呢？小编也不知道。

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

template <typename T>
inline T gi()
{
	T f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 10000003, M = N << 1;

int n, q;
int tot, head[N], ver[M], nxt[M];
int dis[N];
vector <string> str;

inline void add(int u, int v)
{
	ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}

inline int zh(string x)
{
	int now = 0;
	for (int i = 0; i < n; i+=1)
		now = now * 3 + (x[i] - 'A');
	return now;
}

void dfs(int u, string now)
{
	if (u > n) {str.push_back(now); return;}
	for (char i = (u == 1) ? 'A' : now[(int)now.size() - 1]; i <= 'C'; i+=1)
		dfs(u + 1, now + i);
}

inline void pre(int len)
{
	dfs(1, "");
	queue <string> q;
	memset(dis, 0x3f, sizeof dis);
	for (auto x : str) q.push(x), dis[zh(x)] = 0;
	while (!q.empty())
	{
		string u = q.front(); q.pop();
		int qz = zh(u);
		for (int i = 2; i <= n; i+=1)
		{
			string now = u;
			reverse(now.begin(), now.begin() + i);
			int tar = zh(now);
			if (dis[tar] == INF)
			{
				dis[tar] = dis[qz] + 1;
				q.push(now);
			}
		}
	}
}

int main()
{
	//File("");
	n = gi <int> (), q = gi <int> ();
	pre(n);
	while (q--)
	{
		string x; cin >> x;
		printf("%d
", dis[zh(x)]);
	}
	return 0;
}