自动搬运

查看原文

来自洛谷，原作者为

	SDqwq 少年何妨梦摘星，敢挽桑弓射玉衡。

搬运于2025-08-24 22:21:12，当前版本为作者最后更新于2020-12-31 13:02:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

建议此题评蓝。

博客食用更佳

前置芝士 $1$：最小表示法

前置芝士 $2$：$\texttt{set}$

前置芝士 $3$：$\texttt{dfs}$

$\texttt{update: 2020/12/31 增加了关于倒推时的说明}$

$\texttt{Step 0 题意}$

• 给出一个由 $\texttt{"B"}$ 和 $\texttt{"W"}$ 构成的初始字符环。

• 给出操作次数 $k$。

• 对于每次操作：

  • 如果相邻的字符相同，则在它们之间插入一个 $\texttt{"B"}$。

  • 如果相邻的字符不同，则在它们之间插入一个 $\texttt{"W"}$。

• 求有多少种初始字符环通过 $k$ 次操作能得到目标字符环。

$\texttt{Step 1 正解}$

• 通过初始字符环可以模拟出目标字符环。

• 通过目标字符环可以通过 $\texttt{dfs}$ 倒推 $k$ 步。

• 对于每次倒推 $1$ 步：

  • 讨论 $2$ 种情况，分别是第一位为 $\texttt{"B"}$ 和第一位为 $\texttt{"W"}$ 的情况。

  • 若第一位为 $\texttt{"B"}$，对于上一步字符环的第 $i$ 位来说：

    • 若上一步字符环的第 $i$ 位为 $\texttt{"B"}$，则当前字符环的第 $i+1$ 位为当前字符环的第 $i$ 位。

    • 若上一步字符环的第 $i$ 位为 $\texttt{"W"}$，则当前字符环的第 $i+1$ 位为当前字符环的第 $i$ 位取反。

    • 最后判断一下构造出的字符环第 $1$ 位与第 $n$ 位的相等情况，是否符合上一步字符环第 $n$ 位的字符。

  • 若第一位为 $\texttt{"W"}$，构造方法同上。

• 把每个倒推出的字符环都求出最小表示法的字符串，这样可以看出是否环同构。

• 把推到 $k$ 步时的 $2^k$ 个字符环的最小表示法的字符串扔进一个 $\texttt{set}$ 中去重。

• 这个 $\texttt{set}$ 的 $\texttt{size}$ 即为答案。

时间复杂度：$\mathcal{O}(2^kn^2k)$

$\texttt{Step 2 代码}$

#include <cstdio>
#include <iostream>
#include <cstring>
#include <set>

using namespace std;

string Min (string x, string y) {return x < y ? x : y;}

int n, k;
string s, target;

set<string> S;

string get (string s) {
	string ret;
	ret = s;
	for (int i = 1; i < n; i++) {
		string tot = ret;
		int cnt = 0;
		for (int j = i; j < n; j++)
			tot[cnt++] = s[j];
		for (int j = 0; j < i; j++)
			tot[cnt++] = s[j];
		ret = Min(ret, tot);
	}
//	cout << s << " " << ret << endl;
//	cout << s << endl;
//	cout << ret << endl;
	return ret;
}

char change (char c) {return c == 'B' ? 'W' : 'B';}

void dfs (int x, string tot) {
	if (x == k) {
		S.insert(get(tot));
		return;
	}
	string t = tot;
	tot[0] = 'B';
	for (int i = 1; i < n; i++) {
		if (t[i - 1] == 'B')
			tot[i] = tot[i - 1];
		else
			tot[i] = change(tot[i - 1]);
	}
	if ((tot[n - 1] == tot[0] && t[n - 1] == 'B') || (tot[n - 1] != tot[0] && t[n - 1] == 'W'))
		dfs(x + 1, tot);
	tot[0] = 'W';
	for (int i = 1; i < n; i++) {
		if (t[i - 1] == 'B')
			tot[i] = tot[i - 1];
		else
			tot[i] = change(tot[i - 1]);
	}
	if ((tot[n - 1] == tot[0] && t[n - 1] == 'B') || (tot[n - 1] != tot[0] && t[n - 1] == 'W'))
		dfs(x + 1, tot);
}

int main () {
	scanf("%d %d", &n, &k);
	cin >> s;
	target = s;
	for (int i = 1; i <= k; i++) {
		char t = target[0];
		for (int j = 0; j < n - 1; j++) {
			if (target[j] == target[j + 1])
				target[j] = 'B';
			else
				target[j] = 'W';
		}
		if (target[n - 1] == t)
			target[n - 1] = 'B';
		else
			target[n - 1] = 'W';
	}
//	cout << target;
	dfs(0, target);
	printf("%d", S.size());
	return 0;
}