自动搬运

查看原文

来自洛谷，原作者为

	RedreamMer 一拍桌子，两眼放光，三十分钟，四百分贝，五指指天，六重积分，七次反演，八维凸包，九只 log，十种做法，全部假啦！！！

搬运于2025-08-24 22:23:05，当前版本为作者最后更新于2020-07-28 18:55:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\Large\texttt{P6687}$

又是一道套路题

算法：逆序对（归并排序）

$\Large\texttt{Solution}$

题目应该很好理解，就不做赘述。

对于一个 $2*2$ 的表格：

1 2
3 4

旋转一次后：

4 3
2 1

可以发现每一列的两个数字是永远呆在一起的，只是上下可能会调换位置。

所以我们可以判断是否有解的问题：以第一个表格第一行作为关键字建桶，将第二行的数放入桶中，与之对应，再遍历第二个表格。

若在 $b[i][j]$ 找到一个关键字 （令这个数字在第一个表格中为 $a[n][m]$ ）判断：

1. 与 $b[i][j]$ 同一列的数是否等于 与$a[n][m]$ 同一列的数。

2. 若 $|m-j|$为奇数，则这一列数字肯定反转了奇数次，则这一列数字一定顺序相反。

3. 若 $|m-j|$为偶数，则这一列数字肯定反转了偶数次，则这一列数字一定顺序一样。

然后就是求解。

因为同一列的数永远不会分离，所以将它们看作同一个数，每次旋转，意义就是交换 $i$ 和 $i+1$ 两个数，然后你就会发现这就是一道经典的逆序对问题。

最后，不要忘记特判列数等于 $1$ 的情况。

$\Large\texttt{Code}$

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7;
#define int long long
#define MP make_pair

int a, s1[2][N + 10], s2[2][N + 10], top, s[N + 10], l[N + 10], ans, st[N + 10];

void msort(int n, int m)
{
    if (n == m)
        return;
    int mid = (n + m) / 2;
    msort(n, mid);
    msort(mid + 1, m);
    int i = n, j = mid + 1, k = n;
    while (i <= mid && j <= m)
    {
        if (s[i] > s[j])
        {
            l[k++] = s[j++];
            ans += mid - i + 1;
        }
        else
        {
            l[k++] = s[i++];
        }
    }
    while (i <= mid)
        l[k++] = s[i++];
    while (j <= m)
        l[k++] = s[j++];
    for (int i = n; i <= m; i++)
        s[i] = l[i];
}

signed main()
{
    scanf("%lld", &a);
    for (int i = 0; i <= 1; i++)
        for (int j = 1; j <= a; j++)
            scanf("%lld", &s1[i][j]);
    for (int i = 0; i <= 1; i++)
        for (int j = 1; j <= a; j++)
            scanf("%lld", &s2[i][j]);
    for (int i = 1; i <= a; i++) st[s1[0][i]] = i;//以第一行为关键字将第二行数字放入桶中
    if (a == 1)//考场上写的11分代码
    {
        if (s1[0][1] == s2[0][1] || s1[1][1] == s2[1][1])
            puts("0");
        else
            puts("dldsgay!!1");
        return 0;
    }
    else if (a == 2)
    {
        if (s1[0][1] == s2[0][1] && s1[1][1] == s2[1][1] && s1[0][2] == s2[0][2] && s1[1][2] == s2[1][2])
            puts("0");
        else if (s1[0][1] == s2[1][2] && s1[1][2] == s2[0][1] && s1[0][2] == s2[1][1] && s1[1][1] == s2[0][2])
            puts("1");
        else
            puts("dldsgay!!1");
        return 0;
    }
    for (int i = 1; i <= a; i++)//判断是否有解以及建造一个要排序的数组s
    {
        if (st[s2[0][i]])
        {
            if ((i - st[s2[0][i]]) & 1)
            {
                puts("dldsgay!!1");
                return 0;
            }
            s[i] = st[s2[0][i]];
            continue;
        }
        else if (st[s2[1][i]])
        {
            if ((i - st[s2[1][i]]) & 1 == 0)
            {
                puts("dldsgay!!1");
                return 0;
            }
            s[i] = st[s2[1][i]];
            continue;
        }
        puts("dldsgay!!1");
        return 0;
    }
    for (int i = 1; i <= a; i++)
        if (!s[i])
        {
            puts("dldsgay!!1");
            return 0;
        }
    msort(1, a);
    printf("%lld", ans);
    return 0;
}

$\Large\texttt{My Blog}$