AtCoder Beginner Contest 383

C - Humidifier 3

Description

一个 $h\times w$ 的网格，每个格子可能是墙、空地或者城堡。
一个格子是好的，当且仅当从至少一个城堡出发，走不超过 $d$ 步能到达。（只能上下左右走，不能穿墙），求好格子的数量。

Solution

从每一个城堡出发进行 bfs，对所有 d 步内能走到的点进行标记。
为了效率，可以把所有城堡丢入队列中，一次搜完。

Code

// Problem: C - Humidifier 3
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int h, w, d;cin >> h >> w >> d;vector<string> a(h);for (int i = 0; i < h; i++) {cin >> a[i];}queue<tuple<int, int, int>> que;vector visit(h, vector<bool>(w, false));auto check = [&](int x, int y) {return x >= 0 && x < h && y >= 0 && y < w && a[x][y] != '#' && !visit[x][y];};auto enque = [&](int x, int y, int step) {if (check(x, y)) {que.emplace(x, y, step);visit[x][y] = true;}};for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {if (a[i][j] == 'H') {enque(i, j, 0);}}}while (!que.empty()) {auto [x, y, step] = que.front();que.pop();if (step >= d) continue;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];enque(nx, ny, step + 1);}}int ans = 0;for (int i = 0; i < h; i++) {ans += accumulate(visit[i].begin(), visit[i].end(), 0);}cout << ans;return 0;
}

D - 9 Divisors

Description

给定 $n$，求 $[1,n]$ 中正好有 $9$ 个因数的数的数量。
$1\le n\le 10^{12}$

Solution

由因数个数定理知，满足条件的数 $t$只有两种可能：

1. $t=p^8$
2. $t=p_1^2\times p_2^2$

显然 $p$ 一定 $\le \sqrt{n}$，所以只需筛出 $\sqrt{n}$ 内的质数即可。
显然答案远小于 $\sqrt{n}$ （看大样例也知道），因此枚举即可。
注意及时跳出循环（特别是情况2，否则会 TLE）

Code

// Problem: D - 9 Divisors
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);i64 n;cin >> n;vector<bool> isp;vector<int> primes;auto sieve = [&](int n) {isp.assign(n + 1, true);primes.clear();isp[0] = isp[1] = false;for (int i = 2; i <= n; i++) {if (isp[i]) {primes.push_back(i);for (int j = i + i; j <= n; j += i) {isp[j] = false;}}}};int m = sqrt(n);sieve(m);int ans = 0;for (auto p : primes) {if (1LL * p * p * p * p <= m) {ans++;}else {break;}}for (int i = 0; i < primes.size(); i++) {for (int j = i + 1; j < primes.size() && 1LL * primes[i] * primes[j] <= m; j++) {ans++;}}cout << ans;return 0;
}

E - Sum of Max Matching

Description

定义 $f(s,t)$ 为 $s,t$ 间的最小瓶颈路。（路径上最大边权的最小值）。
给定 $n$ 点 $m$ 边的无向图和两个序列 $a=(a_1,a_2,\cdots ,a_k)$，$b=(b_1,b_2,\cdots ,b_k)$，重排 $b$ 使得 $\sum _{i=1}^{k}f(a_i,b_i)$ 最小。

Solution

关于最小瓶颈路，有一个结论：两点间的最小瓶颈路，就是最小生成树上两点间的最大边权。

据此，可以得到一个思路：
首先将每个点 $u$ 看成一个集合，其中有 $cnt{a}_u$ 个红点和 $cnt{b}_u$ 个蓝点。
然后仿照最小生成树的做法，在合并集合时，将红蓝点对配对消去，答案加上消去的点对数 $\times w$。
由上面结论可知，这个方法是正确的。

Code

// Problem: E - Sum of Max Matching
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_e
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m, k;cin >> n >> m >> k;vector<array<int, 3>> edges(m);for (auto &[u, v, w] : edges) {cin >> u >> v >> w;u--, v--;}sort(edges.begin(), edges.end(), [](const array<int, 3> &a, const array<int, 3> &b) {return a[2] < b[2];});vector<int> ca(n), cb(n);for (int i = 0, x; i < k; i++) {cin >> x;x--;ca[x]++;}for (int i = 0, x; i < k; i++) {cin >> x;x--;cb[x]++;}vector<int> p(n);iota(p.begin(), p.end(), 0);auto find = [&](auto &&self, int x) -> int {if (x != p[x]) p[x] = self(self, p[x]);return p[x];};i64 ans = 0;for (auto [u, v, w] : edges) {int x = find(find, u), y = find(find, v);if (x == y) {continue;}ca[x] += ca[y];cb[x] += cb[y];int t = min(ca[x], cb[x]);ans += 1LL * t * w;ca[x] -= t;cb[x] -= t;p[y] = x;}cout << ans;return 0;
}

F - Diversity

Description

有 $n$ 个物品，第 $i$ 个的价格为 $p_i$，价值为 $u_i$，颜色为 $c_i$。
定义一种选择的价值为 $\sum u+t\times k$，其中 $t$ 是所选物品的不同颜色种类数，$k$ 为给定常数。
你需要选择一些物品（可以不选），在所选物品总价格不超过 $x$ 的前提下，求最大价值。

Solution

容易看出是 0-1背包 的变式，首先按颜色对物品分组。
设 $d{p}_{i,j}$ 为考虑前 $i$ 种颜色，总价格在 $j$ 以内的最大价值。
对于第 $i$ 个颜色，额外考虑从上一个颜色，即 $d{p}_{i-1,j-p}+u+k$ 转移过来即可。
注意要跳过不存在的颜色。

Code

滚掉了第一维。

// Problem: F - Diversity
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2024（AtCoder Beginner Contest 383）
// URL: https://atcoder.jp/contests/abc383/tasks/abc383_f
// Memory Limit: 1024 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}const i64 inf = 1e18;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, v, k;cin >> n >> v >> k;vector<vector<pair<int, int>>> adj(n);for (int i = 0, p, u, c; i < n; i++) {cin >> p >> u >> c;c--;adj[c].emplace_back(p, u);}vector<i64> dp(v + 1, -inf);dp[0] = 0;for (int c = 0; c < n; c++) {if (adj[c].empty()) {continue;}vector<i64> dp2 = dp;for (auto [p, u] : adj[c]) {for (int i = v; i >= p; i--) {dp2[i] = max({dp2[i], dp2[i - p] + u, dp[i - p] + u + k});}}dp.swap(dp2);}cout << *max_element(dp.begin(), dp.end());return 0;
}