P2133 天作之合 题解

· · 题解

题意

定义 6 位长的 X 若只需交换两个字符就能得到 6 位长的 Y，则 X 相似于 Y。问 A 要经过多少次找与当前数的相似数才能得到 S。

思路

标签里虽然写着搜索，但我个人认为实际是用不着的。

首先，我们可以在找相似数这一模块上简化一下。实际上，该过程就是交换字符。所求即为 A 要经过多少次教皇两字符才能得到 S。

那么，直接求 A 与 S 的逆序对，也就是需要交换的数字即可。因为 A 经过操作后一定能变成 S，所以该方法是可行的。并且由于 A 与 S 的长度 6，常数非常小，该代码足以通过该题。

代码

# include <bits/stdc++.h>
using namespace std;
# define int long long
int numa[7], numb[7];
int a, b, ans;
signed main()
{
    cin >> a >> b;
    for (int i = 6; i >= 1; --i)
        numa[a % 10] = i, a /= 10;
    for (int i = 6; i >= 1; --i)
        numb[i] = numa[b % 10], b /= 10;
    for (int i = 1; i <= 5; ++i)
        for (int j = i + 1; j <= 6; ++j)
            if (numb[i] > numb[j]) ++ans;
    if (ans <= 2) ans += 2;
    cout << ans << endl;
    return 0;
}

最后祝各位 \texttt{Oier} 早日成为小明

千山万水总是情，给个点赞行不行~~