Acwing163周赛题解

A

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, l, r;

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int min_val = INF;
    cin >> n >> l >> r;

    for (int i = 1; i <= n; ++i) {
   
        int val;
        cin >> val;
        if (i >= l && i <= r) min_val = min(min_val, val);
    }

    cout << min_val << "\n";

    return 0;
}

B

奶牛之间有朋友关系, 相邻奶牛是朋友 之间隔了一个奶牛也是朋友$n\ge 5$, 给出$2n$对朋友关系, 构造可能的排列关系如果无解输出$-1$

以任意一头奶牛开始, 读入的时候将所有奶牛的朋友读入, 如果第一头奶牛的所有朋友确定, 也就是上图中$a,b,c,d$四个位置, 如果想知道下一头奶牛位置, 可以用$c$递推

对于奶牛$c$, 因为有四个朋友, 但是三个是已知的, 因此将三个已知的朋友去掉剩下一个就是下一个奶牛位置

递推的时候递推回原始位置, 如果不合法枚举下一个排列, 最开始直接枚举$1$的所有朋友

时间复杂度$O(4!\times n)$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n;
vector<int> p[N];
int path[4], res[N];
bool vis[N], used[N];

//寻找未被替代的奶牛
int get(int x, int a, int b, int c) {
   
	for (int v : p[x]) {
   
		if (v != a && v != b && v != c) return v;
	}
	return -1;
}

bool check() {
   
	res[2] = 1;
	int d[] = {
   0, 1, 3, 4};

// 将全排列位置放到0 1 3 4四个位置上
	for (int i = 0; i < 4; ++i) res[d[i]] = p[1][path[i]];

// 从第5个牛开始递推
	for (int i = 5; i < n + 5; ++i) {
   
		res[i] = get(res[i - 2], res[i - 4], res[i - 3], res[i - 1]);
		if (res[i] == -1) return false;
	}

// 检查奶牛位置和递推出奶牛位置是否一致
	for (int i = 0; i < 5; ++i) {
   
		if (res[i] != res[n + i]) return false;
	}

// 判断每一头奶牛是否有重复
	memset(used, false, sizeof used);
	for (int i = 0; i < n; ++i) {
   
		int u = res[i];
		if (used[u]) return false;
		used[u] = true;
	}

	for (int i = 0; i < n; ++i) cout << res[i] << " ";

	return true;
}

//枚举全排列
bool dfs(int u) {
   
	if (u == 4) return check();

	for (int i = 0; i < 4; ++i) {
   
		if (!vis[i]) {
   
			path[u] = i;
			vis[i] = true;
			if (dfs(u + 1)) return true;
			vis[i] = false;
		}
	}

	return false;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
// 朋友关系是双向的
	for (int i = 0; i < 2 * n; ++i) {
   
		int a, b;
		cin >> a >> b;
		p[a].push_back(b);
		p[b].push_back(a);
	}

	if (!dfs(0)) cout << -1 << "\n";
	return 0;
}

*并查集处理染色问题

3115. 疯狂的馒头
该问题的性质

• 如果正着枚举, 那么任意阶段的每个馒头颜色是无法确定的, 因为下一个阶段会被染色为新的颜色
• 但是如果倒着枚举, 如果当前馒头已经被染上色, 那么颜色就是固定的了, 也就是最后一次染色的颜色

因此从后往前枚举, 同时记录每个馒头被染上的颜色

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m, p, q;
int fa[N], color[N];

int find(int u) {
   
	if (fa[u] != u) fa[u] = find(fa[u]);
	return fa[u];
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m >> p >> q;
	for (int i = 1; i <= n + 1; ++i) fa[i] = i;

	for (int i = m; i; --i) {
   
		int u = (i * p + q) % n + 1;
		int v = (i * q + p) % n + 1;

		int l = min(u, v);
		int r = max(u, v);

// 找到第一个未染色的位置
		int idx = find(l);
		while (idx <= r) {
   
			color[idx] = i;
			fa[idx] = find(idx + 1);
			idx = find(idx);
		}
	}

	for (int i = 1; i <= n; ++i) cout << color[i] << "\n";
	return 0;
}

C

一共$m$轮, $x_i$为胜者, 输出每个奶牛被谁击败

并查集处理染色问题

初始的时候节点指向自己表示未被淘汰, 如果淘汰一个奶牛, 那就将该位置指向下一个位置, 操作过程中指向自己的未被淘汰, 非指向自己的都被淘汰

在$[L,R]$找到哪些节点未被淘汰

因为最终有一个优胜者, 因此只要删除$[L,X-1]$和$[X+1,R]$

执行路径压缩, 找到祖宗节点, 如果该位置在$[L,R]$范围内, 将其删除$fa$节点指向下一个元素, 一个点被删除后因为会路径压缩, 不会重复找, 每个节点只会被考虑一次, 因此时间复杂度是$O(n)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 3e5 + 10;

int n, m;
int fa[N], res[N];

int find(int u) {
   
	if (fa[u] != u) fa[u] = find(fa[u]);
	return fa[u];
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i <= n + 1; ++i) fa[i] = i;

	while (m--) {
   
		int l, r, x;
		cin >> l >> r >> x;
// 将区间分为两段
		for (int i = l; i < x;) {
   
			i = find(i);
			if (i < x) {
   
				fa[i] = i + 1;
				res[i] = x;
			}
		}

		for (int i = x + 1; i <= r; ++i) {
   
			i = find(i);
			if (i >= x + 1 && i <= r) {
   
				fa[i] = i + 1;
				res[i] = x;
			}
		}
	}

	for (int i = 1; i <= n; ++i) cout << res[i] << " ";
	cout << "\n";
	return 0;
}