本文主要是介绍AtCoder Beginner Contest 369 ABCDE，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
背景
无
A题：369
思路
假设A<=B
分类讨论，有如下两种情况
1.A==B，情况唯一，另外一个数只能取A
2.A<B，首先我们可以以B-A为公差d构造，另外一个数可以取A-d或者B+d。（然后接着考虑放在A和B中间的情况，样例中给了，只要B-A为偶数即可）
代码
inline void solve() {int a, b; cin >> a >> b;if (a > b) swap(a, b);if (a == b) cout << 1 << endl;else cout << 2 + ((b - a) % 2 == 0) << endl;return;
}B题：Piano 3
思路
这个是一步一步操作的，所以说左手和右手一定是放在第一次进行对应手操作的位置上的。
按题意模拟即可
代码
inline void solve() {int n; cin >> n;int ans = 0;int l = -1, r = -1;for (int i = 1; i <= n; i ++ ) {int x; char op; cin >> x >> op;if (op == 'L') {if (l != -1) ans += abs(l - x);l = x;}else {if (r != -1) ans += abs(r - x);r = x;}}cout << ans << endl;return;
}C题：Count Arithmetic Subarrays
思路
双指针
为什么：
因为对于一个等差数列区间，我们可以用双指针进行维护，并且等差区间内部也是等差的。如果在某一个点不满足等差条件的话，那么对于这个点的右边的所有点都无法算到这个等差数列区间去了。
3 6 9 3 1 1 1
这个我们只能找到3 6 9，后面那个3无法加入到前面的等差区间，所以后面的也不行。“等差区间内部也是等差的”，所以我们可以直接O(n)进行计算
怎么做：定义j为1，i从2开始遍历
一开始我们可以找到3 6 9，看上面的样例，这个对答案的贡献为3+2+1-1。为什么要减去一呢？要去重。（这点可以结合代码进行理解）之后我们将j移到9的位置上（因为9也可能作为等差区间的开头），i继续进行遍历即可。
代码
inline void solve() {int n; cin >> n;vector<ll> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];int j = 1;ll ans = 0;for (int i = 2; i <= n; i ++ ) {if (a[i] - a[i - 1] != a[j + 1] - a[j]) {ll len = i - j;ans += (1 + len) * len / 2 - 1;j = i - 1;}}ll len = n + 1 - j;ans += (1 + len) * len / 2;cout << ans << endl;return;
}D题：Bonus EXP
思路
可打可不打么？两种选择，一眼dp
我定义的是dp[N][2]，其中dp[i][1]代表着前i个怪兽打奇数次的最大exp，同理dp[i][0]对应偶数次
转移方程（很容易想到）
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i])--不打或者打
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + 2 * a[i])--不打或者打
其中要注意，偶数次的转移必须满足i>=2
你这只少要打两次才能双倍经验吧
代码
const int N = 2e5 + 9;
ll dp[N][2];
inline void solve() {int n; cin >> n;for (int i = 1; i <= n; i ++ ) {ll x; cin >> x;dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + x);if (i >= 2) dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + 2 * x);}cout << max(dp[n][0], dp[n][1]) << endl;return;
}E题：Sightseeing Tour
思路
暴力枚举
它这题目到底什么意思呢？
要求你必须走这k条边
你一开始从1出发，要经过这k条边，然后到达点n
那就只是思考这k条边怎么走的问题了，首先枚举顺序，接着枚举从那边进那边出即可（这步可以直接暴力实现，k<=5）
这样我们的路径上就必定会经过这k条边，我们一次将其“连起来即可”
连起来的操作我们用从几号点到几号点的最小距离即可(Floyd)
代码
ll d[410][410];
inline void solve() {int n, m; cin >> n >> m;memset(d, 63, sizeof d);for (int i = 1; i <= n; i ++ ) d[i][i] = 0;vector<array<ll, 3>> a(m + 1);for (int i = 1; i <= m; i ++ ) {ll u, v, t; cin >> u >> v >> t;a[i] = {u, v, t};d[u][v] = d[v][u] = min(d[v][u], t);}for (int k = 1; k <= n; k ++ ) {for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= n; j ++ ) {d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}int q; cin >> q;while (q -- ) {int k; cin >> k;vector<int> b(k + 1);ll ans = 0, add = (ll)1e18;for (int i = 1; i <= k; i ++ ) cin >> b[i], ans += a[b[i]][2];do {for (int i = 0; i < (1 << k); i ++ ) {ll extra = 0, last = 1;for (int j = 1; j <= k; j ++ ) {int st = a[b[j]][0], ed = a[b[j]][1];if (i >> (j - 1) & 1) swap(st, ed);extra += d[st][last];last = ed;}extra += d[last][n];add = min(add, extra);}}while (next_permutation(b.begin() + 1, b.end()));cout << ans + add << endl;}return;
}
这篇关于AtCoder Beginner Contest 369 ABCDE的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
