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\)个字符串里的,即出现的都在子串里,子串里的都出现了。

解题思路

<++>

神奇的代码