AtCoder Beginner Contest 373
省流版
- A. 暴力即可
- B. 求出字母位置,绝对值相加即可
- C. 显然答案为两个数组的最大值的和
- D. 注意直接BFS的点权范围不超过题目范围,直接BFS即可
- E. 发现单调性,二分票数,用前缀和\(O(1)\)判断可行性即可
- F. 朴素背包DP,相同重量的物品一起考虑,用优先队列求解\(l\)个相同重量物品最大价值的最优取法即可
A - September (abc373 A)
题目大意
给定\(12\)个字符串,问第 \(i\)个字符串的长度是不是 \(i\)。
解题思路
按照题意依次判断即可,python
可以一行。
神奇的代码
print(sum(i + 1 == len(input().strip()) for i in range(12)))
B - 1D Keyboard (abc373 B)
题目大意
给定一个键盘,从左到右的\(26\)个字母分别是什么。
现在依次输入abcdefgh...xyz
,初始手指在a
处,然后要移动到b
处按b
,然后移动到c
处按c
...
问输入完这\(26\)个字符需要移动的距离数。
解题思路
当前手指在位置\(x\),移动到下一个字母的位置 \(y\) ,距离数是\(|x-y|\),求出 \(pos[i]\)表示字符 \(i\)的位置,答案就是 \(|pos[i] - pos[i-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;
cin >> s;
array<int, 26> pos{};
for (int i = 0; i < 26; ++i)
pos[s[i] - 'A'] = i;
int ans = 0;
for (int i = 1; i < 26; ++i)
ans += abs(pos[i] - pos[i - 1]);
cout << ans << '\n';
return 0;
}
C - Max Ai+Bj (abc373 C)
题目大意
给定两个数组\(a,b\),分别从中选一个数,使得和最大。
解题思路
显然选的两个数分别为最大的数即可。python
可以两行。
神奇的代码
input()
print(max(map(int, input().split())) + max(map(int, input().split())))
D - Hidden Weights (abc373 D)
题目大意
给定一张有向图,边有边权。
确定点权\(x_i\),满足对于每一条有向边 \(u_i \to v_i, w_i\),满足 \(x_{v_i} - x_{u_i} = w_i\)。
题目保证有解。
解题思路
视为无向图,但反过来的边权是\(-w_i\),然后从未访问过的点开始\(BFS\),其点权为\(0\),然后按照上述等式得到周围点的点权即可。
点数\(n \leq 2 \times 10^5\),边权 \(\leq 10^9\),所以点权不会超过\(2 \times 10^{14}\),满足题意范围的 \(10^{18}\)。
神奇的代码
#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});
edge[v].push_back({u, -w});
}
vector<LL> ans(n);
queue<int> team;
vector<int> vis(n);
auto BFS = [&](int st) {
team.push(st);
vis[st] = 1;
while (!team.empty()) {
int u = team.front();
team.pop();
for (auto& [v, w] : edge[u]) {
if (vis[v])
continue;
ans[v] = ans[u] + w;
vis[v] = 1;
team.push(v);
}
}
};
for (int i = 0; i < n; ++i)
if (!vis[i])
BFS(i);
for (int i = 0; i < n; ++i)
cout << ans[i] << " \n"[i == n - 1];
return 0;
}
E - How to Win the Election (abc373 E)
题目大意
\(n\)个候选人, \(k\)张票。最终票数最多的\(m\)个候选人获胜,同票数的都会获胜,因此可能获胜的可能会超过 \(m\)个 。
现已知部分投票情况。 问每一个候选人,需要给他至少多少张票,才能使得他一定会获胜,即无论剩余票数如何分配,他始终都是票数前\(m\)多的。
解题思路
对于当前第\(i\)个候选人,他的票数\(v_i\)目前排第 \(rank_i\)名,那他至少还要多少票才能稳赢呢?
最朴素的想法就是,枚举这个票数,即假设他得到了\(x\)票,看看能否稳赢? (如果你没想到二分,可能是因为这个最朴素的做法没想到——通过增设条件来解决问题,从这个条件其实是很容易看出来具有单调性,进而可以二分)
那能否稳赢呢?假设他得到了\(x\)票,那此时的票数是 \(v_i + x\),通过二分可以得到该票数的排名,假设是\(r_i\)名。然后还剩下\(left\)张票没投。
- 如果 \(r_i > m\),那他必不可能赢了。
- 如果 \(r_i \leq m\),即此时他前面只有 \(r_i - 1\)个人,剩下的票分配给其他人,只要少于 \(danger = m - r_i + 1\)个人的票数超过他,那他就能赢。
考虑最坏情况,即为票数\(\leq v_i + x\)的最大的\(danger\)个人的票数达到\(v_i + x + 1\)所需要的票数,少于剩余未投的票数 \(left\),那第 \(i\)个人一定是票数前 \(m\) 大的,即稳赢。而前者的票数计算相当于是\(danger \times (v_i + x + 1) - \sum v_j\) ,事先对\(v\)排序,后者其实就是一个区间和,可以用前缀和优化,在 \(O(1)\)的时间内得到。
到此,我们可以 \(O(1)\)判断当前枚举的票数 \(x\)是不是稳赢的。但枚举的票数的范围有 \(O(k)\),但容易发现该票数
与是否稳赢
之间具有单调性——给越多票,稳赢的可能性越高。
因此我们不必一个一个枚举票数,而是二分该票数,然后 通过前缀和,\(O(1)\) 判断是否可行即可。
对所有人都这么求一遍,总的时间复杂度就是\(O(n \log 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, m;
LL k;
cin >> n >> m >> k;
vector<LL> a(n);
for (auto& i : a)
cin >> i;
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) { return a[i] > a[j]; });
vector<LL> sum(n);
sum[0] = a[id[0]];
for (int i = 1; i < n; ++i)
sum[i] = sum[i - 1] + a[id[i]];
vector<LL> ans(n);
LL left = k - accumulate(a.begin(), a.end(), 0ll);
auto get_sum = [&](int l, int r, int ex) {
if (l > r)
return 0ll;
LL s = 0;
if (l <= ex && ex <= r) {
r += 1;
s -= a[id[ex]];
}
s += sum[r] - (l ? sum[l - 1] : 0);
return s;
};
auto solve = [&](int pos, int rank) {
auto check = [&](LL votes) {
LL now_votes = a[pos] + votes;
int now_rank = lower_bound(id.begin(), id.end(), now_votes,
[&](int x, LL v) { return a[x] > v; }) -
id.begin();
int left_candi = m - now_rank;
LL demand = left_candi * (now_votes + 1) -
get_sum(now_rank, now_rank + left_candi - 1, rank);
LL ano = left - votes;
return ano < demand;
};
LL l = -1, r = left;
while (l + 1 < r) { //(l, r]
LL mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid;
}
return check(r) ? r : -1;
};
for (int i = 0; i < n; ++i) {
ans[id[i]] = solve(id[i], i);
}
for (int i = 0; i < n; ++i)
cout << ans[i] << " \n"[i == n - 1];
return 0;
}
F - Knapsack with Diminishing Values (abc373 F)
题目大意
\(n\)种物品,重量 \(w_i\),价值\(v_i\),无限个。
背包容量 \(W\),现在选物品放入背包,不超背包容量,价值最大。
当第 \(i\)种物品放 \(k\)个时,其价值为 \(kv_i - k^2\)。
解题思路
考虑最朴素的背包做法,即\(dp[i][j]\)表示考虑前 \(i\)个物品,放的容量是 \(j\)的最大价值。转移即考虑当前物品放多少个,其时间复杂度为 \(O(nw^2)\)。此处 \(n \leq 3000\),无法通过。
究其复杂度,主要在考虑每种物品,其重量是\(w_i\),我们需要考虑该物品的数量为 \(1,2,...,\lfloor \frac{W}{w_i} \rfloor\) 。如果每个物品的重量都挺小的,那么物品数量的数量级就是\(O(W)\)。转移的复杂度就是 \(O(W)\)。
怎么办呢?对于重量都小的,我们能否一起考虑呢?
即我们不依次考虑每种物品,而是依次考虑重量为\(i\)的所有物品,即设 \(dp[i][j]\)表示考虑重量\(\leq i\)的物品,放的容量是 \(j\)的最大价值。这样考虑的物品数量就是\(O(\frac{W}{i})\),对所有的\(i\)的转移复杂度累加,其复杂度就是 \(O(w^2 \log w)\)。
复杂度对了,考虑如何转移呢,即\(dp[i][j]\),然后枚举选重量为 \(i\)的物品的数量个数 \(l\),假设其物品的价值分别是 \(v_1,v_2,v_3,...\),现在要取 \(l\)个,怎么取最优?
由于每种物品的价值,随着取的个数的增加,其价值会减少,最朴素的想法就是一个一个取。
考虑每种物品是一行,从左到右的物品的价值依次减少,即设\(f_i(k) = kv_i - k^2\),第一行第一个物品的价值是\(f_1(1)\),第二个物品的价值就是\(f_1(2) - f_1(1)\),第三个物品的价值就是 \(f_1(3) - f_1(2)\),而第二行的第一个物品的价值就是\(f_2(1)\)。
上述怎么取的问题就变成,每行取一个前缀的物品,一共 \(l\)个,价值最大。
我们就考虑每行的第一个未取的物品,每次就取这些行里,价值最大的。如何快速找到这些的最大值,用优先队列维护即可,队列里的元素最多也就\(O(n)\)。
由于取物品数量\(l\)是从 \(1\)开始枚举的,因此求最优的取法就这样依次迭代,从优先队列里取价值最大的物品即可。
总的时间复杂度是 \(O(w^2 \log w \log n)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, w;
cin >> n >> w;
vector<vector<int>> a(w + 1);
for (int i = 0; i < n; i++) {
int w, v;
cin >> w >> v;
a[w].push_back(v);
}
vector<LL> dp(w + 1, -inf);
dp[0] = 0;
auto f = [&](int k, int v) { return 1ll * k * v - k * k; };
auto get_val = [&](int k, int v) { return f(k, v) - f(k - 1, v); };
for (int i = 0; i <= w; i++) {
if (!a[i].empty()) {
vector<LL> dp2 = dp;
for (int j = 0; j <= w; j++) {
priority_queue<pair<LL, pair<int, int>>> q;
for (auto x : a[i]) {
q.push({get_val(1, x), {1, x}});
}
LL sum = 0;
for (int l = i; j + l <= w; l += i) {
auto [val, p] = q.top();
auto [k, v] = p;
q.pop();
sum += val;
dp2[j + l] = max(dp2[j + l], dp[j] + sum);
q.push({get_val(k + 1, v), {k + 1, v}});
}
}
dp.swap(dp2);
}
}
LL ans = *max_element(dp.begin(), dp.end());
cout << ans << '\n';
return 0;
}
G - No Cross Matching (abc373 G)
题目大意
二维平面,给定两组点\(p,q\)各\(n\)个,打乱 \(q\)的顺序,使得\(n\)个线段 \(p_i \to q_i\)互不相交。
给定一种 \(q\)的顺序或告知不可能。
解题思路
<++>
神奇的代码