ABC383(A-F)
A - Humidifier 1¶
题目大意
有一个加湿器，\(t = 0\) 时刻，里面没有水。你会在其中加入 \(N\) 次水，每一次加水用两个数字 \(T_i\) 和 \(V_i\) 描述，表示你在 \(t = T_i\) 时刻加了 \(V_i\) 单位的水。当加湿器有水的时候，每隔 \(1\) 单位时间就会消耗 \(1\) 单位的水；如果加湿器没有水，则不会消耗水。
问：在你第 \(N\) 次加完水之后，加湿器里面还有多少单位的水？
参考代码
#include <iostream>
using namespace std;
int main()
{
int last = 0, now = 0;
int n = 0;
cin >> n;
while(n--)
{
int t, v;
cin >> t >> v;
int d = t - last;
now = max(0, now - d);
now += v;
last = t;
}
cout << now << endl;
return 0;
}
B - Humidifier 2¶
题目大意
有一个 \(H \times W(1 \le H,W \le 10)\) 的网格，每个网格如果是 # 表示是桌子，如果是 . 表示是地板。你可以挑选两个地板的位置，在上面各放置一个加湿器。
对于网格中的位置 \((i, j)\)，如果 \((i, j)\) 是地板且距离任意一个加湿器的曼哈顿距离小于等于 \(D\)，则称这个位置是“湿润的地板”。（注：加湿器所在的位置也视为湿润的地板）
问：有多少个湿润的地板？
解题思路
\((1 \le H,W \le 10)\) , 至多有 \(HW \le 100\) 个地板，记录下所有的地板位置，直接开两重循环枚举放置加湿器，然后枚举所有的地板统计是否潮湿即可，时间复杂度 \(O(H^3W^3)\)
参考代码
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main()
{
int h, w, d;
cin >> h >> w >> d;
vector<pair<int, int>> floor;
for (int i = 0; i < h; i++)
{
string s;
cin >> s;
for (int j = 0; j < w; j++)
if (s[j] == '.')
floor.push_back({i, j});
}
int ans = 0;
int len = floor.size();
auto dis = [](int r1, int c1, int r2, int c2) -> int
{ return abs(r1 - r2) + abs(c1 - c2); };
for (int i = 0; i < len; i++)
{
auto [r1, c1] = floor[i];
for (int j = i + 1; j < len; j++)
{
auto [r2, c2] = floor[j];
int cnt = 0;
for (int k = 0; k < len; k++)
{
auto [r3, c3] = floor[k];
if (dis(r1, c1, r3, c3) <= d || dis(r2, c2, r3, c3) <= d)
cnt++;
}
ans = max(ans, cnt);
}
}
cout << ans << endl;
return 0;
}
C - Humidifier 3¶
题目大意
有一个 \(H \times W(1 \le H,W \le 1000)\) 的网格，每个网格如果是 # 表示是墙，如果是 . 表示是地板，如果是 H 表示是加湿器。所有加湿器的扩散能力都是 \(D\)。
对于网格中的位置 \((i, j)\)，满足以下条件可被称为“湿润的地板”：
- \((i, j)\) 是地板。
- 从 \((i, j)\) 位置出发，每一步可以走上下左右，在不经过墙的情况下，至多走 \(D\) 步能到达任意一个加湿器。
特别的，加湿器所在的位置一定视为湿润的地板。
问：有多少个湿润的地板？
解题思路
从所有的加湿器开始 bfs 即可。
参考代码
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};
int main()
{
int h, w, d;
cin >> h >> w >> d;
vector<string> g(h);
queue<pair<int, int>> q;
vector<vector<int>> dis(h, vector<int>(w, numeric_limits<int>::max()));
int ans = 0;
for (int r = 0; r < h; r++)
{
cin >> g[r];
for (int c = 0; c < w; c++)
if (g[r][c] == 'H')
{
dis[r][c] = 0;
q.push({r, c});
ans++;
}
}
auto in_graph = [h, w](int r, int c) -> bool
{ return r >= 0 && r < h && c >= 0 && c < w; };
while (!q.empty())
{
auto [r, c] = q.front();
q.pop();
int now = dis[r][c];
if(now == d)
break;
for (int i = 0; i < 4; i++)
{
int nr = r + dr[i];
int nc = c + dc[i];
if (in_graph(nr, nc) && g[nr][nc] != '#' && now + 1 < dis[nr][nc])
{
dis[nr][nc] = now + 1;
q.push({nr, nc});
ans++;
}
}
}
cout << ans << endl;
return 0;
}
D - 9 Divisors¶
题目大意
给你一个数字 \(N(1 \le N \le 4 \times 10 ^ {12})\)，问：有多少个小于等于 \(N\) 的正整数恰好只有 \(9\) 个因数？
解题思路
根据算数基本定理，\(9 = 1 \times 9 = 3 \times 3\)，因此 \(9\) 个因数一定是 \(p^8\) 或者 \(p_1^2p_2^2\) 的形式，把所有素数筛出来就好。
参考代码
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
LL n;
cin >> n;
auto get_prime = [](LL n) -> vector<LL>
{
vector<LL> prime;
vector<bool> isp(n+1, true);
for(int i = 2; i <= n; i++)
{
if(isp[i])
prime.push_back(i);
for(auto p : prime)
{
if(i * p > n)
break;
isp[i * p] = false;
if(i % p == 0)
break;
}
}
return prime;
};
vector<LL> prime = get_prime(sqrt(n / 4));
LL ans = 0;
for(auto p : prime)
{
if(pow(p, 8) > n)
break;
ans++;
}
int len = prime.size();
for(int l = 0, r = len - 1; l < r; l++)
{
LL x = prime[l], y = prime[r];
while(l < r && x * x * y * y > n)
y = prime[--r];
ans += r - l;
}
cout << ans << endl;
return 0;
}
E - Sum of Max Matching¶
题目大意
给你一个 \(N(2 \le N \le 2 \times 10^5)\) 个点 \(M(N-1 \le M \le \min(\frac{N \times (N-1)}{2}, 2 \times 10 ^ 5))\) 条边的无向简单连通图，每条边都有边权。定义一条路径的权值为路径中所有边权值的最大值。
定义 \(f(x, y)\) 为所有从点 \(x\) 到点 \(y\) 的路径中权值最小的路径。给你两个长度为 \(K(1 \le K \le N)\) 的序列 \((A_1, A_2, ..., A_K)\) 和 \((B_1, B_2, ..., B_K)\)，其中 \(1 \le A_i, B_i \le N\) 且保证 \(A_i \neq B_j(1 \le i, j \le K)\)
你可以任意变换序列 \(B\) 中元素的位置，问：最小的 \(\sum\limits_{i=1}^Kf(A_i, B_i)\) 是多少？
解题思路
一个结论是，最小生成树一定能保证图中任意两个点 \(x\) 和 \(y\) 对应的 \(f(x, y)\) 值最小。
考虑用 Kruskal 求解，在并查集中同时维护 \(A\) 中点的数量和 \(B\) 中点的数量，每当合并两个集合 \(X\) 和 \(Y\) 的时候，如果 \(X\) 集合中有一些 \(A\) 的点且 \(Y\) 集合中有一些 \(B\) 的点，就把它们匹配起来，则这些点对应的 \(f(x, y)\) 权值就是这条边的权值。其他情况，仅仅增加集合中点的数量即可。
参考代码
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
struct Edge
{
int u, v, w;
bool operator<(const Edge &other) const { return w < other.w; }
};
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<Edge> edge(m);
for (auto &[u, v, w] : edge)
cin >> u >> v >> w;
sort(edge.begin(), edge.end());
vector<LL> cnt(n + 1);
for(int i = 0; i < k; i++)
{
int a;
cin >> a;
cnt[a]++;
}
for(int i = 0; i < k; i++)
{
int b;
cin >> b;
cnt[b]--;
}
vector<int> parent_or_size(n + 1, -1);
auto leader = [&parent_or_size](auto &self, int u) -> int
{ return parent_or_size[u] < 0 ? u : parent_or_size[u] = self(self, parent_or_size[u]); };
LL ans = 0;
for(auto [u, v, w] : edge)
{
u = leader(leader, u);
v = leader(leader, v);
if(u == v)
continue;
if(-parent_or_size[u] < -parent_or_size[v])
swap(u, v);
if(cnt[u] * cnt[v] < 0)
{
LL t = min(abs(cnt[u]), abs(cnt[v]));
ans += t * w;
}
parent_or_size[u] += parent_or_size[v];
cnt[u] += cnt[v];
parent_or_size[v] = u;
}
cout << ans << endl;
return 0;
}
F - Diversity¶
题目大意
你有 \(X(1 \le X \le 50000)\) 元。商店里有 \(N(1 \le N \le 500)\) 个商品，第 \(i\) 个商品的价格是 \(P_i(1 \le P_i \le X)\) 元，价值是 \(U_i(1 \le U_i \le 10 ^ 9)\)，颜色是 \(C_i(1 \le C_i \le N)\)。每个商品只有 \(1\) 个，在商品总价格不超过 \(X\) 的情况下，你可以挑选任意商品购买。你的购物满意度是 \(S + T \times K\)，其中 \(S\) 表示购买的商品的价值之和，\(T\) 表示购买的商品中不同的颜色数，\(K(1 \le K \le 10 ^ 9)\) 是一个给定的常数。
问：最大的购物满意度是多少？
解题思路
如果不考虑颜色，这就是一个背包问题。考虑能否把颜色压缩到背包的维度中，但因为 \(C_i \le N\)，所以用状态记录买了哪些颜色是不现实的。
假设现在已经有一个方案能获得 \(S + T \times K\) 的满意度，对于一个商品 \(i\)，如果这个商品的颜色之前没有买过，则满意度会变为 \(S + T \times K + U_i + K\)，相当于满意度增加了 \(U_i + K\)，而如果是之前买过的颜色，满意度就变为 \(S + T \times K + U_i\)，相当于满意度增加了 \(U_i\)。
为了避免同时考虑多种颜色，可以把所有商品按颜色分组，同颜色的收集在一起（也可以按颜色排序）。设 \(P_{i, k}\) 和 \(U_{i, k}\) 分别表示颜色为 \(i\) 的第 \(k\) 个商品对应的价格和价值。
定义 \(dp[i][j]\) 表示前 \(i\) 种颜色中花 \(j\) 元能获得的最大满意度，每遍历一个商品 \((P_{i, k}, U_{i, k})\)，有三种情况：
- 不买这个颜色的商品，则 \(dp[i][j] = dp[i-1][j]\)
- 买这个颜色的商品，且 \((P_{i, k}, U_{i, k})\) 是第一次购买这个颜色的商品，则 \(dp[i][j] = dp[i-1][j-P_{i, k}] + U_{i, k} + K\)
- 买这个颜色的商品，且 \((P_{i, k}, U_{i, k})\) 不是第一次购买这个颜色的商品，则 \(dp[i][j] = dp[i][j-P_{i, k}] + U_{i, k}\)
总的时间复杂度 \(O(NX)\)
下面的代码压缩了存储空间，是从后往前更新的。
参考代码
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n, x, k;
cin >> n >> x >> k;
unordered_map<int, vector<pair<LL, LL>>> products;
for (int i = 0; i < n; i++)
{
int p, u, c;
cin >> p >> u >> c;
products[c].push_back({p, u});
}
vector<vector<LL>> dp(2, vector<LL>(x + 1));
LL *now = dp[0].data(), *pre = dp[1].data();
for (auto [_, v] : products)
{
swap(now, pre);
for (int j = 0; j <= x; j++)
now[j] = max(now[j], pre[j]);
for (auto [p, u] : v)
for (int j = x; j >= p; j--)
now[j] = max(max(now[j], pre[j - p] + u + k), now[j - p] + u);
}
LL ans = 0;
for (int j = 0; j <= x; j++)
ans = max(ans, now[j]);
cout << ans << endl;
return 0;
}
创建日期: 2025-01-01