P6482 [CRCI2006-2007] CIRCLE

SDqwq · 2020-12-31 13:02:17 · 题解

建议此题评蓝。

博客食用更佳

前置芝士 1：最小表示法

前置芝士 2：\texttt{set}

前置芝士 3：\texttt{dfs}

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