ABC325VP 记录

ABC325 VP 记录

目录

• ABC325 VP 记录
  • A
    • 题意
    • 思路
    • 代码
  • B
    • 题意
    • 思路
    • 代码
  • C
    • 题意
    • 思路
    • 代码
  • D
    • 题意
    • 思路
    • 代码
  • E
    • 题意
    • 思路
    • 代码
  • F
    • 题意
    • 思路
    • 代码
  • G
    • 题意
    • 思路
    • 代码

A

题意

一个人的名字由 姓 \(S\) 和 名 \(T\) 组成
Keyence 公司对一个人的称呼是姓加上 san

给定一个人的姓， 名， 输出他的称呼

思路

直接输出 S + san

时间复杂度 \(O(1)\)

空间复杂度 \(O(|s|)\)

代码

(甚至不用读 \(T\))

// A - Takahashi san
// 2000 ms
// 1024 MB
// https://atcoder.jp/contests/abc325/tasks/abc325_a
// Made by Billlly 喵~#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using real = long double;int tests = 1;void solve() {std::string s;std::cin >> s;std::cout << s << ' ' << "san" << '\n';
}int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);while (tests--) {solve();}return 0;
}

B

题意

Keyence 公司有 \(N\) 个基地, 每个基地有 \(W\) 个员工吗, 相较于协调世界时晚了 \(X\) h, 现在你要选择一个整点开一场会议，每个基地的员工只有在当地时间 $ 9:00$ ~ \(18:00\) 才会参会，请你确定最多有多少个员工可以参会

思路

显然只有可能在 \(0:00\) ~ \(23:00\) 的任意一个整点开会，所以我们枚举开始时间，对于每一个基地，只有它们当地时间位于 \(9:00\) ~ \(17:00\) 时他们才能 听完 会议，然后记录最大值即为答案

时间复杂度 \(O(24n)\)
空间复杂度 \(O(n)\)

代码

// B - World Meeting
// 2000 ms
// 1024 MB
// https://atcoder.jp/contests/abc325/tasks/abc325_b
// Made by Billlly 喵~#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using real = long double;int tests = 1;void solve() {int n;std::cin >> n;std::vector<std::pair<int, int> > bases(n + 1);for (int i = 1; i <= n; ++i)std::cin >> bases[i].first >> bases[i].second;int ans = 0;for (int i = 0; i <= 23; ++i) {int now = 0;for (int j = 1; j <= n; ++j) {int tim = (bases[j].second + i) % 24;if (tim >= 9 and tim <= 17)now += bases[j].first;}ans = std::max(ans, now);}std::cout << ans << '\n';
}int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);while (tests--) {solve();}return 0;
}

C

题意

Keyence 公司有若干个传感器分布在 \(N \times M\) 的地图上，如果 \((i, j)\) 位置是 #， 代表这个地方有传感器

如果两个传感器八连通则称它们相互作用，当作一个传感器来看待，相互作用具有传递性

求共有多少个被不同看待的传感器

思路

其实就是求八连通个数，纯板子

直接对于每一个点 dfs， 记得记录 vis 就行了

时间/空间复杂度 \(O(nm)\)

代码

// C - Sensors
// 2000 ms
// 1024 MB
// https://atcoder.jp/contests/abc325/tasks/abc325_c
// Made by Billlly 喵~#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using real = long double;int tests = 1;void solve() {int n, m;std::cin >> n >> m;std::vector<std::vector<char> > mp(n + 1, std::vector<char>(m + 1));for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)std::cin >> mp[i][j];std::vector<std::vector<bool> > vis(n + 1, std::vector<bool>(m + 1, false));int ans = 0;const std::vector<int> dx = {0, 1, 0, -1, 1, -1, 1, -1};const std::vector<int> dy = {1, 0, -1, 0, 1, 1, -1, -1};auto dfs = [&](auto&& dfs, int x, int y) -> void {if (vis[x][y])return;vis[x][y] = true;for (int i = 0; i < 8; ++i) {int nx = x + dx[i];int ny = y + dy[i];if (nx >= 1 and nx <= n and ny >= 1 and ny <= m andnot vis[nx][ny] and mp[nx][ny] == '#')dfs(dfs, nx, ny);}};for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (not vis[i][j] and mp[i][j] == '#') {dfs(dfs, i, j);++ans;} elsevis[i][j] = true;}}std::cout << ans << '\n';
}int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);while (tests--) {solve();}return 0;
}

D

题意

有 \(N\) 个文件经过打印机，第 \(i\) 个文件从 \(T_i\) μs 进入打印机，经过 \(D_i\) μs 出打印机，打印机可以在每一 μs 选择在内部的一个文件复印并花费 1 μs，问最多可以复印下来多少张文件？

思路

省流：依旧贪心苦手，依旧 WA WA WA

显然每一 μs 选择最早离开打印机的文件一定是最优的， 这个具体证明由于篇幅就不写了，感性理解是好理解的

所以用先按进入时间为第一关键字，离开时间为第二关键字，小根堆维护一下就做完了

代码

// D - Printing Machine
// 3000 ms
// 1024 MB
// https://atcoder.jp/contests/abc325/tasks/abc325_d
// Made by Billlly 喵~#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using real = long double;int tests = 1;void solve() {int n;std::cin >> n;std::vector<std::pair<i64, i64>> seg(n + 1, {0ll, 0ll});for (int i = 1; i <= n; ++i)std::cin >> seg[i].first >> seg[i].second;std::sort(seg.begin() + 1, seg.end(),[](const std::pair<i64, i64>& a, const std::pair<i64, i64>& b) {return ((a.first == b.first)? a.first + a.second < b.first + b.second: a.first < b.first);});int ans = 0;std::priority_queue<i64, std::vector<i64>, std::greater<i64>> q;for (i64 t = 0, i = 1; i <= n or not q.empty(); ++t) {if (q.empty())t = seg[i].first;while (i <= n and seg[i].first == t) {q.emplace(seg[i].second + seg[i].first);++i;}while (not q.empty() and q.top() < t)q.pop();if (not q.empty()) {++ans;q.pop();}}std::cout << ans << '\n';
}int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);while (tests--) {solve();}return 0;
}

E

题意

给定一个 \(N\) 个节点的图，这个图的性质是每个节点到所有节点（包括自己）的所有节点连一条有向边，权值为 \(d\)

还有三个权值 \(a, b, c\)

现在你要从城市 \(1\) 走入 \(N\)，对于每条路径，其权值为 \(d\)，你可以选择两种方式走过这条路径

1. 公司汽车，花费 \(d * a\) min
2. 火车，花费 \(d * b + c\) min

你可以在任意站点从公司汽车换乘火车，但没法换乘回公司汽车，求最短时间

思路

直接连一个分层图

第一层是公司汽车，第二层是火车，由第一层向第二层对应节点连一条权值为 \(0\) 的有向边，代表换乘，然后跑第一层的节点 1 到第二层的节点 N 的最短路

为什么正确？首先如果答案要换乘，正确性是显然的，那如果全程做火车呢？那其实等价于从第一站就开始换成; 同理，如果全程公司汽车，就相当于到最后一站换乘

时间复杂度 \(O(n^2 log n)\) (Dijkstra)

空间复杂度 \(O(n^2)\)

代码

// E - Our clients, please wait a moment
// 2000 ms
// 1024 MB
// https://atcoder.jp/contests/abc325/tasks/abc325_e
// Made by Billlly 喵~#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using real = long double;int tests = 1;void solve() {int n;i64 a, b, c;std::cin >> n >> a >> b >> c;std::vector<std::vector<std::pair<int, i64>>> adj(n << 1 | 1);for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {i64 d;std::cin >> d;adj[i].emplace_back(j, d * a);adj[i + n].emplace_back(j + n, d * b + c);}}for (int i = 1; i <= n; ++i)adj[i].emplace_back(i + n, 0);const i64 INF = 1e18;std::vector<i64> dist(n << 1 | 1, INF);std::vector<bool> vis(n << 1 | 1, false);std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>,std::greater<std::pair<i64, int>>>pq;dist[1] = 0;pq.emplace(0, 1);while (not pq.empty()) {auto [d, u] = pq.top();pq.pop();if (vis[u])continue;vis[u] = true;for (auto [v, w] : adj[u]) {if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.emplace(dist[v], v);}}}std::cout << dist[2 * n] << '\n';
}int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);while (tests--) {solve();}return 0;
}

F

题意

\(N\) 个传送带， 第 \(i\) 个传送带长度为 \(D_i\)

有两个传感器，第 \(i\) 个传感器可以监测 \(L_i\)，价格\(C_i\), 最多可以用\(K_i\)个

请你判断是否可以完全覆盖所有的传送带，如果可以输出需要的最少价格

思路

其实就是一个背包问题，我们发现只需要记录 \(dp_{i,j}\) 表示前 \(i\) 个传送带用了 \(j\) 个一型传感器，最少还需要多少个二型传感器

对于第 \(i\) 个传送带，如果我们用了 \(x\) 个一型，则至少需要 \(\lceil \frac{D_i - x \cdot L_1}{L_2}\rceil\) 个二型

所以就有

\[dp_{i,j} \leftarrow \max_{0 \leq s \leq j} \left( dp_{i-1,s} + \left\lceil \frac{\max\left(0, D_i - (j - s) \cdot L_1\right)}{L_2} \right\rceil \right) \]

代码

// dp - Sensor Optimization Dilemma
// 2000 ms
// 1024 MB
// https://atcoder.jp/contests/abc325/tasks/abc325_f
// Made by Billlly 喵~#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using real = long double;int tests = 1;void solve() {int n;std::cin >> n;std::vector<int> a(n + 1, 0);for (int i = 1; i <= n; ++i)std::cin >> a[i];int l[2] = {}, b[2] = {}, m[2] = {};for (int p = 0; p < 2; ++p)std::cin >> l[p] >> b[p] >> m[p];const i64 inf = 1e18;std::vector<std::vector<i64>> dp(n + 1, std::vector<i64>(m[0] + 1, inf));dp[0][0] = 0;auto calc = [&](int rem, int val) -> int {int need = std::max(0, val - rem * l[0]);if (need <= 0)return 0;return (need + l[1] - 1) / l[1];};for (int i = 1; i <= n; ++i) {for (int j = 0; j <= m[0]; ++j) {for (int r = 0; r <= j; ++r) {int need = calc(j - r, a[i]);if (dp[i - 1][r] + need < dp[i][j])dp[i][j] = dp[i - 1][r] + need;}}}i64 ans = inf;for (int j = 0; j <= m[0]; ++j) {if (dp[n][j] > m[1])continue;i64 cur = 1LL * j * b[0] + 1LL * dp[n][j] * b[1];if (cur < ans)ans = cur;}std::cout << (ans == inf ? -1 : ans) << '\n';
}int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);while (tests--) {solve();}return 0;
}

G

题意

给定一个字符串 \(S\) 和一个参数 \(K\), 你可以进行若干次如下操作

选择一个存在的子串of，然后删除它及其后方不超过 \(K\) 个字符

问最后这个字符串的最小可能长度

思路

省流：ABC 真爱 DP

这类区间类问题我们考虑区间DP

\(dp_{i, j}\) 表示区间 \([i, j]\) 操作后的可能最短长度

• 如果 \(S_i\) 不是 'o', 则加入 \(S_i\) 之后不会产生新的删除可能性，那我们就直接枚举分割点，dp值就是左右两区间的加和最大值
• 如果 \(S_i\) 是 'o'，则我们枚举 \([i + 1, j]\) 中的所有 'f'

最终转移就可以写出来了，见代码

时间复杂度 \(O(n ^ 3)\)

代码

// G - offence
// 2000 ms
// 1024 MB
// https://atcoder.jp/contests/abc325/tasks/abc325_g
// Made by Billlly 喵~#include <bits/stdc++.h>using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using real = long double;int tests = 1;void solve() {std::string s;std::cin >> s;int n = s.size();int k;std::cin >> k;auto dfs = [&](auto&& dfs, int l, int r) -> int {if (l > r)return 0;static std::vector<std::vector<int>> mem(n, std::vector<int>(n, -1));if (mem[l][r] != -1)return mem[l][r];int& res = mem[l][r];res = r - l + 1;if (l == r) {res = 1;return res;}if (l + 1 == r) {res = (s[l] == 'o' and s[r] == 'f') ? 0 : 2;return res;}if (s[l] == 'o') {for (int m = l + 1; m <= r; ++m) {if (s[m] != 'f')continue;int left = 0;if (m > l + 1)left = dfs(dfs, l + 1, m - 1);if (left != 0)continue;int right = dfs(dfs, m + 1, r);res = std::min(res, std::max(right - k, 0));}}for (int m = l; m < r; ++m)res = std::min(res, dfs(dfs, l, m) + dfs(dfs, m + 1, r));return res;};std::cout << dfs(dfs, 0, n - 1) << '\n';
}int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);while (tests--) {solve();}return 0;
}