AtCoder Beginner Contest 376
省流版
- A. 记录上次发糖时间，依题意模拟判断即可
- B. 移动策略唯一，模拟移动即可
- C. 二分箱子大小，从小到大依次判断能否放入即可
- D. 分别从点\(1\)通过正反向边到达点\(i\)的距离最小值，正反边分别\(BFS\)求距离最小值即可。
- E. 枚举\(\max a_i\)，用优先队列维护满足 \(a_j \leq a_i\) 的前\(b_j\)小的和即可
- F. 注意每执行完一条指令后只有一个棋子情况数有\(O(n)\)，因此直接 \(dp[i][j]\)表示执行完前 \(i\)条指令，另一个棋子位于 \(j\)的最小移动次数，根据前后两个指令移动的棋子是否相同，转移分别考虑顺指针移动或逆时针移动对另一个棋子的位置影响和代价即可
A - Candy Button (abc376 A)
题目大意
一个按钮，按了会发糖。
给定多次按的时间。如果这次按的时间距离上次发糖时间超过了\(c\)，则发个糖。
问发的糖数量。
解题思路
记录上次发糖的时间，然后判断此次按按钮的时间是否和上次距离超过\(c\)即可。
神奇的代码
#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, c;
cin >> n >> c;
int la = -c;
int ans = 0;
while (n--) {
int x;
cin >> x;
if (x - la >= c) {
ans++;
la = x;
}
}
cout << ans << '\n';
return 0;
}
B - Hands on Ring (Easy) (abc376 B)
题目大意
\(n\)的环形格子。两个棋子，初始位于\(0,1\)。
给定 \(q\)个指令，每个指令指定一个棋子移动到某个格子上，期间不能移动另外一个棋子。
依次执行这些指令，问移动的次数。
解题思路
模拟即可，一个棋子只能顺时针或逆时针移动，其中一个方向会撞到另一个棋子而不能移动，因此每次只有一个方向可以移动。
直接模拟两次移动，其时间复杂度为\(O(n^2q)\)，同样可过。或者移动前判断某个方向会不会撞到另一个棋子，其时间复杂度为\(O(nq)\)。
代码里判断的是顺时针是否会遇到另一个棋子\(b\)。虽然有环会导致判断困难，但可以这么想：
因为是顺时针，格子标号不断递增，因此保持\(s < t\)（如果\(t < s\)则令 \(t = t + n\)），然后看 \(b\)或者 \(b-n\)或者 \(b+n\)是否在 \([s,t]\)中间，即可知道\(s \to t\)会经过\(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 n, q;
cin >> n >> q;
int l = 0, r = 1;
int ans = 0;
auto inner = [](int l, int m, int r) { return l < m && m < r; };
auto step = [&](int s, int t, int b) {
if (s == t)
return 0;
if (s > t)
t += n;
if (inner(s, b, t) || inner(s, b + n, t))
return n - (t - s);
else
return t - s;
};
while (q--) {
string s;
int p;
cin >> s >> p;
--p;
if (s[0] == 'L') {
ans += step(l, p, r);
l = p;
} else {
ans += step(r, p, l);
r = p;
}
}
cout << ans << '\n';
return 0;
}
C - Prepare Another Box (abc376 C)
题目大意
给定\(n\)个球的大小和 \(n-1\)个箱子的大小。现买一箱子，要求尺寸最小，使得 \(n\)个球恰好可以放进 \(n\)个箱子里。
解题思路
容易发现，如果我们已知了最后一个箱子的尺寸，我们很容易判断能否恰好放进：对球和箱子的尺寸从小到大排序，然后看是否一一放进去即可。
但此处就是要求其尺寸的最小值，可以枚举，但很显然，最后一个箱子越大，可以放进它的球越多，要求越容易满足，反之越小的时候，越难满足。所以箱子尺寸与是否可行具有单调性。
因此二分最后一个箱子的尺寸，然后\(O(n\log n)\)判断是否可行即可。
神奇的代码
#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> a(n), b(n);
for (auto& i : a)
cin >> i;
for (int i = 0; i < n - 1; ++i)
cin >> b[i];
int l = 0, r = inf;
sort(a.begin(), a.end());
auto check = [&](int x) {
auto bb = b;
bb.back() = x;
sort(bb.begin(), bb.end());
for (int i = 0; i < n; ++i)
if (a[i] > bb[i])
return false;
return true;
};
while (l + 1 < r) { // (l, r]
int mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid;
}
if (r == inf)
r = -1;
cout << r << '\n';
return 0;
}
D - Cycle (abc376 D)
题目大意
给定一张有向图，问包含点\(1\)的环的最小环点数。
解题思路
想的时候脑子有点不清醒，其经历为：
- 直接从点\(1\) \(DFS\)，发现 \(T\)了，思索下发现是环套环的情况会退化成 \(O(n^2)\)。
- 退化的原因是一个点被重复访问了，避免重复访问，记录了 \(dis[i]\)表示第一次从点 \(i\)回到点 \(1\)的距离，发现 \(wa\)了，思索下 发现是第一次记录的值不一定是最小值
- 要确保最小值，只好改成\(BFS\)，但其 \(dis[i]\)是 \(1 \to i\)的，我还需要一个 \(dis[i] \to 1\)的，发现该距离就是反向边的结果，因此就正反方向从\(1\)开始 各\(BFS\)一次即可。
包含点\(1\)的环可以看成是 从点\(1\)出发，正向边和反向边到达同一个点所组成的路径。
因此从点 \(1\)分别沿正向边和反向边求出 \(dis[i]\)和\(dis2[i]\)表示 \(1 \to i\)的正向边和反向边长度 ，答案就是\(\min_i dis[i] + dis2[i]\)。
神奇的代码
#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, m;
cin >> n >> m;
vector<vector<int>> edge(n);
vector<vector<int>> edge2(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
edge[u].push_back(v);
edge2[v].push_back(u);
}
int ans = inf;
int cnt = 0;
auto BFS = [&](int st, vector<vector<int>>& e) {
queue<int> team;
vector<int> dis(n, inf);
dis[st] = 0;
team.push(st);
while (!team.empty()) {
auto u = team.front();
team.pop();
for (auto& v : e[u]) {
if (dis[v] > dis[u] + 1) {
team.push(v);
dis[v] = dis[u] + 1;
}
}
}
return dis;
};
auto dis = BFS(0, edge);
auto dis2 = BFS(0, edge2);
for (int i = 1; i < n; ++i) {
ans = min(ans, dis[i] + dis2[i]);
}
if (ans == inf)
ans = -1;
cout << ans << '\n';
return 0;
}
E - Max × Sum (abc376 E)
题目大意
给定两个数组\(a,b\)，求一个大小为 \(k\)的集合下表 \(S\)，使得 \(\max_{i \in S} a_i + \sum_{i \in S} b_i\)最小。
解题思路
枚举\(a_i\)，剩下的问题就是找满足 \(a_j \leq a_i\)的前 \(k-1\)小的 \(b_j\)的和。
首先对数组\(a\)从小到大排序，数组 \(b\)也跟着变动。
然后依次枚举 \(a_i\)，此即为\(\max_{i \in S} a_i\)。然后找\(1 \leq j \leq i\)中最小的 \(k-1\)个 \(b_i\)。
考虑如何维护前 \(k-1\)小的和，因为会有不断的 \(b_i\)加入，会不断淘汰较大的 \(b_i\)，因此可以用优先队列维护这些 \(b_i\)。
在优先队列不断 push,pop时维护其里面的值的和即可。其时间复杂度为\(O(n\log n)\)。
注意枚举 \(a_i\)时， \(b_i\)是一定要选的，因此要从优先队列里求出前 \(k-1\)小的和（但第 \(k\)小的不能丢弃，它可能比 \(b_i\)小，只是因为此时 \(b_i\)必选，因而暂时不能选它）。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL inf = 1e18 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n), id(n);
for (auto& i : a)
cin >> i;
for (auto& i : b)
cin >> i;
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y) { return a[x] < a[y]; });
priority_queue<int> pq;
LL sum = 0;
LL ans = inf;
for (int j = 0; j < n; ++j) {
int i = id[j];
while (pq.size() > k) {
sum -= pq.top();
pq.pop();
}
if (j >= k - 1) {
int del = (j >= k ? pq.top() : 0);
ans = min(ans, 1ll * a[i] * (sum - del + b[i]));
}
pq.push(b[i]);
sum += b[i];
}
cout << ans << '\n';
}
return 0;
}
F - Hands on Ring (Hard) (abc376 F)
题目大意
\(n\)的环形格子。两个棋子，初始位于\(0,1\)。
给定 \(q\)个指令，每个指令指定一个棋子移动到某个格子上，期间可以移动另外一个棋子。
依次执行这些指令，问最小的移动次数。
解题思路
朴素\(dp\)即为 \(dp[i][j][k]\)表示执行了前 \(i\)个指令后，两个棋子的位置分别为\(j,k\)的最小移动次数。
但其时间复杂度为 \(O(qn^2)\)，由于 \(n,q \leq 3000\)，不能通过。
但注意到，当执行完第\(i\)个指令时，其中一个棋子的位置是一定是刚刚移动到的位置（情况数为\(1\)），只是另一个棋子的位置 不确定，情况数为\(O(n)\)。因此实际上状态数就只有 \(O(qn)\)，转移可以 \(O(1)\)，因此可以通过了。只是实现有一点点思维细节。
设 \(dp[i][j]\)表示执行完前 \(i\)个指令后，另一个棋子（如果第\(i\)条指令移动的是 L，则另一个棋子为R，反之为L）位于 \(j\)时的最小移动次数。
然后\(dp[i] \to dp[i + 1]\)时，设第\(i\)个指令移动的位置是 \(lp\)，第 \(i+1\)个指令移动的位置是 \(p\) ，考虑第\(i\)个指令和第 \(i+1\)个指令移动的是否是同一个棋子。
如果是同一个棋子：
- 在第\(i\)个指令时，当前移动棋子\(a\)，另一个棋子 \(b\)（即\(j\)位置所指的棋子）。
- 在第\(i+1\)个指令时，当前移动棋子\(a\)，另一个棋子 \(b\)（即\(j\)位置所指的棋子）。
- 此时计算\(dp[i+1]\)，枚举\(dp[i][j]\)的\(j\)，这是棋子\(b\)的位置。考虑转移，即 棋子\(a\)从 \(lp \to p\)，转移方式有两种：顺时针和逆时针，分别考虑这两个方向的代价和对棋子 \(b\)位置\(j\)的影响，转移即可。
如果不是同一个棋子：
- 在第\(i\)个指令时，当前移动棋子\(b\)，另一个棋子 \(a\)（即\(j\)位置所指的棋子）。
- 在第\(i+1\)个指令时，当前移动棋子\(a\)，另一个棋子 \(b\)（即\(j\)位置所指的棋子）。
- 此时计算\(dp[i+1]\)，枚举\(dp[i][j]\)的\(j\)，这是棋子\(a\)的位置。考虑转移，即 棋子\(a\)从 \(j \to p\)，转移方式有两种：顺时针和逆时针，分别考虑这两个方向的代价和对棋子 \(b\)位置的\(lp\)影响，转移即可。
对于转移方式的计算，就是三个参数\(s \to t\)，对 \(b\)的影响，返回棋子 \(b\)的位置和总代价。
- 顺时针 \(s \to t\)，位置标号不断增大，因此若 \(t < s\)，则令 \(t += n\)，然后看 \(b - n, b, b + n\)是否有一个落在 \([s, t]\)范围内，有则最终 \(b\)的位置会变成 \(t+1\)。 然后计算两个棋子移动的距离即可。注意计算其距离时要将\(b\)修正在 \([s,t]\)的范围内。
- 逆时针 \(s \to t\)，位置标号不断减小，因此若 \(t > s\)，则令 \(t -= n\)，然后看 \(b - n, b, b + n\)是否有一个落在 \([t, s]\)范围内，有则最终 \(b\)的位置会变成 \(t-1\)。 然后计算两个棋子移动的距离即可。注意计算其距离时要将\(b\)修正在 \([t,s]\)的范围内。
神奇的代码
#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, q;
cin >> n >> q;
vector<int> dp(n, inf);
char cur = 'L';
int lp = 0;
dp[1] = 0;
auto inner = [](int l, int m, int r) { return l <= m && m <= r; };
auto shun = [&](int s, int t, int b) {
if (s == t)
return make_pair(b, 0);
if (s > t)
t += n;
if (inner(s, b - n, t) || inner(s, b, t) || inner(s, b + n, t)) {
if (inner(s, b - n, t))
b -= n;
else if (inner(s, b + n, t))
b += n;
int cost = t - s + t + 1 - b;
int pos = (t + 1) % n;
return make_pair(pos, cost);
} else {
return make_pair(b, t - s);
}
};
auto ni = [&](int s, int t, int b) {
if (s == t)
return make_pair(b, 0);
if (s < t)
t -= n;
if (inner(t, b - n, s) || inner(t, b, s) || inner(t, b + n, s)) {
if (inner(t, b - n, s))
b -= n;
else if (inner(t, b + n, s))
b += n;
int cost = s - t + b - (t - 1);
int pos = (t - 1 + n) % n;
return make_pair(pos, cost);
} else {
return make_pair(b, s - t);
}
};
while (q--) {
string s;
int p;
cin >> s >> p;
--p;
vector<int> dp2(n, inf);
if (s[0] == cur) {
for (int i = 0; i < n; ++i) {
auto [nxt, cost] = shun(lp, p, i);
dp2[nxt] = min(dp2[nxt], dp[i] + cost);
auto [nxt2, cost2] = ni(lp, p, i);
dp2[nxt2] = min(dp2[nxt2], dp[i] + cost2);
}
} else {
for (int i = 0; i < n; ++i) {
auto [nxt, cost] = shun(i, p, lp);
dp2[nxt] = min(dp2[nxt], dp[i] + cost);
auto [nxt2, cost2] = ni(i, p, lp);
dp2[nxt2] = min(dp2[nxt2], dp[i] + cost2);
}
}
cur = s[0];
lp = p;
dp2.swap(dp);
}
cout << *min_element(dp.begin(), dp.end()) << '\n';
return 0;
}
G - Treasure Hunting (abc376 G)
题目大意
给定一棵\(n+1\)个点的有根树。根为\(0\)号点。
\(1 \sim n\)个点中有一个点有宝藏，给定 \(a_i\)，表示第 \(i\)个点有宝藏的概率为 \(\frac{a_i}{\sum a_i}\)。
点有已探索和未探索两个状态。初始点\(0\)为 已探索，其余点为未探索。
每次，可选择一个未探索的点，且其父亲为已探索的点，探索该点。一旦探到宝藏即停下。
由于宝箱位置不固定，求一个最佳策略，该策略在所有情况的探索点的期望值最小。
即求策略\(f\)，记 \(f(x)\)表示如果宝箱位于点 \(x\)，该策略需要探索 \(f(x)\)个点才能探到位于点 \(x\)的宝箱。
最小化 \(\sum_{1 \leq i \leq n}\frac{a_i}{\sum a_i} f(i)\)
解题思路
<++>
神奇的代码