暑假集训 Day1 总结

前言：

这场比赛打了 $449$ 分，感觉很开心。

E.阶乘与倍数

这道题目比较难，在比赛中只获得了 $47$ 分。

正解思路：

首先，我们要知道求出 $n!$ 中包含多少个质数 $p$，可以用一种简单的快捷的方法 $n\div p$。这就是做这道题的核心思路。但由于数据范围过大，直接枚举固然不行。所以我们可以运用二分答案的思路。我们先把 $k$ 进行分解质因数。如果二分的 $n$ 包含 $e$ 个 $p$，那么这就是一个合法的答案，用 $ans$ 对其取 $max$ 值。这里取 $max$ 值的原因是：由于答案要满足包含所有 $e$ 个 $p$，而且大的数能包含小的数，小的数不能包含大的数，所以我们要取 $max$。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k, ans = -0x3f3f3f3f;
map<int, int> mp;
bool check(int x, int p, int e) {
	int sum = 0;

	while (x >= p) {
		x /= p;
		sum += x;
	}

	return sum >= e;
}
signed main() {
	cin >> k;

	for (int i = 2; i <= k / i; i++) {
		while (k % i == 0) {
			mp[i]++;
			k /= i;
		}
	}

	if (k > 1) {
		mp[k]++;
	}

	for (auto [p, e] : mp) {
		int l = 0, r = p * e, mid;

		while (l <= r) {
			mid = (l + r) >> 1;

			if (check(mid, p, e)) {
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}

		ans = max(ans, l);
	}

	cout << ans;
	return 0;
}

F.黄金商人

由于图论没有学好，所以这道题我看都没看，直接输出的样例骗了 $2$ 分。

正解思路：

首先，看到题目描述中所说的有向无环图，可以判断这道题可以用拓扑排序。我们首先把每一个点之间建立起关系，把所有入度为 $0$ 的点存入队列做 BFS。我们定义一个 $ans$，存储答案，一个数组 $f$ 存储目前为止黄金售价最便宜的那一个价格。每到一个新的城镇，就更新 $ans$ 为当前 $ans$ 与当前城镇黄金售价减去到目前为止黄金售价的最小值的差的最大值。然后，实时更新到当前城镇时黄金售价的最小值。然后把现在入度为 $0$ 的所有城镇编号入队，进行下一步处理。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;
int n, m, ans = -0x3f3f3f3f;
vector<int> a(N + 1);
vector<int> r(N + 1, 0);
vector<int> f(N + 1, INT_MAX);
vector<vector<int>> d(N + 1);
queue<int> q;
signed main() {
	cin >> n >> m;

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

	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		r[y]++;
		d[x].push_back(y);
	}

	for (int i = 1; i <= n; i++) {
		if (r[i] == 0) {
			q.push(i);
		}
	}

	while (q.size()) {
		int u = q.front();
		q.pop();
		ans = max(ans, a[u] - f[u]);

		for (int i = 0; i < d[u].size(); i++) {
			r[d[u][i]]--;

			if (r[d[u][i]] == 0) {
				q.push(d[u][i]);
			}

			f[d[u][i]] = min(f[d[u][i]], min(f[u], a[u]));
		}
	}

	cout << ans;
	return 0;
}