AtCoder Beginner Contest 374

省流版

• A. 判断末三位即可
• B. 逐位判断即可
• C. 枚举所有分组情况即可
• D. 枚举线段顺序、端点顺序即可
• E. 二分答案，发现贵的机器数量不超过\(100\)，枚举求最小花费看是否可行即可
• F. 朴素DP，复杂度分析得到有效时刻不超过\(O(n^2)\)而非\(O(s_i)\)，直接\(DP\)即可

A - Takahashi san 2 (abc374 A)

题目大意

给定一个字符串，问结尾是不是san

解题思路

直接判断最后三个字母即可，python可以一行。

神奇的代码

print("Yes" if input().strip().endswith('san') else "No")

---

B - Unvarnished Report (abc374 B)

题目大意

给定两个字符串，问第一个字母不相同的次数。

解题思路

逐位判断即可。

python的想法，即先找出不同的位置，然后取最小值。

神奇的代码

a = input().strip()
b = input().strip()
if len(a) > len(b):a, b = b, a
if len(a) < len(b):a += ' ' * (len(b) - len(a))
pos = [i for i in range(len(a)) if a[i] != b[i]]
if not pos:print(0)
else:print(pos[0] + 1)

---

C - Separated Lunch (abc374 C)

题目大意

给定\(n\)个数字，分成两组，使得和最大值最小。

解题思路

\(n \leq 20\)，直接花 \(O(2^n)\)枚举分组情况，每种情况花 \(O(n)\)统计和，所有情况取最小值即可。总的时间复杂度为\(O(2^nn)\)。

神奇的代码

#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;cin >> n;vector<int> a(n);for (auto& x : a)cin >> x;int tot = accumulate(a.begin(), a.end(), 0);int up = (1 << n);int ans = 2e9 + 7;for (int i = 0; i < up; ++i) {int cnt = 0;for (int j = 0; j < n; ++j) {cnt += ((i >> j) & 1) * a[j];}ans = min(ans, max(cnt, tot - cnt));}cout << ans << '\n';return 0;
}

---

D - Laser Marking (abc374 D)

题目大意

二维平面，给定\(n\)个线段，用激光打印机打印。

激光移动速率为\(s\)，打印时的速率为 \(t\)。

规定打印顺序，使得耗时最短。初始激光位于\((0,0)\)。

解题思路

打印顺序，即规定打印线段的顺序，以及每个线段从哪个端点开始打印。

由于\(n \leq 6\)，因此花 \(O(n!)\)枚举顺序，花 \(O(2^n)\)枚举线段的打印端点，然后花 \(O(n)\)计算时间即可。

总的时间复杂度为\(O(n!2^nn)\)。

神奇的代码

#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, s, t;cin >> n >> s >> t;vector<array<int, 4>> a(n);for (auto& x : a) {cin >> x[0] >> x[1] >> x[2] >> x[3];}vector<int> id(n);iota(id.begin(), id.end(), 0);double ans = 1e9 + 7;int up = (1 << n);auto dist = [](int x, int y, int sx, int sy) -> double {return sqrt((x - sx) * (x - sx) + (y - sy) * (y - sy));};auto solve = [&](vector<int>& id, int dir) -> double {int x = 0, y = 0;double res = 0;for (auto& i : id) {auto [sx, sy, ex, ey] = a[i];if ((dir >> i) & 1) {swap(sx, ex);swap(sy, ey);}res += dist(x, y, sx, sy) / s;res += dist(sx, sy, ex, ey) / t;x = ex;y = ey;}return res;};do {for (int i = 0; i < up; i++) {ans = min(ans, solve(id, i));}} while (next_permutation(id.begin(), id.end()));cout << fixed << setprecision(10) << ans << '\n';return 0;
}

---

E - Sensor Optimization Dilemma 2 (abc374 E)

题目大意

制作产品，有\(n\)道工序。

每道工序有两种设备，单价 \(p_i\)和 \(q_i\)，一天可做 \(a_i\)和 \(b_i\)的产品。

最终的生产效率是所有工序的产品数量的最小值。

现有 \(x\)元，问生产效率的最大值。

解题思路

这题写的有点不明不白。

首先枚举这个最大值，然后看可不可行。容易发现生产效率越小越容易满足，越大越难满足，因此这个答案可以二分（典型的最小值最大）。

二分了生产效率\(m\)后，剩下的问题就是让每一个工序的产能都\(\geq m\)，且让花费最小。

这里只有两种机器，一个朴素的想法就是计算单位产能的价格，即 \(\frac{p_i}{a_i}\)和 \(\frac{q_i}{b_i}\)看看那个小，那我们肯定买小的那个。

但是会有个问题，如果我们只买小的，然后产能刚好 \(=m\)，此时肯定是最优策略。但如果产能 \(>m\)，此时满足了\(\geq m\)，但花费不见得是最小的：比如可以少买几个，多买另外的，使得产能刚好 \(=m\)，且花费比前面的还小（样例一就是个反例）。

假设 \(a_i\)的单价更低，上述考虑的是全买\(a_i\)的，但不一定是花费最小的，退而求其次，买一些 \(b_i\)来替换 \(a_i\)，那我应该买多少个\(b_i\)呢？

由于\(a_i, b_i \leq 100\)，比赛时就直接猜的 \(b_i\)的范围就是 \(1 \sim 100\)，再大的话完全可以又等价的\(a_i\)替换之类的。然后就过了。

现在细细想来，这里的问题即为\(a_i x + b_iy \geq m\)，找到一个最好的\((x,y)\)满足该不等式，且 \(p_i x + q_i y\)最小。\(x,y\)的范围都高达 \((10^7)\)，直接遍历不现实，但我们知道 \(x\)尽可能大是最好的，因此这里的 \(y\)的范围不会很大，但有多小呢？

假设\(y=0\)的情况，此时全买 \(a_i\)，最坏情况就是\(a_ix = m + a_i - 1\)，产量超了太多，现在想通过买一些\(b_i\)使得产量超标少一点，比如多一台\(b_i\)，少几台\(a_i\)，就能让超标量少 \(1\) ，这样\(b_i\)最多多买\(a_i-1\)台，就能调整产能刚刚好\(=m\)之类的。 因此\(y\)的范围最多就到 \(a_i\)。

神奇的代码

#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, x;cin >> n >> x;vector<array<int, 4>> a(n);for (auto& i : a) {cin >> i[0] >> i[1] >> i[2] >> i[3];}auto check = [&](int t) {LL sum = 0;for (auto& i : a) {auto [a, p, b, q] = i;if (1ll * p * b > 1ll * q * a)swap(a, b), swap(p, q);LL tmp = 1e9 + 7;for (int j = 0; j < a; ++j) {LL cost = 1ll * max(0, (t - j * b + a - 1) / a) * p + j * q;tmp = min(tmp, cost);}sum += tmp;}return sum <= x;};int l = 0, r = 1e9 + 8;while (l + 1 < r) { // [l,r)int mid = (l + r) / 2;if (check(mid))l = mid;elser = mid;}cout << l << '\n';return 0;
}

---

F - Shipping (abc374 F)

题目大意

\(n\)个单，第 \(i\)个单从 \(s_i\)时刻可以接。

一次最多接 \(k\)个单，接了后 \(x\)时刻之后才能再接。

一个单的不满意度为接单时刻与可接时刻的差，即\(t_i - s_i\)。

求最小的不满意度，

解题思路

这题难在复杂度分析。

朴素\(dp\)即 \(dp[i][j]\)表示前 \(i\)时刻，完成了前 \(j\)个单的最小不满意度。但这里时刻数高达\(10^{12}\)，不大行。

时刻数不能作为状态。但考虑上述状态，有非常多的显然不优的状态：我接单的时刻，只有两类：

• 我现在刚刚可以接单，就立刻接还在囤积的单。
• 或者我等等下一个单，然后一起接。

考虑这样的时刻数有多少：

• 第一类的时刻数，就是形如\(s_i + x + x + x...\)，但注意到每 \(+x\)，必定有一个囤积的单，如果没有囤积的单，那下一个时刻就是第二类的（某个\(s_j\)）。因此第一类的时刻数，对于每个 \(i\)来说只有\(O(n)\)个，即最多有\(n\)个\(+x\) 。因此总的时刻数就\(O(n^2)\)个。
• 第二类的时刻数，显然就是\(O(n)\)个。

所以，上述\(dp[i][j]\)中的 \(i\)，抛去显然不优的状态，剩下的只有 \(O(n^2)\)个需要考虑的状态，加之 \(j\)有\(O(n)\)状态，其状态数就是 \(O(n^3)\)，加之转移复杂度是\(O(k)\)，总的时间复杂度就是\(O(n^3k)\)。

转移考虑往后转移的方式，代码里，则为\(dp[i][j]\)表示完成前 \(i\)个单，此时时刻为 \(j\)的最小不满意度，因为\(j\)是离散的所以是个 \(map\)。然后枚举接下来完成的单的数量\(l\)，计算不满意度转移即可。计算不满意度即\(\sum t - s_i\)，可以用前缀和优化，或者枚举\(l\)时维护 \(\sum s_i\)。

标准写法500ms

#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, k, x;cin >> n >> k >> x;vector<LL> t(n);for (auto& i : t)cin >> i;vector<LL> sum(n);partial_sum(t.begin(), t.end(), sum.begin());vector<map<LL, LL>> dp(n + 1);dp[0][0] = 0;auto get_sum = [&](int l, int r) {if (l > r)return 0ll;return sum[r] - (l ? sum[l - 1] : 0);};for (int i = 0; i < n; ++i) {for (auto& [now, val] : dp[i]) {int st = i;for (int j = 1; j <= k && i + j <= n; ++j) {int ed = st + j;LL cur = max(now, t[ed - 1]);LL nxt = val + j * cur - get_sum(st, ed - 1);if (dp[i + j].count(cur + x)) {dp[i + j][cur + x] = min(dp[i + j][cur + x], nxt);} else {dp[i + j][cur + x] = nxt;}}}}LL ans = 1e18 + 7;for (auto& [_, val] : dp[n]) {ans = min(ans, val);}cout << ans << '\n';return 0;
}

下面的是比赛时写的，加了点小小的转移优化，省去了一些不必要的转移（即囤积的单肯定全部处理）。

赛场时写的稍加优化的1ms

#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, k, x;cin >> n >> k >> x;vector<LL> t(n);for (auto& i : t)cin >> i;vector<LL> sum(n);partial_sum(t.begin(), t.end(), sum.begin());vector<map<LL, LL>> dp(n + 1);dp[0][0] = 0;auto get_sum = [&](int l, int r) {if (l > r)return 0ll;return sum[r] - (l ? sum[l - 1] : 0);};for (int i = 0; i < n; ++i) {for (auto& [now, val] : dp[i]) {int st = i;int ed = upper_bound(t.begin(), t.end(), now) - t.begin(); // 囤积的单int cnt = max(1, ed - st);for (int j = min(k, cnt); j <= k && i + j <= n; ++j) { // 囤积的单肯定全部处理ed = st + j;LL cur = max(now, t[ed - 1]);LL nxt = val + j * cur - get_sum(st, ed - 1);if (dp[i + j].count(cur + x)) {dp[i + j][cur + x] = min(dp[i + j][cur + x], nxt);} else {dp[i + j][cur + x] = nxt;}}}}LL ans = 1e18 + 7;for (auto& [_, val] : dp[n]) {ans = min(ans, val);}cout << ans << '\n';return 0;
}

---

G - Only One Product Name (abc374 G)

题目大意

给定\(n\)个长度为 \(2\)的大写字符串，构造一个字符串列表，满足每个大写字符都作为子串出现在这列表里，且列表里每个字符串的 \(2\)字母子串都是这 \(n\)个字符串里的，即出现的都在子串里，子串里的都出现了。

解题思路

<++>

神奇的代码

---