洛谷：矩阵旋转
观察可以发现： できない
对于这样的两列表格，一次 2x2 的正方形 180° 旋转相当于 左上与右下、左下与右上交换
而这样的交换不会改变什么？不会改变任意一列的两个数字！
但会改变这两个数字的位置关系，旋转一次就上下颠倒一次
所以我们得到了第一个判断无解的条件：
若 原状态 任意一列的两个数字在 目标状态 中位置不是在同一列，显然无解
接着，在排除了以上无解情况后，我们又可以 通过看题解 发现：
原状态 任意一列的两个数字在 目标状态 中对应的位置不同，解的存在性也会改变！
2
/
3
2/3
2/3 要转化成
3
/
2
3/2
3/2 中间旋转的次数显然是 奇数次 ！
同理，若 原状态 到 目标状态 的列上下关系没变，旋转次数就是 偶数次
若不满足这 奇偶性 ，显然无解
—————————————————————————————————————
综上，我们终于探讨完了有无解的判断
那怎么求 最少 旋转次数呢？
可以观察到，同一列的两个数字怎么旋转都是捆绑在一起的、不会变动，所以可以把 一列 当成 一个数字
这样问题就转化成：
原状态 的一列数字 转化成 目标状态 的一列数字，问转化的最小步数（转化方式是交换任意相邻的两列数字）
通过经验我们可知：在一个序列（由母版映射过来）里求逆序对的数量 == 这个序列从母版转化过来的最小步数
所以，上代码：
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define fx first
#define fy second
//#pragma GCC optimize(2)
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1000010, M = 110, MM = 3000010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
struct arr
{
int row, col;
}ch[N << 1];//开大啊！！！开小了re错误都没直接wa
int b[3][N], z[N], tmp[N];
bool check() {
for (int j = 1; j <= n; j++) {
int b1 = b[1][j], b2 = b[2][j];
if (ch[b1].col != ch[b2].col)return false;
//首先先判 同列 是否合法
}
for (int j = 1; j <= n; j++) {
int b1 = b[1][j];
if (ch[b1].row == 1) { //再判奇偶
if (ch[b1].col % 2 != j % 2)return false;
}
else {
if (ch[b1].col % 2 == j % 2)return false;
}
}
return true;
}
ll gui_sort(int l, int r) {
if (l >= r)return 0;//递归边界勿忘，否则死循环上门服务
int mid = l + r >> 1;
ll cnt = gui_sort(l, mid) + gui_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r)
{
if (z[i] <= z[j])tmp[k++] = z[i++];
else {
//找到第一个 i 大于 j，显然 i 之后的所有数都大于 j，统计到逆序对的数量中
cnt += (ll)mid - i + 1;
tmp[k++] = z[j++];
}
}
while (i <= mid)tmp[k++] = z[i++];
while (j <= r)tmp[k++] = z[j++];
for (int i = l; i <= r; i++)z[i] = tmp[i];
return cnt;
}
int main() {
cinios;
cin >> n;
for (int i = 1; i <= 2; i++)
for (int j = 1; j <= n; j++) {
int t;
cin >> t;
ch[t] = { i,j };//记录母版（原状态）的数所处的行列信息
//题目告诉我们数是不重不漏的
//注意这里的数最多有 2*n 个...数组开小了bug找一天
}
for (int i = 1; i <= 2; i++)
for (int j = 1; j <= n; j++)
cin >> b[i][j];//目标状态
if (!check()) {
cout << "dldsgay!!1";
return 0;
}
for (int j = 1; j <= n; j++)//母版映射过来的序列，用来求逆序对
z[j] = ch[b[2][j]].col;
cout << gui_sort(1, n);
return 0;
}
—————————————————————————————————————
更简便的一种判断方法，摘自洛谷题解
所有数字可以分成两种状态，
W
和
M
W 和 M
W和M
只要有 W 的数字跑到了 M 的位置，或者反之，就可以说明无解
代码：
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define fx first
#define fy second
//#pragma GCC optimize(2)
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1000010, M = 110, MM = 3000010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int st[N << 1];
int a[N][2], b[N][2], z[N], tmp[N];
ll gui_sort(int l, int r) {
if (l >= r)return 0;//递归边界勿忘
int mid = l + r >> 1;
ll cnt = gui_sort(l, mid) + gui_sort(mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r)
{
if (z[i] <= z[j])tmp[k++] = z[i++];
else {
cnt += (ll)mid - i + 1;
tmp[k++] = z[j++];
}
}
while (i <= mid)tmp[k++] = z[i++];
while (j <= r)tmp[k++] = z[j++];
for (int i = l; i <= r; i++)z[i] = tmp[i];
return cnt;
}
int main() {
cinios;
cin >> n;
for (int i = 0; i < 2; i++)
for (int j = 1; j <= n; j++)cin >> a[j][i];//注意 j 在前，i 记录上下状态
for (int i = 0; i < 2; i++)
for (int j = 1; j <= n; j++)cin >> b[j][i];
for (int i = 1; i <= n; i++)
st[a[i][i & 1]] = i;//对原状态记录一下 M 类型在哪个列（记录W也可）
for (int i = 1; i <= n; ++i) {
if (st[b[i][i & 1]])z[i] = st[b[i][i & 1]];//顺手记录序列
//对应在 目标状态 看看这个数字是不是还是 M 类型
//若不是就无解，因为 旋转操作 不可能会让数跑到其他状态上
else {
cout << "dldsgay!!1";
return 0;
}
}
cout << gui_sort(1, n);
return 0;
}
简洁优美