Luobuyu's Blog

0%

1762.牛的洗牌

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 1.9k 阅读时长 ≈ 2 分钟
是置换群，进行反向置换得到答案。

1762. 牛的洗牌

题目描述：

农夫约翰坚信快乐的奶牛会产出更多的牛奶，因此他在谷仓中安装了一个巨大的迪斯科球，并计划教他的奶牛跳舞！

在查阅了一些牛的流行舞蹈后，约翰决定教他的奶牛“洗牌舞”。

洗牌舞是由他的 $ N $ 只奶牛按一定顺序排成一行，然后连续执行三次“洗牌”，每次“洗牌”都可能会使奶牛重新排序。

为了让奶牛们更容易找到自己所处的位置，约翰用数字 $ 1 \sim N $ 对一行中奶牛所在的位置进行了标记，一行中第一头奶牛处于位置 $ 1 $ ，第二头奶牛处于位置 $ 2 $ ，以此类推，直到位置 $ N $ 。

每次“洗牌”用 $ N $ 个数字 $ a_1,a_2,\cdots ,a_N $ 来描述，处于位置 $ i $ 的奶牛在一次“洗牌”过后，需要移动至位置 $ a_i $ （因此，每个 $ a_i $ 在 $ 1\cdots N $ 范围内）。

幸运的是，所有 $ a_i $ 都是互不相同的，因此，不会存在多头奶牛在洗牌结束后移动到同一个位置的情况。

约翰的每头奶牛都有一个属于自己的唯一 $ 7 $ 位整数 $ ID $ （不含前导 $ 0 $ ）。

给定你三轮“洗牌”过后的奶牛排列顺序，请你求出奶牛们的初始排列顺序。

输入格式

第一行包含整数 $ N $ 。

第二行包含 $ N $ 个整数，表示 $ a_1,a_2,\cdots ,a_N $ 。

第三行包含了 $ N $ 头奶牛三轮“洗牌”过后的排列顺序，每头奶牛都用其 $ ID $ 指代。

输出格式

共 $ N $ 行，按照 $ N $ 头奶牛的初始排列顺序，每行输出一头奶牛的 $ ID $ 。

数据范围

输入样例：

1
2
3
5
1 3 4 5 2
1234567 2222222 3333333 4444444 5555555

输出样例：

1
2
3
4
5
1234567
5555555
2222222
3333333
4444444

题解：

原1 5 2 3 4
置换1 3 4 5 2
第一次1 4 5 2 3
第二次1 5 2 3 4
第三次1 2 3 4 5

题目中的洗牌就是 $ i\to a[i] $ ，因此逆向洗牌就是 $ a[i] \to i $ ,可以得到反向洗牌数组。b[a[i]] = i;得到反向洗牌数组之后可以直接模拟三次 a[b[i]] = i 也就是 a[b[b[b[i]]]] = i 这样的话就可以一次得到原数组。

原1 2 3 4 5
置换1 5 2 3 4
第一次1 3 4 5 2
第二次1 4 5 2 3
第三次1 5 2 3 4

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
string s[maxn];
int a[maxn];
int b[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        // 原来 i位置a[i]跑到了 a[a[i]]
        // 就是 i -> a[i]
        // 逆 a[i] -> i
        cin >> a[i];
        b[a[i]] = i;
    }
    // for (int i = 1; i <= n; i++)
    // {
    //     cout << b[i] << " ";
    // }
    // cout << endl;
    string ch;
    for (int i = 1; i <= n; i++)
    {
        cin >> ch;
        s[i] = ch;
    }
    // s[i]
    // b 是转换数组
    for (int i = 1; i <= n; i++)
    {
        a[b[b[b[i]]]] = i;
    }

    for (int i = 1; i <= n; i++)
    {
        cout << s[a[i]] << endl;
    }
    return 0;
};

// 1 5 2 3 4
// 1 3 4 5 2
// 1 4 5 2 3     ----1
// 1 5 2 3 4     ----2
// 1 2 3 4 5     ----3

// 1 2 3 4 5
// 1 5 2 3 4
// 1 3 4 5 2     ----1
// 1 4 5 2 3     ----2
// 1 5 2 3 4     ----3