2.1 vp Codeforces Round #842 (Div. 2)

A - Greatest Convex

题意

给出k，要找出最大的x(1 <= x <= k)，使x! + (x - 1)! 是k的倍数，问是否存在，为多少

思路

变换一下即可得原式为(x - 1)!(x + 1)，若要满足条件，令x = k - 1即可

void solve() {
	int n;
	cin >> n;
	cout << n -1 << endl;
}

B - Quick Sort

题意

给出长度为n个排列和k，有一个操作，可以挑选排列中任意k个数删掉，然后将它按递增的顺序加到排列末尾，问最少需要多少次可以使整个排列是递增的

思路

显然最多次数是 (n + k - 1) / k次，但是当前面数字有序的时候是可以不需要算在需要排序的数字里，所以找到第一个没有顺序的数字，然后将长度更新为它之后的数字再算即可

void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 1), p(n + 1);
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		p[a[i]] = i;
	}
	
	int ans = 0;
	
	for (int i = 1; i < n; i ++) {
		if (p[i] > p[i + 1]) {
			int x = n - i;
			ans = x / k + ((x % k == 0) ? 0 : 1);
			break;
		}
	}
	
	cout << ans << endl;
}

C - Elemental Decompress

题意

给出长度为n的序列a，问是否存在排列p, q，满足\(max(p_i, q_i) = a_i\)

思路

这题是个构造题，思路并不难，难的只是模拟
思路就是找到重复的元素，不存在的元素，和其他元素，然后重复的和不存在的元素一一配对，若可以配对成功，输出即可，否则判负，只出现了一次的元素不需要配对，就是他自己
如：
a
2 3 3 4 5
重复的元素就是3， 不存在的元素是1
其他元素就是2，4，5
所以2,4,5原样输出
不存在的元素和重复的元素一一配对
1
3
也就是1和3配对
故而p
2 3 1 4 5
q
2 1 3 4 5

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1), p(n + 1), q(n + 1);
	map<int, int> mp, re;
	set<int> se, more, little;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		mp[a[i]] ++;
		se.insert(a[i]);
		if (mp[a[i]] > 1) {
			more.insert(a[i]);
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		if (se.find(i) == se.end()) {
			little.insert(i);
		}
	}
	
	auto it = little.begin();
	for (auto t : more) {
		if (t > *it) {
			re[t] = *it;
			re[*it] = t;
			it ++;
		}else {
			cout << "NO" << endl;
			return ;
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		if (mp[a[i]] == 1) p[i] = a[i];
		else if (mp[a[i]] == 2) {
			mp[a[i]] += n;
			p[i] = a[i];
		}else if (mp[a[i]] == 2 + n){
			p[i] = re[a[i]];
		} else {
			cout << "NO" << endl;
			return ;
		}
	}
	
	for (int i = 1; i <= n; i ++) {
		if (mp[a[i]] == 1) q[i] = a[i];
		else if (mp[a[i]] == 2) {
			q[i] = a[i];
		}else if (mp[a[i]] == 2 + n){
			q[i] = re[a[i]];
			mp[a[i]] -= n;
		}else {
			cout << "NO" << endl;
			return ;
		}
	}
	
	cout << "YES" <<endl;
	for (int i = 1; i <= n; i ++) cout << p[i] << " \n"[i == n];
	for (int i = 1; i <= n; i ++) cout << q[i] << " \n"[i == n];
}

D - Lucky Permutation

题意

给出长度为n的排列，你可以进行操作：将排列中任意两个元素交换位置
问最少多少次操作可以使排列中只有一个逆序对

思路

只有一个逆序对其实就是在1 2 3 4 5 ... n的基础上相邻两个元素交换位置
这里看到一个大佬用的并查集，很有意思，原址：https://zhuanlan.zhihu.com/p/596927783
将元素和当前下标连一条边，最少需要操作数就是n - cnt（也就是连通块内部需要调整的次数），cnt是连通块的数量，当两个元素不在一个连通块里，说明我们需要额外操作一次使排列产生一个逆序，当两个元素在一个连通块里，那我们可以少进行一次操作直接满足条件
例如1 2 5 3 4
共有3个连通块 1 2 534
若在外部我们需要2次操作使534有序，也就是12345，然后再进行一次操作产生一个逆序，这是三次
而若在534内部操作，那么就可以将操作降到一次：将5，4交换，变成1 2 4 3 5

vector<int> p(N, 0);
 
int find(int x) {
	if (x != p[x]) p[x] = find(p[x]);
	return p[x];
}
 
//注意观察N的大小
void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1), st(n + 1, 0);
	for (int i = 1; i <= n; i ++) cin >> a[i];
	
	for (int i = 1; i <= n; i ++) p[i] = i;
	
	for (int i = 1; i <= n; i ++) {
		int x = find(i), y = find(a[i]);
		if (x != y) {
			p[x] = y;
		}
	}
	
	int cnt = 0;
	
	for (int i = 1; i <= n; i ++) {
		int x = find(i);
		if (!st[x]) {
			st[x] = 1;
			cnt ++;
		}
	}
	
	int ans = INF;
	
	for (int i = 1; i < n; i ++) {
		int x = find(a[i]), y = find(a[i + 1]);
		if (x != y) {
			ans = min(ans, n - cnt + 1);
		} else ans=  min(ans, n - cnt - 1);
	}
	
	cout << ans << endl;
}

总结

对于并查集有了新的认识
对于排列的变换可用并查集来维护