Codeforces Global Round 9

https://codeforces.com/contest/1375

真的吐了，全都是构造

C. Element Extermination

 

题意：给定一个n的排列，每次操作选择 $a[i]<a[i+1]$ 的数对并删去其中任一个，问能否最终数列只剩一个数。

构造

结论：若 $a[1]<a[n]$ 则可以，否则不行。

若 $a[1]<a[n]$，则先把 $a[2]\cdots a[n]$，任意贪心地删，最终一定递减，再用 $a[1]$ 贪心删其它数，再用 $a[n]$ 贪心删其它数，最终一定能删到只剩 $a[1],a[n]$，这两个数再删去任意一个。

若 $a[1]>a[n]$，可以发现对于满足条件的 $a[i]$，删完后 $a[i]$ 要么保留，要么变成 $a[i+1]$，也就更大了，所以 $a[1]$ 只会变得越来越大，而 $a[n]$ 越来越小，所以最终 $a[1]$ 必定还是 大于 $a[n]$，则无法删完。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int T;
int n;
int a[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
		if (a[1] < a[n])puts("YES");
		else puts("NO");
	}
	return 0;
}

 

D. Replace by MEX

 

题意：给定一个长度n的数列，每个数在 0 到 n，每次操作选择一个数变成当前数列的MEX值，问多少次操作后使得数列非递减，要求操作数小于等于2n。

构造

考虑构造出 $\{0,1,2,\cdots,n-1\}$。

要逐步确定下每一位，但不一定按照顺序。

先求出MEX，如果MEX=n，则随便选择一位没有确定的进行操作；否则选择第MEX位，这样第MEX位就确定下来了。确定了之后它就不会再成为MEX了，所以每一位最多被操作两次：作为n或者MEX。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int T;
int n;
int a[1010], cnt[1010];
vector<int>ans;
int mex() {
	for (int i = 0; i <= n; i++)if (!cnt[i])return i;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		fill(cnt, cnt + n + 1, 0);
		ans.clear();
		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
			cnt[a[i]]++;
		}
		while (1) {
			int mx = mex(), p;
			for (p = 0; a[p] == p && p < n; p++);
			if (p >= n)break;
			if (mx == n) {
				cnt[a[p]]--;
				cnt[mx]++;
				ans.push_back(p + 1);
				a[p] = mx;
			}
			else {
				cnt[a[mx]]--;
				cnt[mx]++;
				a[mx] = mx;
				ans.push_back(mx + 1);
			}
		}
		printf("%d\n", (int)ans.size());
		for (int u : ans)printf("%d ", u);
		puts("");
	}
	return 0;
}

 

E. Inversion SwapSort

 

题意：给定一个数列，要求先找出所有的逆序对，再排序，使得按照顺序翻转每一对位置后数列变为非递减。

构造

假设该数列是一个排列，则最终在第n个位置要放n，假设现在第n个位置上是 $x$，每个数值所在的位置设为 $pos[i]$，则按照 $(n,pos[x+1]),(n,pos[x+2]),\cdots,(n,pos[n])$ 的顺序排列这些逆序对，最终一定可以使得 n 放到第 n 个位置上，且这中间的所有位置对都是逆序对。第 n 位放好之后，一定不会再有涉及到第 n 位的逆序对了，所以再用这种方法处理前面每一位即可。

而如果给定数列不是一个排列，则可以通过重新分配数字映射到一个排列，再使用以上方法处理。

对于大小不同的数字，直接按照大小关系映射；对于大小相同的，排在后面的更大，这样不会改变逆序对个数。

映射完之后直接在得到的排列上解决。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n;
int a[N], b[N], p[N];
typedef pair<int, int>pii;
vector<pii>vc;
bool cmp(int i, int j) {
	return a[i] == a[j] ? i < j : a[i] < a[j];
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	iota(b + 1, b + n + 1, 1);
	sort(b + 1, b + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		a[b[i]] = i;
		p[a[b[i]]] = b[i];
	}
	for (int i = n; i >= 1; i--) {
		for (int j = a[i] + 1; j <= i; j++) {
			vc.push_back(pii(p[j], i));
			swap(a[p[j]], a[i]);
			p[a[p[j]]] = p[j];
			p[j] = i;
		}
	}
	printf("%d\n", (int)vc.size());
	for (pii p : vc)printf("%d %d\n", p.first, p.second);
	return 0;
}

 

F. Integer Game

 

题意：交互题。两个人博弈，初始给定三个不同的正数数a，b，c，每轮要求先手任选一个正数 y，后手把 y 加到三个数中任一个，且上一轮加过的数不能再加，如果后手加完使得两个数相等了，则后手输；过了1000轮则先手输。

博弈

结论：先手必胜，且最多3轮。

设三个数从小到大依次 $p,q,r$，先手给出 $2r-p-q$，后手若加在 $p$ 上，则变为 $2r-q,q,r$，先手再给出 $r-q$，由于第一个数不能再选，所以后手没法操作。

若后手加在 $q$ 上，则类似。

若后手加在 $r$ 上，由于 $2r-p-q$ 为正数，所以大小关系不变，再重复上面的策略即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
ll a[4], x, b[4];
int main() {
	scanf("%d%d%d", &a[1], &a[2], &a[3]);
	for (int i = 1; i <= 3; i++)b[i] = a[i];
	sort(b + 1, b + 4);
	cout << "First" << endl;
	ll tmp = 2 * b[3] - b[1] - b[2];
	cout << tmp << endl;
	cin >> x;
	if (a[x] == b[3]) {
		b[3] += tmp;
		tmp = 2 * b[3] - b[1] - b[2];
		cout << tmp << endl;
		cin >> x;
		for (int i = 1; i <= 2; i++)if (b[i] != a[x])tmp = b[i];
		cout << b[3] - tmp << endl;
		cin >> x;
	}
	else {
		for (int i = 1; i <= 2; i++)if (b[i] != a[x])tmp = b[i];
		cout << b[3] - tmp << endl;
		cin >> x;
	}
	return 0;
}