AtCoder Beginner Contest 362
前言
vp 的时候出了四题，被 C 题卡了一会，很久才出，D 题是 dijkstra 的板子，改下条件即可，E 题是个计数 dp，这类题一直不怎么擅长，想起之前杭电第一场那个序列立方的题也是类似这种计数 dp，需要加强练习。
A - Buy a Pen (atcoder.jp)
思路
判断两两最小。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, c;
cin >> a >> b >> c;
string x;
cin >> x;
if (x == "Red") cout << min(b, c) << '\n';
if (x == "Blue") cout << min(a, b) << '\n';
if (x == "Green") cout << min(a, c) << '\n';
return 0;
}
B - Right Triangle (atcoder.jp)
思路
根据勾股定理判一下即可，这里坐标都很小，可以不用开方，开方的话还会涉及到精度问题。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct point {
i64 x;
i64 y;
} ;
//求两点之间的距离
i64 dis(point p1, point p2) {
return ((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
point a, b, c;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
i64 ab = dis(a, b);
i64 ac = dis(a, c);
i64 bc = dis(b, c);
if ((ab + ac == bc) || (ab + bc == ac) || (ac + bc == ab)) {
printf("Yes");
}
else {
printf("No");
}
return 0;
}
C - Sum = 0 (atcoder.jp)
思路
先累计两边边界的和，记为 \(sum_l\) 和 \(sum_r\) ，如果 \(sum_l>0\) 说明左边取全最小都还是不可能等于 0 ，右边同理，这种特殊处理一下即可。
考虑当 \(sum_l\le 0\) 的时候，那我们只要往右边偏移 \(|sum_l|\) 即可，把小于 0 的那部分用正数来补；右边同理。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
i64 lsum = 0, rsum = 0;
vector<array<i64, 2>> node(n);
for (auto &[x, y] : node) {
cin >> x >> y;
lsum += x, rsum += y;
}
if (lsum > 0 || rsum < 0) {
cout << "No\n";
return 0;
}
cout << "Yes\n";
if (lsum <= 0) {
i64 now = -lsum;
for (auto [x, y] : node) {
if (now) {
cout << min(x + now, y) << ' ';
now -= min(x + now, y) - x;
} else
cout << x << ' ';
}
} else {
i64 now = rsum;
for (auto [x, y] : node) {
if (now) {
cout << max(x, y - now) << ' ';
now -= y - max(y - now, x);
} else
cout << y << ' ';
}
}
return 0;
}
D - Shortest Path 3 (atcoder.jp)
思路
dijkstra 板子题，只要在判断条件那里增加一个 \(a_v\) 即可。
代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> a[i];
vector g(n + 1, vector<array<int, 2>>());
for (int i = 0; i < m; i ++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<i64> dis(n + 1, LLONG_MAX >> 1);
priority_queue<pair<i64, i64>, vector<pair<i64, i64>>, greater<>> Q;
dis[1] = a[1];
Q.push({dis[1], 1});
while (Q.size()) {
auto [_, u] = Q.top();
Q.pop();
if (dis[u] < _) continue;
for (auto [v, w] : g[u]) {
if (dis[v] > dis[u] + w + a[v]) {
dis[v] = dis[u] + w + a[v];
Q.push({dis[v], v});
}
}
}
for (int i = 2; i <= n; i ++)
cout << dis[i] << " \n"[i == n];
return 0;
}
E - Count Arithmetic Subsequences (atcoder.jp)
思路
考虑计数 dp。
设 \(dp_{i,j,k}\) 为长度为 i 的子序列末尾两项为 \(a_j\) 和 \(a_k\) 的方案数。
转移的时候可以枚举倒数第三项来转移：
\[dp_{len,j,k} = dp_{len,j,k}+\sum\limits_{i=len-2}^{j-1}dp_{len-1,i,j}[a_j-a_i=a_k-a_j] \]代码
// LUOGU_RID: 169183095
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr i64 mod = 998244353, N = 300;
i64 dp[N][N][N] {};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> a[i];
if (n == 1) {
cout << 1 << '\n';
return 0;
}
vector<int> ans(n + 1);
ans[1] = n, ans[2] = n * (n - 1) / 2;
for (int i = 1; i <= n; i ++) {
for (int j = i + 1; j <= n; j ++) {
dp[2][i][j] = 1;
}
}
for (int len = 3; len <= n; len ++) {
for (int j = len - 1; j <= n; j ++) {
for (int k = j + 1; k <= n; k ++) {
for (int i = len - 2; i < j; i ++) {
if (a[j] - a[i] == a[k] - a[j]) {
(dp[len][j][k] += dp[len - 1][i][j]) %= mod;
}
}
(ans[len] += dp[len][j][k]) %= mod;
}
}
}
for (int i = 1; i <= n; i ++)
cout << ans[i] << " \n"[i == n];
return 0;
}