ABC392题解_牛客博客

A

算法标签: 模拟

在这里插入图片描述

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

using namespace std;

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

	int w[3];
	for (int i = 0; i < 3; ++i) cin >> w[i];

	sort(w, w + 3);
	if (w[0] * w[1] == w[2]) cout << "Yes" << "\n";
	else cout << "No";
	
	return 0;
}

B

算法标签: 哈希表

在这里插入图片描述

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

using namespace std;

const int N = 1010;

int range, n, w[N];

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

	unordered_set<int> s;
	cin >> range >> n;
	for (int i = 0; i < n; ++i) {
   
		int val;
		cin >> val;
		s.insert(val);
	}

	vector<int> res;
	for (int i = 1; i <= range; ++i) {
   
		if (!s.count(i)) res.push_back(i);
	}
	
	cout << res.size() << "\n";
	for (int val : res) cout << val << " ";
	cout << "\n";

	return 0;
}

C

算法标签: 模拟

在这里插入图片描述

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

using namespace std;

const int N = 3e5 + 10;

int n;
int p[N], q[N];
int pos[N];

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

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	for (int i = 1; i <= n; ++i) {
   
		cin >> q[i];
		pos[q[i]] = i;
	}

	for (int i = 1; i <= n; ++i) {
   
		int per = pos[i];
		int see = p[per];
		cout << q[see] << " ";
	}
	cout << "\n";

	return 0;
}

D

算法标签: 桶计数, 模拟

在这里插入图片描述

*精度不够的错误案例

而且没说两个骰子只有一个点数相等, 下面做法有遗漏情况

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

using namespace std;

const int N = 110, M = 1e5 + 10;
const double EPS = 1e-20;

int n;
int cnt[N];
// 记录每个骰子 每个数字出现的概率
double w[N][M];

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

	cin >> n;
	for (int i = 1; i <= n; ++i) {
   
		cin >> cnt[i];
		for (int j = 1; j <= cnt[i]; ++j) {
   
			int val;
			cin >> val;
			w[i][val] += 1.0 / cnt[i];
		}
	}

	// 枚举点数
	double res = 0;
	for (int i = 1; i < M; ++i) {
   
		vector<double> nums;
		for (int j = 1; j <= n; ++j) {
   
			if (w[j][i] > EPS) nums.push_back(w[j][i]);
		}

		sort(nums.begin(), nums.end(), greater<double>());
		if (nums.size() < 2) continue;
		double tmp = nums[0] * nums[1];
		res = max(res, tmp);
	}

	printf("%lf\n", res);
	return 0;
}

正确解法

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

using namespace std;

typedef long double LD;
const int N = 110, M = 1e5 + 10;
const double EPS = 1e-20;

int n;
int cnt[N];
int w[N][M];

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

	cin >> n;
	for (int i = 1; i <= n; ++i) {
   
		cin >> cnt[i];
		for (int j = 1; j <= cnt[i]; ++j) {
   
			int val;
			cin >> val;
			w[i][val]++;
		}
	}

	LD res = 0;
	for (int i = 1; i < n; ++i) {
   
		for (int j = i + 1; j <= n; ++j) {
   
			LD curr = 0;
			for (int k = 1; k < M; ++k) {
   
				curr +=( (LD) w[i][k] / cnt[i]) * ((LD) w[j][k] / cnt[j]);
			}
			res = max(res, curr);
		}
	}

	printf("%.15Lf\n", res);
	return 0;
}

E

算法标签: $D S U$ , 并查集

在这里插入图片描述

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

using namespace std;

typedef pair<int, int> PII;
const int N = 2e5 + 10, M = 4e5 + 10;

int n, m;
int p[N];
int vers[M];
bool vis[M];

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

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

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

	for (int i = 1; i <= m; ++i) {
   
		int u, v;
		cin >> u >> v;
		int fa1 = find(u);
		int fa2 = find(v);
		if (fa1 != fa2) p[fa2] = fa1;
		else {
   
			vis[i] = true;
			vers[i] = u;
		}
	}

	int res = 0;
	for (int i = 1; i <= n; ++i) {
   
		if (p[i] == i) res++;
	}

	cout << res - 1 << "\n";

	int k = 1;
	for (int i = 1; i <= n; ++i) {
   
		if (!vis[i]) continue;
		while (k <= n && find(k) == find(vers[i])) k++;
		if (k > n) break;
		int fa1 = find(k);
		int fa2 = find(vers[i]);
		p[fa1] = fa2;
		cout << i << " " << vers[i] << " " << k << "\n";
	}

	return 0;
}

F

算法标签: 树状数组, $F e n w i c k - T ree$ , $BST$

在这里插入图片描述

思路

如果正着做, 插入不好操作, 平衡树操作, 如果倒着做, 插入第 $n$ 个数, 所在位置 $p_{n - 1}$ , 初始化树状数组每个位置 $1$ , 如果这个位置被占用将其改为 $0$ , 寻找从左往右的第 $p_{n - 1}$ 个空格, 也就是找 $p_{n - 1}$ 就是找前缀和等于 $p_{n - 1}$ 的位置, 时间复杂度 $O(n\log ^ 2n)$

树状数组写法

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

using namespace std;

const int N = 5e5 + 10;

int n, w[N];
int tr[N], res[N];

int lowbit(int val) {
   
	return val & -val;
}

void add(int u, int val) {
   
	for (int i = u; i <= n; i += lowbit(i)) tr[i] += val;
}

int query(int u) {
   
	int res = 0;
	for (int i = u; i; i -= lowbit(i)) res += tr[i];
	return res;
}

int find(int val) {
   
	int l = 1, r = n;

	while (l < r) {
   
		int mid = l + r >> 1;
		if (query(mid) >= val) r = mid;
		else l = mid + 1;
	}

	return l;
}

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

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> w[i];
	for (int i = 1; i <= n; ++i) add(i, 1);

	for (int i = n; i >= 1; --i) {
   
		int pos = find(w[i]);
		res[pos] = i;
		add(pos, -1);
	}

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

	return 0;
}

线段树写法

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

using namespace std;

const int N = 5e5 + 10;

int n, w[N];
struct Node {
   
	int l, r;
	int sum;
} tr[N << 2];
int res[N];

void push_up(int u) {
   
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r) {
   
	if (l == r) {
   
		tr[u] = {
   l, r, 1};
		return;
	}

	tr[u] = {
   l, r};
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	push_up(u);
}

void update(int u, int pos, int val) {
   
	if (tr[u].l == tr[u].r) {
   
		tr[u].sum += val;
		return;
	}

	int mid = tr[u].l + tr[u].r >> 1;
	if (pos <= mid) update(u << 1, pos, val);
	if (pos > mid) update(u << 1 | 1, pos, val);
	push_up(u);
}

// 查询和为val的起始位置
int query(int u, int k) {
   
	if (tr[u].l == tr[u].r) return tr[u].l;

	if (tr[u << 1].sum < k) return query(u << 1 | 1, k - tr[u << 1].sum);
	else return query(u << 1, k);
}

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

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> w[i];
	build(1, 1, n);

	for (int i = n; i >= 1; --i) {
   
		// 找到第w[i]个未被赋值的位置
		int pos = query(1, w[i]);
		res[pos] = i;
		update(1, pos, -1);
	}

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

	return 0;
}

G

算法标签: $FFT$ , $NTT$ , 卷积

在这里插入图片描述

ABC392题解

A

算法标签: 模拟

B

算法标签: 哈希表

C

算法标签: 模拟

D

算法标签: 桶计数, 模拟

*精度不够的错误案例

正确解法

E

算法标签: DSUDSUDSU, 并查集

F

算法标签: 树状数组, Fenwick−TreeFenwick-TreeFenwick−Tree, BSTBSTBST

思路

树状数组写法

线段树写法

G

算法标签: FFTFFTFFT, NTTNTTNTT, 卷积

思路

算法标签: $D S U$ , 并查集

算法标签: 树状数组, $F e n w i c k - T ree$ , $BST$

算法标签: $FFT$ , $NTT$ , 卷积