AtCoder Beginner Contest 338
A - Capitalized? (abc338 A)
题目大意
给定一个字符串，问是否满足下述条件：
- 第一个字母大写
- 其余字母小写
解题思路
逐位判断即可。也可以将字符串变成上述形式，然后判断与原串是否相等。
神奇的代码
#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;
auto t = s;
t[0] = toupper(t[0]);
transform(t.begin() + 1, t.end(), t.begin() + 1, ::tolower);
if (s == t)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
B - Frequency (abc338 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);
array<int, 26> cnt{};
string s;
cin >> s;
for (auto& i : s) {
cnt[i - 'a']++;
}
int maxx = ranges::max(cnt);
for (int i = 0; i < 26; ++i)
if (cnt[i] == maxx) {
cout << char(i + 'a') << '\n';
break;
}
return 0;
}
C - Leftover Recipes (abc338 C)
题目大意
现有\(n\)种素材各 \(q_i\)个。
制作两种物品，物品\(A\)需要素材各 \(a_i\)个，物品 \(B\)需要素材各 \(b_i\)个。
问制作出来的物品数量的最大值。
解题思路
注意到\(q_i \leq 10^6\)。
那么一种物品制作出来的最大数量只有 \(10^6\)。
因此我们可以直接枚举制作的物品 \(A\)的数量，然后用剩下的素材看看能制作多少个物品 \(B\)。
时间复杂度是 \(O(10^6n)\)。
神奇的代码
#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<LL> q(n), a(n), b(n);
for (auto& x : q)
cin >> x;
for (auto& x : a)
cin >> x;
for (auto& x : b)
cin >> x;
LL ans = 0;
for (int i = 0; i <= 1000000; ++i) {
vector<LL> left(n);
for (int j = 0; j < n; ++j) {
left[j] = q[j] - 1ll * i * a[j];
}
if (ranges::min(left) < 0) {
continue;
}
LL r = 1e9;
for (int j = 0; j < n; ++j) {
if (b[j])
r = min(r, left[j] / b[j]);
}
ans = max(ans, r + i);
}
cout << ans << '\n';
return 0;
}
D - Island Tour (abc338 D)
题目大意
给定一个\(n\)个点的环，然后依次访问\(m\)个点 \(v_1,v_2,...,v_m\) 。
现问删去一条边，求依次访问这些点的距离（边数和）的最小值。
解题思路
一个朴素的\(O(n^2)\)做法即为枚举删去的边 \(i \to i+1\)，然后依次访问这些点求距离，取最小值。
考虑如何优化，上述做法的时间复杂度，一个花在了枚举删去的边 \(O(n)\)，一个花在了计算距离的 \(O(n)\)。
按顺序枚举删去的边，看看后者能否快速从上一个的答案得到。
通过画图可以发现可行。如下图所示。
假设一开始删除 \(n \to 1\)的边，求距离，即 \(\sum_{i=1}^{m-1}|v_{i+1} - v_i|\)。
然后考虑删除 \(1 \to 2\)的边，发现只有 \(1 \to 3\)的路径会变化，长度从原来的 \(3-1变成了5-(3-1)\)。而其他的边比如 \(2 \to 4\)的路径没有变化。
而当删除 \(3 \to 4\)的边时，原来的 \(1 \to 3\)的路径再度发生变化，从 \(5-(3-1)\)变回了 \(3-1\)。
综上观察可得，对于原来的路径 \(i \to j(i < j)\)，当我们删除边 \(i \to i+1\)时，该路径会发生变化，而当删除边 \(j \to j + 1\)时，该路径会再度发生变化。
因此当我们删边从 \(i-1 \to i\)变成 \(i \to i +1\)时，对于路径 \(x \to y(x < y)\)中，只有所有 \(x = i\)和 \(y = i\)的路径会发生变化，我们直接更新这些路径的距离即可。其他路径则不会发生变化。
由于每条边只会被更新两次，因此总的时间复杂度是 \(O(n + m)\)。
神奇的代码
#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, m;
cin >> n >> m;
vector<int> x(m);
for (auto& i : x) {
cin >> i;
--i;
}
vector<array<int, 3>> edge(m - 1);
for (int i = 0; i < m - 1; ++i) {
int u = x[i], v = x[i + 1];
if (u > v)
swap(u, v);
edge[i] = {u, v, v - u};
}
LL sum = 0;
for (auto& e : edge) {
sum += e[2];
}
LL ans = sum;
vector<vector<int>> l(n), r(n);
for (int i = 0; i < m - 1; ++i) {
l[edge[i][0]].push_back(i);
r[edge[i][1]].push_back(i);
}
for (int i = 0; i < n; ++i) {
for (auto id : l[i]) {
sum -= edge[id][2];
edge[id][2] = n - edge[id][2];
sum += edge[id][2];
}
for (auto id : r[i]) {
sum -= edge[id][2];
edge[id][2] = n - edge[id][2];
sum += edge[id][2];
}
ans = min(ans, sum);
}
cout << ans << '\n';
return 0;
}
E - Chords (abc338 E)
题目大意
\(n\)个点的圆环，给定\(m\)条线段，端点不重合，问是否有交点。
解题思路
考虑枚举线段\([l,r]\)，我们需要判断是否有线段与其相交，就需要：
- 判断所有左端点在\([l+1, r-1]\)的线段的右端点的最大值是否大于\(r\)。
- 判断所有右端点在\([l+1, r-1]\)的线段的左端点的最小值是否小于\(l\)。
对于第一个判断，则对线段的左端点排序，那上述判断就是一个关于右端点的区间最值问题，因为是多次查询而无修改，则用\(ST\)维护即可。这个区间范围直接通过关于左端点对\(l\)和 \(r\)的二分得到。
对于第二个判断，则对线段的右端点排序，那上述判断就是一个关于左端点的区间最值问题，因为是多次查询而无修改，则用\(ST\)维护即可。这个区间范围直接通过关于左端点对\(l\)和 \(r\)的二分得到。
时间复杂度为\(O(n\log n)\)
好像有更简洁的做法
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
public:
int n;
vector<vector<T>> mat;
F func;
SparseTable(const vector<T>& a, const F& f) : func(f) {
n = static_cast<int>(a.size());
int max_log = 32 - __builtin_clz(n);
mat.resize(max_log);
mat[0] = a;
for (int j = 1; j < max_log; j++) {
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
}
T get(int from, int to) const { // [from, to]
assert(0 <= from && from <= to && to <= n - 1);
int lg = 32 - __builtin_clz(to - from + 1) - 1;
return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<array<int, 2>> e(n);
for (auto& i : e) {
cin >> i[0] >> i[1];
if (i[0] > i[1])
swap(i[0], i[1]);
}
sort(e.begin(), e.end(),
[](const array<int, 2>& a, const array<int, 2>& b) {
return a[0] < b[0];
});
vector<int> s1(n), t1(n);
for (int i = 0; i < n; ++i) {
s1[i] = e[i][0];
t1[i] = e[i][1];
}
SparseTable<int> rb(t1, [&](int a, int b) { return max(a, b); });
auto ee = e;
sort(ee.begin(), ee.end(),
[](const array<int, 2>& a, const array<int, 2>& b) {
return a[1] < b[1];
});
vector<int> s2(n), t2(n);
for (int i = 0; i < n; ++i) {
s2[i] = ee[i][1];
t2[i] = ee[i][0];
}
SparseTable<int> ls(t2, [&](int a, int b) { return min(a, b); });
bool ok = false;
auto check = [&](int l, int r, auto& pos, auto& st) {
auto L = ranges::upper_bound(pos, l) - pos.begin();
auto R = ranges::lower_bound(pos, r) - pos.begin();
if (L >= R)
return false;
auto v = st.get(L, R - 1);
return v < l || v > r;
};
for (auto& i : e) {
if (check(i[0], i[1], s1, rb) || check(i[0], i[1], s2, ls)) {
ok = true;
break;
}
}
if (ok)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
F - Negative Traveling Salesman (abc338 F)
题目大意
给定一张图，边有边权，问访问所有点的最小边权和。边权有负，但无负环。多次访问算多次边权。
解题思路
一个朴素的做法就是状压\(DP\)，设 \(dp[i][j]\)表示当前访问的点的状态为\(i\)，当前在点\(j\)的最小距离。
因为会有边权为负，直接\(DP\)的话（即两个\(for\)循环，\(i\)和 \(j\)），在转移时\(i\)不变的情况下，可能会得到更优的 \(dp[i][k](k < j，即更新已经\)for\(过的状态）\)，导致 原来\(dp[i][k]\)往后更新的状态不是最优的。
这跟用\(BFS\)求最短距离遇到的问题一样，需仿照\(dijkstra\)那样，用一个优先队列来维护 \(DP\)顺序，从\(dp[i][j]\)最小的状态 \((i,j)\)往后转移，或者像\(SPFA\)那样，通过多次进队解决，由于\(n\)只有 \(20\)，跑一次 \(floyd\)也行。
考虑其复杂度，状态数已经是\(O(2^n n)\) 是\(1e7\)的级别了，再加上 优先队列的 \(log\)复杂度，第一次尝试时不出意料超时了。
考虑优化，注意到原来的两层循环状态\((i,j)\)，可能转移到 \((i|(1<<k),k)\)或 \((i,k)\) ，其中第二维大小关系不是固定的，但第一维要么更大，要么不变，而我们使用 \(dijkstra\)式的方式维护更新时，主要是防止\(i\)不变的转移造成的重复更新。
原来是直接维护状态\((i,j)\)的转移顺序，状态数达到 \(O(2^n n)\)，但转移的第一维有明显的方向性，因此我们可以对第一维一层一层的求解，在每一层的求解使用优先队列维护转移。这样优先队列里的状态数降为\(O(n)\)，\(n\)只有 \(20\)就基本没什么耗时，最后的复杂度就是\(O(2^n n \log 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, m;
cin >> n >> m;
vector<vector<array<int, 2>>> edge(n);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
edge[u].push_back({v, w});
}
int up = (1 << n);
vector<vector<int>> dp(up, vector<int>(n, INT_MAX));
for (int i = 0; i < n; ++i) {
dp[1 << i][i] = 0;
}
for (int i = 0; i < up; ++i) {
priority_queue<array<int, 3>, vector<array<int, 3>>,
greater<array<int, 3>>>
pq;
for (int j = 0; j < n; ++j) {
if (dp[i][j] != INT_MAX)
pq.push({dp[i][j], i, j});
}
while (!pq.empty()) {
auto [d, s, u] = pq.top();
pq.pop();
if (dp[s][u] < d)
continue;
for (auto [v, w] : edge[u]) {
if (dp[s | (1 << v)][v] > dp[s][u] + w) {
dp[s | (1 << v)][v] = dp[s][u] + w;
if ((s | (1 << v)) == s)
pq.push({dp[s | (1 << v)][v], s | (1 << v), v});
}
}
}
}
int ans = INT_MAX;
for (int i = 0; i < n; ++i) {
ans = min(ans, dp[(1 << n) - 1][i]);
}
if (ans == INT_MAX) {
cout << "No" << '\n';
} else
cout << ans << '\n';
return 0;
}
G - evall (abc338 G)
题目大意
给定一个字符串，包含数字和\(+*\)。问所有的子串的表达式的值。若表达式不合法则其值为\(0\)。
解题思路
<++>
神奇的代码