AtCoder Beginner Contest 364
A - Glutton Takahashi (abc364 A)
题目大意
给定\(n\)个字符串，问是否有两个相邻的 sweet。
解题思路
遍历判断当前字符串与上一个字符串是否都为sweet即可。
神奇的代码
#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;
string la;
cin >> n >> la;
bool ok = true;
for (int i = 1; i < n - 1; ++i) {
string cur;
cin >> cur;
if (cur == la && cur.back() == 't')
ok = false;
la = cur;
}
if (ok)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - Grid Walk (abc364 B)
题目大意
给定一个二维网格，有障碍物，有空地，给定初始位置。
给定移动操作，若移动目标位置为空地则移动，否则留在原地。
问最终位置。
解题思路
按照题意模拟上下左右移动即可。
神奇的代码
#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 h, w;
int sx, sy;
cin >> h >> w >> sx >> sy;
sx--;
sy--;
vector<string> s(h);
for (auto& x : s)
cin >> x;
string op;
cin >> op;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
for (auto c : op) {
int nx, ny;
if (c == 'L') {
nx = sx + dx[3];
ny = sy + dy[3];
} else if (c == 'R') {
nx = sx + dx[1];
ny = sy + dy[1];
} else if (c == 'U') {
nx = sx + dx[2];
ny = sy + dy[2];
} else {
nx = sx + dx[0];
ny = sy + dy[0];
}
if (nx < 0 || nx >= h || ny < 0 || ny >= w || s[nx][ny] == '#') {
continue;
}
sx = nx;
sy = ny;
}
cout << sx + 1 << " " << sy + 1 << '\n';
return 0;
}
C - Minimum Glutton (abc364 C)
题目大意
\(n\)个食物，有咸度和甜度。安排一个吃的顺序，使得吃的食物尽可能少，且一旦咸度\(> x\)或甜度 \(> y\)就停下来不吃。
解题思路
两者条件满足其一即可，那我们就单独考虑一维，比如第一维\(> x\)，那肯定是挑最大的那几个。因此对第一维排个序，求一遍前缀和直到 \(> x\)，看看有多少个。
再单独考虑第二维，挑最大的，看看多少个。
两个情况取最小值即可。
神奇的代码
#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;
LL x, y;
cin >> n >> x >> y;
vector<LL> a(n), b(n);
for (auto& i : a)
cin >> i;
for (auto& i : b)
cin >> i;
sort(a.begin(), a.end(), greater<LL>());
sort(b.begin(), b.end(), greater<LL>());
auto solve = [](vector<LL>& a, LL x) {
vector<LL> sum(a.size());
partial_sum(a.begin(), a.end(), sum.begin());
int ret = upper_bound(sum.begin(), sum.end(), x) - sum.begin();
return min(a.size(), ret + 1ul);
};
int ans = min(solve(a, x), solve(b, y));
cout << ans << '\n';
return 0;
}
D - K-th Nearest (abc364 D)
题目大意
\(n\)个二元组，选择尽可能少的二元组，使得第一维和 \(> x\)，或第二维和 \(> y\)。
一维坐标，给定\(n\)个点，依次回答 \(q\)个询问。
每个询问给定一个位置，问距离该位置第\(k\)近的点的距离是多少。
解题思路
对于询问的一个位置\(p\)，左边有一些点，右边也有一些点，对应了一些距离。
如果对这些点的距离进行一个排名，那么\(p\)往右，点的排名是依次递增的，同理往左也是依次递增。
因此可以二分右边的点，求该点的排名与 \(k\)的关系。而求该点的排名，还要求 \(p\)左边距离小于它的点的个数，这同样一个二分就可以解决了。
其实跟求第 \(k\)小的问题一样，我们可以二分这个距离是\(m\)，然后看 \([p-m, p+m]\) 的点的数量，如果是\(\geq k\)则说明该距离是第 \(k\)小或更大距离，则往小的方向收缩。 而统计点的数量则通过两次二分点坐标即可知道。
神奇的代码
#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, q;
cin >> n >> q;
vector<int> a(n);
for (auto& x : a)
cin >> x;
sort(a.begin(), a.end());
auto solve = [&](int b, int k) {
int l = -1, r = 2e8 + 1;
while (l + 1 < r) {
int m = (l + r) / 2;
int cnt = 0;
auto lb = lower_bound(a.begin(), a.end(), b - m);
auto rb = upper_bound(a.begin(), a.end(), b + m);
cnt = rb - lb;
if (cnt >= k)
r = m;
else
l = m;
}
return r;
};
while (q--) {
int b, k;
cin >> b >> k;
int ans = solve(b, k);
cout << ans << '\n';
}
return 0;
}
E - Maximum Glutton (abc364 E)
题目大意
\(n\)个食物，有咸度和甜度。安排一个吃的顺序，使得吃的食物尽可能多，且一旦咸度\(> x\)或甜度 \(> y\)就停下来不吃。
解题思路
安排顺序其实没什么用，最终还是决定要吃什么。
首先考虑满足咸度\(\leq x\)甜度 \(\leq y\)的情况下吃的尽可能多。
考虑朴素搜索，即每个食物吃或不吃，我们需要维护的状态是 考虑前\(i\)个食物，已经吃的咸度\(j\)，甜度\(k\) 这三个状态，容易发现这已经足够作出 吃或不吃的决策，记忆化一下，即\(dp[i][j][k]\)表示考虑前\(i\)个食物，我吃的咸度为 \(j\)，甜度为 \(k\)的最多食物数。
考虑其复杂度，其两个状态都是 \(O(10^4)\)的数量级，时间空间都不太行。但注意到其值的取值只有 \(O(n)\)，我们可以交换值和状态的意义，比如设 \(dp[i][j][k]\)表示考虑前\(i\)个食物，我吃了 \(j\)个食物，且咸度是\(k\)的最小甜度数。
转移时时刻保证 \(k \leq x\)且\(dp[i][j][k] \leq y\)即可，最后再随便吃一个。这样状态数即为 \(O(n^2x)\)，转移为\(O(1)\)，总的时间复杂度就是 \(O(n^2x)\)
神奇的代码
#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, x, y;
cin >> n >> x >> y;
vector<vector<int>> dp(n + 1, vector<int>(x + 1, inf));
dp[0][0] = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
vector<vector<int>> dp2(n + 1, vector<int>(x + 1, inf));
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= x; k++) {
dp2[j][k] = dp[j][k];
if (j > 0 && k >= a && dp[j - 1][k - a] + b <= y) {
dp2[j][k] = min(dp2[j][k], dp[j - 1][k - a] + b);
}
}
}
dp.swap(dp2);
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= x; j++) {
if (dp[i][j] <= y) {
ans = max(ans, i + 1);
}
}
}
ans = min(ans, n);
cout << ans << '\n';
return 0;
}
F - Range Connect MST (abc364 F)
题目大意
\(n+q\)个点，维护 \(q\)次操作。
第 \(i\)个操作，连边 \(j \to n+i\)，其中 \(l_i \leq j \leq r_i\)，边权\(c_i\)。
问最后是否连通，联通请求出最小生成树。
解题思路
是否构成连通块，即这\(q\)个线段是否构成一个大线段。
考虑最小生成树怎么求，即考虑前\(n\)个点该和哪个操作点 \((n+i)\)连边。
第一感觉就像是线段覆盖，即从代价小的操作开始，给\(l_i \leq j \leq r_i\)中的每个点合并成一个联通块，每合并一次的代价是 \(c_i\)。最后看是否是同个连通块即可。
连通块就用并查集维护，合并时总是以编号大的点为根，这样在上述 从左到右合并时能仅考虑每个连通块之间，而不用遍历\(l_i \to r_i\)了。
神奇的代码
#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) {
if (x > y)
swap(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 n, q;
cin >> n >> q;
vector<array<int, 3>> seg(q);
for (auto& [l, r, c] : seg) {
cin >> l >> r >> c;
--l, --r;
}
sort(seg.begin(), seg.end(),
[](const array<int, 3>& a, const array<int, 3>& b) {
return a[2] < b[2];
});
dsu d(n);
auto merge = [&](int l, int r) {
int cnt = 1;
int cur = d.get(l);
while (cur < r) {
int nxt = d.get(cur + 1);
d.unite(cur, nxt);
cur = nxt;
++cnt;
}
return cnt;
};
LL ans = 0;
for (auto& [l, r, c] : seg) {
int cnt = merge(l, r);
ans += 1ll * cnt * c;
}
if (d.sz[d.get(0)] != n)
ans = -1;
cout << ans << '\n';
return 0;
}
G - Last Major City (abc364 G)
题目大意
\(n\)个点 \(m\)条边，边有边权。
前 \(k-1\)个点是重要点。
依次解决以下问题。
分别选定 \(k \to n\) 的节点为重要点，问每个情况下，由重要点构成的最小生成树的权值。
解题思路
<++>
神奇的代码