Codeforces Round (2021-03-21)

Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)

A. Prison Break

题意

一个 $a\times b$ 的监狱被墙分成 $ab$ 个格子，外边也有墙。问最少打通多少面墙，才能让任意一个格子里的人都能走到外面。

思路

把外面也看成一个点，一共 $ab+1$ 个点，连通它们至少需要 $ab$ 条边。反过来，把所有格子连成一棵树，再打通一面外墙，正好也是 $ab$ 面墙。答案直接是 $ab$ 。

代码

#include <cstdio>
#include <iostream>
using namespace std;
int a, b;

int main() {
	int t;
	cin >> t;
	while(t--) {
		cin >> a >> b;
		cout << a * b << endl;
	}
	return 0;
}

B. Restore Modulo

题目链接

题意

给一个数组，要求找出 $m,c$ ，让 $a_{i+1}=(a_i+c)\bmod m$ ，并让 $m$ 尽量大。无解输出 -1， $m$ 可以任意大就输出 0，否则输出 $m,c$ 。

思路

每一步只有两种差值：没绕回去时是 $c$ ，绕回去时是 $c-m$ 。所以只要既有上升又有下降，就能用一次上升确定 $c$ ，再用一次下降确定 $m$ ，最后把整个数组代回去检查。

如果所有差值都相同， $m$ 就能任意大，下降的等差数列也一样。如果出现相邻相等，就只能是 $c=0$ ，这时整个数组都得相等。

代码

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 1e5 + 17;
int T, c, m, n, a[maxn];

int main() {
	cin >> T;
	while(T--) {
		cin >> n; for(int i = 1; i <= n; i++) cin >> a[i];
		if(a[1] == a[2]) {
			int flg = 1;
			for(int i = 2; i <= n; i++) if(a[i - 1] != a[i]) flg = 0;
			if(flg) cout << 0 << endl;
			else cout << -1 << endl;
			continue;
		}
		else if(a[1] < a[2]) {
			int flg = 1;
			c = a[2] - a[1];
			m = 0;
			for(int i = 1; i < n; i++) {
				if(a[i + 1] < a[i]) {
					m = a[i] + c - a[i + 1];
					break;
				}
			}
			if(m == 0) {
				for(int i = 1; i < n; i++) {
					if(a[i + 1] != (a[i] + c) ) flg = 0;
				}
				if(flg) cout << 0 << endl;
				else cout << -1 << endl;
				continue;
			}
			for(int i = 1; i < n; i++) {
				if(a[i] >= m || a[i + 1] >= m) flg = 0;
				if(a[i + 1] != (a[i] + c) % m) flg = 0;
			}
			if(flg) cout << m << " " << c << endl;
			else cout << -1 << endl;
			continue;
		}
		else {
			int flg = 1;
			c = 0;
			for(int i = 1; i < n; i++) {
				if(a[i + 1] > a[i]) c = a[i + 1] - a[i];
			}
			if(c == 0) {
				c = a[2] - a[1];
				for(int i = 1; i < n; i++) {
					if(a[i + 1] != (a[i] + c) ) flg = 0;
				}
				if(flg) cout << 0 << endl;
				else cout << -1 << endl;
				continue;
			}
			m = a[1] - a[2] + c;
			for(int i = 1; i < n; i++) {
				if(a[i] >= m || a[i + 1] >= m) flg = 0;
				if(a[i + 1] != (a[i] + c) % m) flg = 0;
			}
			if(flg) cout << m << " " << c << endl;
			else cout << -1 << endl;
			continue;
		}
	}
	return 0;
}

C. Basic Diplomacy

题目链接

题意

有 $m$ 天，每天给出可以一起玩游戏的朋友列表，要从中选一个人。每个人最多被选 $\lceil m/2\rceil$ 次，问能不能安排出来，并输出一种方案。

思路

先处理选择少的日子，只有一个候选人的就只能选他。每个人的额度设成出现次数和 $\lceil m/2\rceil$ 的较小值，每天在候选里挑剩余额度最多的。

处理完只有一个选择的日子，后面每天至少有两个候选。某个人在还有出场机会时额度用完，说明他已经被选满 $\lceil m/2\rceil$ 次；要让两个候选都用满，至少已经安排了 $2\lceil m/2\rceil\ge m$ 天，和当前还没安排完矛盾。所以只要前面的必选情况没超额，后面就一定能继续选。

代码

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 1e5 + 17;

struct day {
	int s, id;
	vector<int> v;
} d[maxn];
int T, n, m, c[maxn], p, ans[maxn];

bool cmp(day A, day B) {
	return A.s < B.s;
}

bool ccmp(int A, int B) {
	// cout << A << " " << B << endl;
	return c[A] > c[B];
}

int main() {
	cin >> T;
	while(T--) {
		cin >> n >> m;
		for(int i = 1; i <= m; i++) {
			cin >> d[i].s;
			d[i].id = i;
			for(int j = 0; j < d[i].s; j++) {
				int tmp; cin >> tmp;
				d[i].v.push_back(tmp);
				c[tmp]++;
			}
		}
		for(int i = 1; i <= n; i++) c[i] = min(c[i], (m + 1) / 2);
		sort(d + 1, d + 1 + m, cmp);
		int flg = 1;
		for(int i = 1; i <= m; i++) {
			p = i;
			if(d[i].v.empty()) {
				flg = 0;
				break;
			}
			// cout << d[i].id << endl;
			// cout << c[d[p].v[0]] << " " << c[d[p].v[1]] << endl;
			sort(d[i].v.begin(), d[i].v.end(), ccmp);
			// cout << "wan" << endl;
			if(c[d[p].v[0]] == 0) {
				flg = 0;
				break;
			}
			else {
				c[d[p].v[0]]--;
				ans[d[i].id] = d[p].v[0];
			}
		}
		puts(flg ? "YES" : "NO");
		if(flg) for(int i = 1; i <= m; i++) printf("%d%c", ans[i], " \n"[i == m]);

		for(int i = 1; i <= n; i++) c[i] = 0;
		for(int i = 1; i <= m; i++) {
			ans[i] = 0;
			d[i].v.clear();
		}
	}

	return 0;
}

D. Playlist

题目链接

题意

按环形顺序播放歌曲，最近听到的两首歌的编号值互质，就删掉后听的那首。删除以后忘掉之前的播放记录，从下一首重新开始，不能紧接着再删。输出被删除的歌曲和删除顺序。

思路

用双向链表维护还在的歌，再把相邻不互质、暂时不会触发删除的一段合起来，用并查集记住这段的结尾。走进段内就直接跳到段尾，只在边界上判断删除。

删掉一首后，把前后重新接上；如果新的相邻两首不互质，就把两段合并。删除后还要先听一首才能重新比较，这里用 fst 记一下。

开始先把相邻不互质的边合并，再从互质的边标出每段两端，跨过 1 号位置也一样处理。整圈都不互质时，一首都删不了，直接输出 0。

代码

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 1e5 + 17;
int T, n, a[maxn];
int pre[maxn], nxt[maxn];
int hd[maxn], ed[maxn];
int fa[maxn];
vector<int> ans;

int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}

int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}

int main() {
	cin >> T;
	while(T--) {
		ans.clear();
		cin >> n; for(int i = 1; i <= n; i++) cin >> a[i];
		if(n == 1 && a[1] != 1) {
			cout << 0 << endl;
			continue;
		}
		for(int i = 1; i <= n; i++) fa[i] = i;
		pre[1] = n; for(int i = 2; i <= n; i++) pre[i] = i - 1;
		for(int i = 1; i < n; i++) nxt[i] = i + 1;
		nxt[n] = 1;
		int flg = 0;
		for(int i = 1; i <= n; i++) {
			if(gcd(a[i], a[nxt[i]]) > 1) fa[getf(nxt[i])] = getf(i);
			else flg = 1;
		}
		if(!flg) {
			cout << 0 << endl;
			continue;
		}
		for(int i = 1; i <= n; i++) {
			if(gcd(a[i], a[nxt[i]]) == 1) {
				ed[getf(i)] = i;
				hd[getf(nxt[i])] = nxt[i];
			}
		}

		for(int p = 1, fst = 1; 1;) {
			if(fst) {
				fst = 0;
				p = nxt[p];
				continue;
			}
			if(pre[p] == ed[getf(pre[p])]) {
				nxt[pre[p]] = nxt[p];
				pre[nxt[p]] = pre[p];
				ans.push_back(p);
				fst = 1;
				if(gcd(a[pre[p]], a[nxt[p]]) > 1) {
					int fn = getf(nxt[p]), fp = getf(pre[p]);
					if(fn == fp) {
						break;
					}
					else{
						fa[fn] = fp;
						ed[fp] = ed[fn];
					}
				}
			}
			else p = ed[getf(p)];

			if(nxt[p] != p) p = nxt[p];
			else break;
		}
		int cnt = ans.size();
		cout << cnt << " ";
		for(int i = 0; i < cnt; i++) cout << ans[i] << " \n"[i == cnt - 1];
	}

	return 0;
}

A. Prison Break

题意

思路

代码

B. Restore Modulo

题意

思路

代码

C. Basic Diplomacy

题意

思路

代码

D. Playlist

题意

思路

代码

Random Posts