Chaos Slover 补档计划 - 置换

2015.11.12 10:55 Thu| 3 visits oi_2016| ChaosSlover补档计划| Text

老规矩:我的代码交到 POJ 上一定会 CE。

置换

置换的乘方:

对于置换 a=T,a'=T^k,设 T 的长度为 L。若 L 与 K 互素,a'[i]=a[i*k mod L]。

置换都是些什么乱七八糟的 T T 不会把人绕晕掉么?

POJ3270 Cow Sorting

题意:给出一群牛,每一只牛都有脾气,牛的脾气两两不同。农夫约翰要把这些牛按照脾气从小到大排序,每一次可以交换两头牛,代价为这两头牛的脾气之和。问最小代价。

首先会发现排好序的序列和原序列之间会形成一个置换,置换分为了许多循环节,我们的目标就是将每一个循环节内部排好序。

在某一个循环节内部排序时,会有两种情况:

  • 循环节内最小的元素和其他元素各交换一次。
  • 全局最小的不在循环节内的元素先与循环节内最小的元素交换一次,然后作为中介和其他元素交换一圈后再和循环节内最小的元素交换回去。 然后随便搞一搞就好了。大概需要考虑循环节长度为1的情况(其实不考虑也完全没有关系)。
 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
#include <bits/stdc++.h>
using namespace std;

#define N 10005

int n, tot, a[N], t[N], mina[N], vis[N], sum[N], cnt[N];
pair<int, int> b[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], b[i] = make_pair(a[i], i);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        t[b[i].second] = i;
    memset(mina, 0x3f, sizeof mina);
    for (int i = 1; i <= n; ++i)
        if (!vis[i])
        {
            int now = i; ++tot;
            do
                ++cnt[tot], vis[now] = 1,
                sum[tot] += a[now], mina[tot] = min(mina[tot], a[now]);
            while ((now = t[now]) != i);
        }
    for (int i = 1; i <= n; ++i)
        mina[0] = min(mina[0], mina[i]);
    int ans = 0;
    for (int i = 1; i <= tot; ++i)
        if (cnt[i] > 1)
            ans += min(sum[i] + mina[i] + mina[0] * (cnt[i] + 1),
                       sum[i] + mina[i] * (cnt[i] - 2));
    cout << ans << endl;
    return 0;
}

POJ1026 Cipher

题意:给出一个长度为 N 的置换。之后每一次给出一个长度为 N 的字符串(不够就用空格补齐),问在 K 次之后它会变成什么样子。

显然对于一个长度为 L 的循环中的每一个元素,我们只需要进行 K % L 次置换操作。需要先预处理出来每一个数被置换了几次,这样就可以大大减少循环次数(至多置换 N 次,千万不要偷懒求置换的最小公倍数)。

POJ 的输出格式真是 ** 了。我们需要在每一大组输出后面加上一个空行……

 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
#include <bits/stdc++.h>
using namespace std;

#define N 205

int n, k, tot, a[N], vis[N], cnt[N];
char str[N], ans[N];
vector<int> v[N];

int main()
{
    while (cin >> n, n)
    {
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        str[n + 1] = ans[n + 1] = '\0';
        memset(vis, 0, sizeof vis);
        for (int i = 1; i <= n; ++i)
            v[i].resize(0);
        tot = 0;
        for (int now, i = 1; i <= n; ++i)
            if (!vis[now = i] && ++tot)
                do
                    vis[now] = 1, v[tot].push_back(now);
                while ((now = a[now]) != i);
        for (int i = 1; i <= tot; ++i)
            for (int j = 0; j < (int)v[i].size(); ++j)
                cnt[v[i][j]] = v[i].size();
        while (scanf("%d", &k), k)
        {
            getchar(); gets(str + 1);
            for (int i = strlen(str + 1) + 1; i <= n; ++i)
                str[i] = ' ';
            for (int t = 0, i = 1; i <= k && t < n; ++i)
            {
                for (int j = 1; j <= n; ++j)
                {
                    if (i > k % cnt[j]) ans[j] = str[j];
                    else ans[a[j]] = str[j];
                    if (i == k % cnt[j]) ++t;
                    if (i == 1 && k % cnt[j] == 0) ++t;
                }
                memcpy(str, ans, sizeof str);
            }
            puts(str + 1);
        }
        puts("");
    }
    return 0;
}

POJ1721 CARDS

题意:洗牌。设第 x 个位置上的牌是 a[x],那么在一次洗牌后第 i 个位置上的牌就会变为 a[a[i]] 。已知某个牌组在洗 S 次之后得到的牌组,问原牌组的顺序。

置换的开方运算。题目的含义就是给出了一个置换,需要我们去开 2^S 次方。很显然,题目给出的 N 是一个奇数,和 2^S 是互素的。由置换的乘方公式,我们就可以求逆元算开方了。

具体来说,我们需要先把序列处理成循环的形式,然后利用 exgcd 求出原置换,最后转回序列的形式并输出。(我竟然能一次 AC 真是太神了。本来打算如果不能 AC 就去扒别人代码的说。

网上找的题解里面都并没有用到 exgcd 什么的实在是太神了。然而我并不能够看懂。

我突然发现我绝对是沙茶。求原置换的时候直接按照平方的方式反推回去不就好了嘛 - -|| 少了整整一个 log 呢!

 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
#include <bits/stdc++.h>
using namespace std;

#define N 2005

int power(int a, int b, int c)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = re * a % c;
        a = a * a % c; b >>= 1;
    }
    return re;
}

pair<int, int> exgcd(int a, int b)
{
    if (b == 0) return make_pair(1, 0);
    pair<int, int> t = exgcd(b, a % b);
    return make_pair(t.second, t.first - a / b * t.second);
}

int n, s, a[N], b[N], t[N], ans[N];

int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int p = power(2, s, n);
    if (p == 0) p += n;
    for (int i = 0, now = 1; i < n; ++i)
        b[i] = now, now = a[now];
    for (int i = 0; i < n; ++i)
        t[i] = b[(i * exgcd(p, n).first % n + n) % n];
    for (int i = 0; i < n; ++i)
        ans[t[i]] = t[(i + 1) % n];
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << endl;
    return 0;
}

O(N) 版本:

 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
#include <bits/stdc++.h>
using namespace std;

#define N 2005

int power(int a, int b, int c)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = re * a % c;
        a = a * a % c; b >>= 1;
    }
    return re;
}

int n, s, a[N], b[N], t[N], ans[N];

int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int p = power(2, s, n);
    if (p == 0) p += n;
    for (int i = 1, now = 1; i <= n; ++i)
        b[i] = now, now = a[now];
    for (int i = 1, now = 1; i <= n; ++i)
        t[now] = b[i],
        now = (now + p) % n == 0 ? n : (now + p) % n;
    for (int i = 1; i < n; ++i)
        ans[t[i]] = t[i + 1];
    ans[t[n]] = t[1];
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << endl;
    return 0;
}