E. Cross Swapping (and check out deformation/good questions)

题目
参考

题意

给定一个n*n的二维矩阵.
执行操作：选择$1<=k<=n,swap(a[i][k],a[k][i]),1<=i<=n$
比如当n=4,k=3时,After conversion, it is shown on the right.

对于上述操作,We can do it any number of times,也可以是0次.
问,By doing the above several times,可以得到的字典序最小What is a two-dimensional array of .

定义二维数组aThe lexicographic order is ：
将二维数组aMaps to a one-dimensional arrayb,映射规则 b[i*n+j] = a[i][j]
二维数组a1The lexicographical order is smaller than a two-dimensional arraya2,
Currently only if they are mappedb1 , b2满足
存在$i,b1[j]==b2[j],1<=j<i;b1[i]<b2[i]$

1<=n<=1000

思路

上述操作,本质上就是将a[x][y]和a[y][x]做交换.
当前仅当k取x或y时,会影响到a[x][y]和a[y][x]是否交换.
k可以取1到n.操作k Essentially it's an exchangek行和第k列.
对于操作k,有两种选择,要么执行,要么不执行.

因此,我们发现：

• 当操作x和操作y 都执行,or when not executed,a[x][y]和a[y][x]没有做交换.
• 当操作x和操作y 一个执行,when one does not execute,a[x][y]和a[y][x]做了交换.

如下图,当前1,2After the operations are performed,a[1][2]和a[2][1]没有交换;而只执行1操作,a[1][2]和a[2][1]发生了交换.

After grasping the above rules,我们再研究,How to get the minimum lexicographical order.
由于是对称的,We only need to think about half of it,Here we consider all elementsa[i][j],下标i<=j的场景.

• 如果a[i][j] < a[i][j],Then do not exchange at this time,比如a[1][2] < a[2][1],This time after the exchange,The lexicographical order has instead increased.不交换,则操作iAnd the operation needs to be synchronized,要么都执行,要么都不执行.
• 如果a[i][j] > a[i][j],Then exchange at this time.交换,则操作iAnd the operation needs to be out of sync,一个执行,另一个不执行
• 此外,due to lexicographical order,is row-first,We want to row smaller elements,Swap is a priority/不交换.For example, we have studieda[1][2]Whether it needs to be exchanged after,再研究a[2][3]是否交换.因为a[1][2]ranking ratioa[2][3]高.

Get these rules,Have a related data structure come to mind–并查集.

• Treat each operation as a separate node,Initially the parent node is itself.
• The same number is required for the operation,We pull it into a collection,用union操作.
• For operations that require different signs,We also pulled it into a collection,But use positive and negative to distinguish them.
• Based on row precedence,next,We build all the operating edges one by one.
• 最终,Put the collection inside,为正的（负的）操作,去做执行,负的（正的）side does not execute.

详见代码

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1010;

int n;
int a[maxn][maxn];
int fa[maxn];

// 并查集初始化 
void init() {
    
	for (int i = 1; i <= n; ++i) {
    
		fa[i] = i;
	}
}

// 并查集查找根节点 
int find1(int u) {
    
	if (u < 0) {
    // 负号 取反 
		return -find1(-u);
	}
	if (u == fa[u]) {
    
		return u;
	}
	// Merge during query 
	return fa[u] = find1(fa[u]);
}

// 并查集 将u, vPull to the same collection 这里u, v可为负数 
void union1(int u, int v) {
    
	u = find1(u);
	v = find1(v);
	if (abs(u) == abs(v)) {
    // already in the same collection 
		return;
	}
	
	if (u < 0) {
    
		fa[-u] = -v;
	} else {
    
		fa[u] = v;
	}
}
void solve() {
    
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
    
    	for (int j = 1; j <= n; ++j) {
    
    		scanf("%d", &a[i][j]);
		}
	}
	init();
	for (int i = 1; i <= n; ++i) {
    
		for (int j = i; j <= n; ++j) {
    
			if (a[i][j] < a[j][i]) {
    // 同号 
				union1(i, j);
			} else if (a[i][j] > a[j][i]) {
    // 异号 
				union1(i, -j);
			}
		}
	}
	
	for (int i = 1; i <= n; ++i) {
    
		fa[i] = find1(i);
		if (fa[i] > 0) {
    // you can skip > 0, or skip < 0.
			continue;
		}
		for (int j = 1; j <= n; ++j) {
    
			swap(a[i][j], a[j][i]);
		}
	}
	
	for (int i = 1; i <= n; ++i) {
    
    	for (int j = 1; j < n; ++j) {
    
    		printf("%d ", a[i][j]);
		}
		printf("%d\n", a[i][n]);
	}
}

int main() {
    
    int t;
// t = 1;
    scanf("%d", &t);
    while (t--) {
    
		solve();
    }
}
/* */

最后

I think the article is good,gongzhonghao 关注下 对方正在debug,一起快乐刷题吧~