链接：https://ac.nowcoder.com/acm/contest/127702

A – 红美铃的访客登记

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    int x;
    cin >> x;

    cout << x << endl;
}

B – 爱丽丝的魔力零件分类

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    auto ok = [&](int x, int y) -> bool
    {
        return x >= 0 && x < n && y >= 0 && y < n && s[x][y] == '*';
    };

    auto check1 = [&](int x, int y) -> bool
    {
        if (ok(x, y) && ok(x, y + 1) && ok(x, y + 2) &&
            (ok(x + 1, y + 1) || ok(x - 1, y + 1)))
            return 1;
        else if (ok(x, y) && ok(x + 1, y) && ok(x + 2, y) &&
                 (ok(x + 1, y - 1) || ok(x + 1, y + 1)))
            return 1;

        return 0;
    };

    auto check2 = [&](int x, int y) -> bool
    {
        if (ok(x, y) && ok(x, y + 1) && ok(x, y + 2) &&
            (ok(x + 1, y + 2) || ok(x - 1, y + 2) || ok(x + 1, y) || ok(x - 1, y)))
            return 1;
        else if (ok(x, y) && ok(x + 1, y) && ok(x + 2, y) &&
                 (ok(x + 2, y - 1) || ok(x + 2, y + 1) || ok(x, y + 1) || ok(x, y - 1)))
            return 1;

        return 0;
    };

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (s[i][j] == '*')
            {
                if (check1(i, j))
                {
                    cout << 'T' << endl;
                    return;
                }

                if (check2(i, j))
                {
                    cout << 'L' << endl;
                    return;
                }
            }
        }
    }
}

C – 博丽大结界的稳定轴心

算法：

贪心，二叉树。

思路：

二叉树中不存在度大于 \(3\) 的节点，因此当某个点的度大于 \(3\) 时，不存在答案。

二叉树中度为 \(3\) 的节点，必然是一个中间节点（既不是根节点也不是叶子节点的节点），其余度数的节点都可以当作根，因此答案为 \(n – deg_3\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> deg(n + 1, 0);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        ++deg[u];
        ++deg[v];
    }

    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (deg[i] >= 3)
            ++cnt;

        if (deg[i] > 3)
        {
            cout << 0 << endl;
            return;
        }
    }

    cout << n - cnt << endl;
}

D – 魔法人偶的十进制校准

算法：

数学，打表。

思路：

打表发现 \(\frac{1}{9} = 0.1111…\)，\(\frac{1}{9} * 2 = 0.2222…\)，直到 \(\frac{1}{9} * 8 = 0.8888…\)，最简分数都满足互质要求，因此当 \(b \ge 1\) 且 \(b \le 8\) 时，都可以构造上面的例子，注意需要化简至最简分数。

考虑 \(b = 0\)：

• 当 \(a = 1\) 时，可以构造 \(0.0100…\)，既 \(\frac{1}{100}\)；
• 否则可以构造 \(0.1000…\)，既 \(\frac{1}{10}\)。

考虑 \(b = 9\)：

• 打表发现，\(\frac{10}{11} = 0.9090….\)，\(\frac{1}{11} = 0.0909….\)，可以分将 \(a\) 奇偶情况进行构造。

关键代码：

void miyan()
{
    ll a, b;
    cin >> a >> b;

    if (b >= 1 && b <= 8)
        cout << b / gcd(b, 9) << ' ' << 9 / gcd(b, 9) << endl;
    else if (b == 9)
    {
        if (a & 1)
            cout << 10 << ' ' << 11 << endl;
        else
            cout << 1 << ' ' << 11 << endl;
    }
    else
    {
        if (a == 1)
            cout << 1 << ' ' << 100 << endl;
        else
            cout << 1 << ' ' << 10 << endl;
    }
}

E – 爱丽丝的人偶圆舞曲

算法：

\(dp\)。

思路：

容易想到 \(dp\)。

定义 \(dp[i][j][d]\) 表示将 \(s[i]\) 变为 \(j\) 且变化后整个序列颜色数值差为 \(d\) 或 \(– d\) 的最小操作次数。

考虑到只有相同的 \(d\) 之间才能进行转移，可以将第三维 \(d\) 优化掉，改为只枚举 \(d\)，状态中不记录 \(d\)。

状态转移：

• 枚举 \(d\)，并求每个 \(d\) 的答案，取全局最小答案，对于当前的 \(d\)，\(dp\) 表为 \(dp[i][j]\)；
• 对于 \((i, j)\)，可以想到其可以通过 \((i – 1, (j + d) \text{%} 26)\) 和 \((i – 1, (j – d + 26) \text{%} 26)\) 转移而来，那么状态转移公式为 \(dp[i][j] := min(dp[i – 1][(j + d) \text{%} 26], dp[i – 1][(j – d + 26) \text{%} 26])\)，由于 \(j\) 与 \(s[i]\) 可能不相等（需要进行一次操作改变），因此当 \(s[i] \neq j\) 时，还需执行 \(dp[i][j] := dp[i][j] + 1\)。

发现 \((i, j)\) 只与 \((i – 1, k), k∈[0, 26)\) 有关，可以滚动数组，代码就不给出了。

关键代码：

void miyan()
{
    string s;
    cin >> s;

    int n = s.size();

    s = ' ' + s;

    int ans = INT_MAX;
    for (int d = 0; d < 26; ++d)
    {
        vector dp(n + 1, vector<int>(26, INT_MAX));
        for (int i = 0; i < 26; ++i)
        {
            dp[1][i] = 1;

            if (s[1] - 'a' == i)
                dp[1][i] = 0;
        }

        for (int i = 2; i <= n; ++i)
        {
            for (int j = 0; j < 26; ++j)
            {
                int l1 = (j + d) % 26;
                int l2 = (j - d + 26) % 26;
                int t = ((s[i] - 'a') != j);

                dp[i][j] = min({dp[i][j], dp[i - 1][l1] + t, dp[i - 1][l2] + t});
            }
        }

        ans = min(ans, ranges::min(dp[n]));
    }

    cout << ans << endl;
}

F – 红魔馆的微瑕序位

算法：

置换环，并查集。

思路：

置换环模板题。

最终满足题目要求的情况就是只存在一个大小为 \(2\) 的置换环其余全是大小为 \(1\) 的置换环，并且这个大小为 \(2\) 的置换环中的元素是相邻的（两个元素差为 \(1\)）。

定义 \(cnt\) 为所有置换环所需要的操作次数：

当不存在相邻两个元素 \((x, x + 1)\) 在同一个置换环中时，那么变成最终状态所需的操作次数就会加一次，既先将数组变成有序排列，再任意交换两个元素，最终答案为 \(cnt + 1\)；

当存在相邻两个元素 \((x, x + 1)\) 在同一个置换环中时，那么变成最终状态所需的操作次数就会少一次，最终答案为 \(cnt – 1\)；

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int cnt = 0;
    vector<int> id(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        if (id[i])
            continue;

        ++cnt;
        int cur = i;
        while (id[cur] == 0)
        {
            id[cur] = cnt;
            cur = a[cur];
        }
    }

    bool ok = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (id[i] == id[i - 1])
        {
            ok = 1;
            break;
        }
    }

    if (ok)
        cout << n - cnt - 1 << endl;
    else
        cout << n - cnt + 1 << endl;
}