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;
else
r = 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\)个字符串里的，即出现的都在子串里，子串里的都出现了。
解题思路
<++>
神奇的代码