A - Leyland Number (abc320 A)
题目大意
给定\(a,b\)，输出 \(a^b + b^a\)。
解题思路
因为数不超过\(10\)，可以直接用 pow计算然后转成\(int\)。不会有精度损失。
神奇的代码
#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 a, b;
cin >> a >> b;
cout << int(pow(a, b) + pow(b, a)) << '\n';
return 0;
}
B - Longest Palindrome (abc320 B)
题目大意
给定一个字符串\(s\)，求长度最长的回文串。
解题思路
因为长度只有\(100\)，可以直接枚举子串，然后暴力判断是不是回文串（翻转后是否和自身相同），复杂度为 \(O(n^3)\)。
数据范围大的话可以用Manachar算法\(O(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);
string s;
cin >> s;
int ans = 0;
auto ok = [&](int l, int r) {
string a = s.substr(l, r - l + 1);
string b = a;
reverse(b.begin(), b.end());
return a == b;
};
for (int i = 0; i < s.size(); ++i)
for (int j = i; j < s.size(); ++j) {
if (ok(i, j))
ans = max(ans, j - i + 1);
}
cout << ans << '\n';
return 0;
}
C - Slot Strategy 2 (Easy) (abc320 C)
题目大意
给定\(n=3\)排灯，以及三个长度都为\(m\)的数字串，表示每一时刻，每盏灯依次循环地显示这些数字。
对于某一时刻，你最多只能按一个按钮，从而让一盏灯停下来。当然你可以什么都不操作。
问最终让三盏灯停下来时显示的数字都一样，需要的最短时间。
解题思路
考虑最朴素的做法，首先枚举最终情况下，显示的数字是什么，有\(10\)种情况。
然后考虑这三排灯按按钮的顺序，同样枚举这个顺序，有 \(3!\)种情况。
确定了数字和按按钮的顺序，剩下的就是模拟，只看一盏灯，然后出现这个数字时就按按钮，时间复杂度是 \(O(m)\)。
最终的时间复杂度是\(O(n! \times 10nm)\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m;
cin >> m;
array<string, 3> s;
for (auto& i : s)
cin >> i;
int ans = 1e9;
for (int i = 0; i <= 9; ++i) {
array<int, 3> id{};
iota(id.begin(), id.end(), 0);
do {
int cur = 0;
int tot = 0;
for (auto& j : id) {
if (s[j].find(i + '0') == string::npos) {
tot = inf;
break;
}
while (s[j][cur] - '0' != i) {
cur = (cur + 1) % m;
++tot;
}
cur = (cur + 1) % m;
++tot;
}
ans = min(ans, tot);
} while (next_permutation(id.begin(), id.end()));
}
if (ans == inf)
ans = 0;
cout << ans - 1 << '\n';
return 0;
}
D - Relative Position (abc320 D)
题目大意
二维平面，有\(n\)个人，其中第一个人在原点。
给定 \(m\)条信息 \((a,b,x,y)\)，表示第 \(b\)个人的位置是 \(a_x + x, a_y + y\)。其中\(a_x,a_y\)表示第 \(a\)个人的位置。
问每个人的位置，或告知不确定。
解题思路
初始只有第一个人的位置确定。那么所有与第一个人相关的信息的其他人的位置都能确定。
有更多的人的位置确定了，那么与这些人相关的信息的更多的人的位置都可以确定。
这感觉上就像是一个关系网，从第一个人往外传播，遍及到能遍及到的人。
这就是一张图，我们根据这些信息建立一张无向图，然后从\(1\)号点开始 \(BFS\)，确定中间每个人的位置。
未遍历到的点就是位置不确定的人。
神奇的代码
#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, 3>>> edge(n);
for (int i = 0; i < m; ++i) {
int a, b, x, y;
cin >> a >> b >> x >> y;
--a, --b;
edge[a].push_back({b, x, y});
edge[b].push_back({a, -x, -y});
}
queue<int> team;
vector<int> ok(n);
vector<array<LL, 2>> pos(n, {0, 0});
ok[0] = 1;
team.push(0);
while (!team.empty()) {
auto u = team.front();
team.pop();
for (auto& [v, x, y] : edge[u]) {
if (!ok[v]) {
pos[v] = {pos[u][0] + x, pos[u][1] + y};
ok[v] = 1;
team.push(v);
}
}
}
for (int i = 0; i < n; ++i) {
if (ok[i])
cout << pos[i][0] << ' ' << pos[i][1] << '\n';
else
cout << "undecidable" << '\n';
}
return 0;
}
E - Somen Nagashi (abc320 E)
题目大意
给定\(n\)个人，从左到右。
有 \(q\)个事件，每个事件形如 \((t, w, s)\)，表示第 \(t\)时刻，当前最左边的人可以获得 \(w\)的分数，然后离开，直到 \(t+s\)时刻回来。
问最后每个人的分数。
解题思路
朴素的思想就是每一时刻迭代，但时刻高达\(10^9\)。注意到有很多时刻都是无事发生的，因此我们只用考虑有事件发生的，即有人离开和有人回来。
问题需要维护两个信息，一个是最左边的人的标号（就是当前最小的标号），以及何时会有人回来这一事件的发生。
注意到每次都是剔除标号最小的人，以及获取的标号最小的人，因此可以用一个优先队列维护当前还在的人的标号，是个小根堆。
至于维护有人何时会回来这一事件，注意到这个事件是有一个发生时间\(t+s\)，而我们是按照时间流逝依次处理的，因此我们可以用另一个优先队列维护这些时间，这样就可以动态插入新的事件，通过时间从小到大排序，以及当前时刻就能判断事件是否发生。
两个优先队列模拟这个过程即可。
神奇的代码
#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;
priority_queue<int> team;
for (int i = 0; i < n; ++i)
team.push(-i);
priority_queue<array<int, 2>> event;
vector<LL> ans(n);
for (int i = 0; i < m; ++i) {
int t, w, s;
cin >> t >> w >> s;
while (!event.empty() && -event.top()[0] <= t) {
auto [_, u] = event.top();
event.pop();
team.push(-u);
}
if (!team.empty()) {
int u = -team.top();
team.pop();
ans[u] += w;
event.push({-(t + s), u});
}
}
for (auto& i : ans)
cout << i << '\n';
return 0;
}
F - Fuel Round Trip (abc320 F)
题目大意
一维数轴，从\(0\)出发到 \(x_n\)，再折返回来。
开车，油箱容量 \(h\)，一距离消耗一单位汽油，有 \(n-1\)个加油站 ，对于第\(i\)个加油站，其位于 \(x_i\)，可花\(p_i\)元加油 \(f_i\)单位汽油，但不能超过\(h\)，超过部分则不要了，且花费价格不变 。
问出发再折返回来，消耗的最小钱数。注意一个加油站只能使用一次，这意味着如果过去用了，折返回来时不能再用了。
解题思路
本题有几个特别的地方，一个是油箱有上限，一个是加油是全加，另一个是有折返，加油站只能用一次。
如果没有加油站只能用一次的情况，注意到\(n\)和 \(h\)只有 \(300\)。
考虑爆搜时的状态信息，我们可以保留 \(dp[i][j]\)表示到达第 \(i\)个加油站，此时还剩下 \(j\)升汽油的最小花费。然后枚举在第 \(i-1\) 个加油站时的汽油状态，考虑当前加油站是否加油，转移即可。
但是这个状态在返程时会有问题，因为对于第\(i\)个加油站能否加油，取决于去时是否加油，但这在状态里，这一信息没有保留下来。而记录每个加油站的使用状态，这是个指数级的状态，不行。
考虑棘手的地方，就是返程时到达了第\(i\)个加油站，此时无法做决策，因为我不知道来时，在第 \(i\)个加油站的状态。而如果我能一次就考虑第\(i\)个加油站，来回这两次的加油状态，就不会有上述问题。
思考如何一次就能考虑来回两次的状态 ：即来时到达第\(i\)个加油站，此时有一个油箱量，回时到达第 \(i\)个加油站 ，也有一个油箱量。
设\(dp[i][j][k]\)表示从\(i\)个加油站 出发，此时油箱量为\(j\)，回来时油箱量为 \(k\)的最小费用。发现可以转移，枚举第\(i+1\)个加油站时的状态，以及考虑当前加油站来回时是否加油即可。
最后答案就是 \(dp[0][h][*]\)的最小值。初始条件为 \(dp[n][i][i] = 0\)，其余为无穷大。
上述是 \(dp\)的整体方向，下述是一些实现细节，主要是由于油箱的上限和时间复杂度的优化。
代码里第一维是压缩掉了，实际维护的 \(dp[i][j][k][0/1]\)表示，在第 \(i\)个加油站，出发时 油箱量为\(j\)，回来时为 \(k\)，且回来时没加油/加了油的最小费用。注意这里的油箱量都是加油前的量，比如我选择出发时加了油，那么实际我转移时，容量起始为 \(min(j + f, h)\)，如果我选择回来时加了油，那么实际转移时，容量起始为 \(min(k + f, h)\)。
循环枚举的 \(j\)是从第 \(i\)个加油站出发时的油量， \(k\)是从第 \(i+1\)个加油站回来时的油量。
这样在转移时直接通过路程来计算 去到\(i+1\)时 油量和回到\(i\)时的油量，不然如果枚举的都是第 \(i\)个加油站的状态的话，如果回来时加油了，且 \(k\)为 \(h\)，要从\(i+1\)转移过来，这要考虑它的加油前的状态 ，分别有\(h, h - 1, h - 2, ..., h - f\)，这又会有 \(O(h)\)的状态要枚举。
新增的 \(0/1\)状态也是为了能够转移而加上的。
于是代码看着就比较复杂了（但是大方向是上述的三维\(dp\)，应该会有更优美的实现方式。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, h;
cin >> n >> h;
vector<int> pos(n + 1, 0);
for (int i = 1; i <= n; ++i)
cin >> pos[i];
vector<array<int, 2>> info(n + 1, {0, 0});
for (int i = 1; i < n; ++i) {
cin >> info[i][0] >> info[i][1];
}
vector<vector<array<int, 2>>> dp(h + 1,
vector<array<int, 2>>(h + 1, {inf, inf}));
for (int i = 0; i <= h; ++i)
dp[i][i][0] = 0;
for (int i = n - 1; i >= 0; --i) {
vector<vector<array<int, 2>>> dp2(
h + 1, vector<array<int, 2>>(h + 1, {inf, inf}));
int dis = pos[i + 1] - pos[i];
auto [p, f] = info[i];
auto [np, nf] = info[i + 1];
for (int j = 0; j <= h; ++j) {
for (int k = 0; k <= h; ++k) {
if (j - dis >= 0 && k - dis >= 0)
dp2[j][k - dis][0] =
min(dp2[j][k - dis][0], dp[j - dis][k][0]);
if (j - dis >= 0 && min(k + nf, h) - dis >= 0)
dp2[j][min(k + nf, h) - dis][0] =
min(dp2[j][min(k + nf, h) - dis][0], dp[j - dis][k][1]);
if (min(j + f, h) - dis >= 0 && k - dis >= 0)
dp2[j][k - dis][0] = min(dp2[j][k - dis][0],
dp[min(j + f, h) - dis][k][0] + p);
if (min(j + f, h) - dis >= 0 && min(k + nf, h) - dis >= 0)
dp2[j][min(k + nf, h) - dis][0] =
min(dp2[j][min(k + nf, h) - dis][0],
dp[min(j + f, h) - dis][k][1] + p);
if (j - dis >= 0 && k - dis >= 0)
dp2[j][k - dis][1] =
min(dp2[j][k - dis][1], dp[j - dis][k][0] + p);
if (j - dis >= 0 && min(k + nf, h) - dis >= 0)
dp2[j][min(k + nf, h) - dis][1] = min(
dp2[j][min(k + nf, h) - dis][1], dp[j - dis][k][1] + p);
}
}
dp.swap(dp2);
}
int ans = inf;
for (int i = 0; i <= h; ++i)
ans = min(ans, dp[h][i][0]);
if (ans == inf)
ans = -1;
cout << ans << '\n';
return 0;
}
G - Slot Strategy 2 (Hard) (abc320 G)
题目大意
给定\(n\)排灯，以及长度都为\(m\)的数字串，表示每一时刻，每盏灯依次循环地显示这些数字。
对于某一时刻，你最多只能按一个按钮，从而让一盏灯停下来。当然你可以什么都不操作。
问最终让\(n\)盏灯停下来时显示的数字都一样，需要的最短时间。
解题思路
<++>
神奇的代码
- Beginner AtCoder Contest 320beginner atcoder contest 320 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310