感觉错失了上分机会
A - Takahashi san (abc325 A)
题目大意
给定姓和名，输出尊称，即姓+san。
解题思路
按照题意模拟即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
cout << s << " san" << '\n';
return 0;
}
B - World Meeting (abc325 B)
题目大意
给定\(n\)个地区的公司人数和对应的时区，规定上班时间为 \(9:00-18:00\)，现召开一小时会议，上班期间的公司可以参加。问订个时间，能参与的人数的最大值。
解题思路
枚举开会的时间，然后依次判断每个公司能否参加，累计参加人数，取最大值即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<array<int, 2>> a(n);
for (auto& i : a)
cin >> i[0] >> i[1];
int ans = 0;
auto is_work_time = [](int time) { return time >= 9 && time < 18; };
for (int i = 0; i < 24; ++i) {
int sum = 0;
for (auto& [num, time] : a)
if (is_work_time((i + time) % 24))
sum += num;
ans = max(ans, sum);
}
cout << ans << '\n';
return 0;
}
C - Sensors (abc325 C)
题目大意
给定二维平面，有#和.。每个#可以与周围八个格子连成一整体。
问有多少个整体。
解题思路
用BFS或者并查集判断一下连通性，最后数连通块即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
sz.resize(n);
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
dsu d(h * w);
auto two2one = [&](int x, int y) { return x * w + y; };
vector<string> s(h);
for (int i = 0; i < h; ++i) {
cin >> s[i];
for (int j = 1; j < w; ++j) {
if (s[i][j - 1] == '#' && s[i][j] == '#') {
d.unite(two2one(i, j - 1), two2one(i, j));
}
}
if (i) {
for (int j = 0; j < w; ++j) {
if (s[i - 1][j] == '#' && s[i][j] == '#') {
d.unite(two2one(i - 1, j), two2one(i, j));
}
if (j > 0 && s[i - 1][j - 1] == '#' && s[i][j] == '#') {
d.unite(two2one(i - 1, j - 1), two2one(i, j));
}
if (j + 1 < w && s[i - 1][j + 1] == '#' && s[i][j] == '#') {
d.unite(two2one(i - 1, j + 1), two2one(i, j));
}
}
}
}
int ans = 0;
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
if (s[i][j] == '#') {
ans += d.get(two2one(i, j)) == two2one(i, j);
}
cout << ans << '\n';
return 0;
}
D - Printing Machine (abc325 D)
题目大意
给定\(n\)个物品的出现时间和消失时间。拿一个物品花费 \(1\)的时间。
问最多能拿多少个物品。
解题思路
对于某一时刻，我肯定拿出现的物品中，最早消失的物品。
由此贪心拿即可。
注意每拿完一个物品后要考虑是否有新物品出现。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<array<LL, 2>> a(n);
for (auto& i : a)
cin >> i[0] >> i[1];
vector<int> id(n);
iota(id.begin(), id.end(), 0);
ranges::sort(id, [&](int x, int y) {
if (a[x][0] != a[y][0])
return a[x][0] < a[y][0];
else
return a[x][1] < a[y][1];
});
priority_queue<LL> item;
LL time = 0;
int ans = 0;
auto it = id.begin();
while (!item.empty() || it != id.end()) {
if (item.empty())
time = a[*it][0];
while (it != id.end() && a[*it][0] <= time) {
item.push(-(a[*it][0] + a[*it][1]));
it = next(it);
}
while (!item.empty() && -item.top() < time)
item.pop();
if (!item.empty() && -item.top() >= time) {
++ans;
++time;
item.pop();
}
}
cout << ans << '\n';
return 0;
}
E - Our clients, please wait a moment (abc325 E)
题目大意
给定一张完全图，从\(1\)号点到 \(n\)号点，一开始打车，在某点可转成坐火车，但不能转回来。
从一个点到另一个点，打车和火车的耗时不同。
问最少耗时。
解题思路
注意到我们肯定是在某一点\(a\)转乘火车，那从\(1\)号点到 \(n\)号点就分成了两部分：
- 先打车到\(a\)号点（可以看成从\(a\)号点打车到 \(1\)号点）
- 再乘火车到 \(n\)号点
因此我们可以预处理出，每个点打车到\(1\)号点和坐火车到 \(n\)号点的最短耗时。然后两者的和的最小值就是答案。
而求每个点到 \(1\)号点的耗时和到 \(n\)号点的耗时，相当于分别从 \(1\)号点出发到每个点的耗时，以及从 \(n\)号点出发到每个点的耗时，两次 最短路即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, a, b, c;
cin >> n >> a >> b >> c;
vector<vector<int>> tu(n, vector<int>(n));
for (auto& i : tu)
for (auto& j : i)
cin >> j;
LL ans = numeric_limits<LL>::max();
auto dijkstra = [&](int st, function<LL(int)> E, vector<LL>& dis) {
dis[st] = 0;
priority_queue<pair<LL, int>> team;
team.push({0, st});
while (!team.empty()) {
auto [expect, u] = team.top();
team.pop();
if (dis[u] != -expect)
continue;
for (int v = 0; v < n; ++v) {
if (v == u)
continue;
if (dis[v] > dis[u] + E(tu[u][v])) {
dis[v] = dis[u] + E(tu[u][v]);
team.push({-dis[v], v});
}
}
}
};
vector<LL> dis0(n, numeric_limits<LL>::max());
auto dis1 = dis0;
dijkstra(
0, [&](int w) { return 1ll * w * a; }, dis0);
dijkstra(
n - 1, [&](int w) { return 1ll * w * b + c; }, dis1);
for (int i = 0; i < n; ++i) {
ans = min(ans, dis0[i] + dis1[i]);
}
cout << ans << '\n';
return 0;
}
F - Sensor Optimization Dilemma (abc325 F)
题目大意
给定\(n\)个区间长度，有两种操作，
- 操作一，区间长度减 \(a_1\)，成本 \(c_1\)，最多用 \(k_1\)次
- 操作二，区间长度减 \(a_2\)，成本 \(c_2\)，最多用 \(k_2\)次
问将每个区间长度减成非正的最小成本。
解题思路
考虑搜索的状态，就是当前的区间，操作一的使用次数，操作二的使用次数，然后枚举当前区间使用的操作一的次数，复杂度是\(O(nk^3)\)。
上述搜索转换成 \(dp\)的形式就是 \(dp[i][j][k]\)表示前\(i\) 个区间，操作一用了\(j\)次，操作二用了 \(k\)次，这一状态是否合法（即 bool型，成本从两个操作次数就能算出来），这难免过于浪费，我们可以把一个状态放到\(dp\)的值里。
即设 \(dp[i][j]\)表示前 \(i\)个区间，操作一用了 \(j\)次时，操作二使用的最小次数（换句话说就是最小成本），转移同样是枚举当前区间的操作一的次数，时间复杂度是 \(O(nk^2)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> d(n);
for (auto& i : d)
cin >> i;
array<int, 2> l{}, c{}, k{};
for (int i = 0; i < 2; ++i)
cin >> l[i] >> c[i] >> k[i];
vector<LL> dp(k[0] + 1, inf);
dp[0] = 0;
for (auto& i : d) {
vector<LL> dp2(k[0] + 1, inf);
for (int j = 0; j <= k[0]; ++j) {
for (int u = 0; u <= j; ++u) {
int v = max(0, (i - u * l[0] + l[1] - 1) / l[1]);
dp2[j] = min(dp2[j], dp[j - u] + v);
}
}
dp.swap(dp2);
}
LL ans = numeric_limits<LL>::max();
for (int i = 0; i <= k[0]; ++i) {
if (dp[i] <= k[1])
ans = min(ans, 1ll * i * c[0] + dp[i] * c[1]);
}
if (ans == numeric_limits<LL>::max())
ans = -1;
cout << ans << '\n';
return 0;
}
G - offence (abc325 G)
题目大意
给定一个字符串\(s\)和一个数 \(k\)，每次可以将 of连带后面的最多\(k\)个字符删除。
问字符串剩余的最小长度。
解题思路
依次考虑每个前缀，设\(dp[i]\)表示 \(s[1..i]\)经过操作后的最小长度，则 \(dp[i] = min(dp[i - 1] + 1, dp[j - 1])\)，其中 \(j\)是满足\(s[j..i]\)能完全被删除的。
从中我们发现需要求一个\(del[i][j]\)表示 \(s[i..j]\)能否被完全删除，这是一个常见的区间\(dp\)。考虑转移，分两种情况
- 一个就是常规的转移，即\(del[i][j] |= del[i][l] & del[l+1][j]\)
- 另一个是考虑进行一次操作，即\(s[i]=o\)，找到\(s[l]=f\)的地方，\(s[l+1..j]\)的进行操作后的最短长度 \(\leq k\)，这样就可以通过一次操作就把 \(del[i][j]\)完全删除。
设\(s[i..j]\)的进行操作后的最短长度为\(mink[i][j]\)，其转移就两种：
- 一个就是常规的转移，即\(mink[i][j] = \min(mink[i][l] + mink[l+1][j])\)
- 另一个就是当\(del[i][j]=true\)时， \(mink[i][j]=0\)
这样 \(dp\)数组就可以转移求答案了。
其实最后发现 \(mink[0][n-1]\)就是答案。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
int k;
cin >> s >> k;
vector<vector<int>> dp(s.size() + 1, vector<int>(s.size() + 1, 0));
vector<vector<int>> mink(s.size() + 1, vector<int>(s.size() + 1, 0));
for (int i = 0; i < dp.size(); ++i)
for (int j = i + 1; j < dp.size(); ++j)
dp[j][i] = 1;
for (int j = 0; j < s.size(); ++j) {
for (int i = j; i >= 0; --i) {
mink[i][j] = j - i + 1;
for (int l = i; l <= j; ++l)
dp[i][j] |= (dp[i][l] & dp[l + 1][j]);
for (int l = i; l <= j; ++l)
if (s[i] == 'o' && s[l] == 'f' && dp[i + 1][l - 1] &&
mink[l + 1][j] <= k) {
dp[i][j] = true;
}
if (dp[i][j])
mink[i][j] = 0;
else {
for (int l = i; l <= j; ++l) {
mink[i][j] = min(mink[i][j], mink[i][l] + mink[l + 1][j]);
}
}
}
}
cout << mink[0][s.size() - 1] << '\n';
return 0;
vector<int> dp2(s.size(), 0);
dp2[0] = 1;
for (int i = 1; i < s.size(); ++i) {
dp2[i] = dp2[i - 1] + 1;
for (int j = 0; j < i; ++j) {
if (dp[j][i]) {
if (j)
dp2[i] = min(dp2[i], dp2[j - 1]);
else
dp2[i] = 0;
}
}
}
cout << dp2.back() << '\n';
return 0;
}
可以发现这是一道区间\(dp\)，从它操作结果可以合并可以感受出来。即设 \(dp[l][r]\)表示子串 \(s[l..r]\)经过操作后的最小长度。
其中一个转移就是\(dp[l][r] = min(dp[l][i] + dp[i + 1][r])\)，就是两个区间的合并。
还有一个转移就是经过操作的转移，可以发现这类转移都可以归到\(s[l]=o\)的情况，因为如果 \(s[l] \neq o\)的话，其实可以归成上面这种情况。如果 \(s[l]=o\)，那么就找一个 \(s[i]=f\)，如果 \(dp[l+1][i-1] = 0\)，即完全删除，可以拼接出一个新的 \(of\)，那么 \(dp[l][r] = max(dp[i + 1][r] - k, 0)\)，即一个前缀被删除了，剩下的字符最多可再减去\(k\)个字符。
时间复杂度都是\(O(n^3)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
int k;
cin >> s >> k;
vector<vector<int>> dp(s.size() + 1, vector<int>(s.size() + 1, 0));
for (int r = 0; r < s.size(); ++r)
for (int l = r; l >= 0; --l) {
dp[l][r] = r - l + 1;
for (int m = l; m < r; ++m)
dp[l][r] = min(dp[l][r], dp[l][m] + dp[m + 1][r]);
if (s[l] == 'o')
for (int m = l + 1; m <= r; ++m) {
if (s[m] == 'f' && dp[l + 1][m - 1] == 0)
dp[l][r] = min(dp[l][r], max(0, dp[m + 1][r] - k));
}
}
cout << dp[0][s.size() - 1] << '\n';
return 0;
}
- Beginner AtCoder Contest 325beginner atcoder contest 325 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315