AtCoder Beginner Contest 319 -526互联

A - Legendary Players (abc319 A)

题目大意

给定rating前10的选手名字和对应分数。

给定名字，问对应分数。

解题思路

复制一下，建个数组，然后一个一个判断即可。Python更好写一点。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

vector<string> s = {"tourist 3858",   "ksun48 3679",  "Benq 3658",
                    "Um_nik 3648",    "apiad 3638",   "Stonefeang 3630",
                    "ecnerwala 3613", "mnbvmar 3555", "newbiedmy 3516",
                    "semiexp 3481"};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string t;
    cin >> t;
    for (auto& i : s) {
        int spa = i.find(' ');
        if (t == i.substr(0, spa))
            cout << i.substr(spa + 1) << '\n';
    }

    return 0;
}

B - Measure (abc319 B)

题目大意

给定\(n\)，生成一个长度为 \(n+1\)的字符串 \(s\)，其中 \(s_i\)（\(i\)从 \(0\)开始）为 \(1 \sim 9\)中最小的\(j\)使得\(i\)是 \(\frac{n}{j}\)倍数的 \(j\)。不存在则为\(-\)

解题思路

按照题意，枚举每个\(i\)，再枚举每个 \(j\)，看是否符合倍数要求即可。

神奇的代码

#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;
    for (int i = 0; i <= n; ++i) {
        int j = 1;
        for (; j < 10; ++j) {
            if (n % j == 0 && i % (n / j) == 0)
                break;
        }
        if (j < 10)
            cout << j;
        else
            cout << '-';
    }

    return 0;
}

C - False Hope (abc319 C)

题目大意

给定一个\(3 \times 3\)的矩阵，然后以随机顺序看这 \(9\)个数。问一个事件的发生概率。使得某一行或某一列或某一对角线中，优先看到的两个数是相同的，且不同于第三个数。

解题思路

因为只有\(9\)，我们可以花 \(O(9!)\)枚举看的顺序，然后对于每个顺序，我们依次判断每一行、每一列、每一对角线看到的三个数字的顺序是否符合上述要求，累计事件发生的情况即可。

代码里其实是枚举的每个位置是第几次看到的，然后对于第一行的三个位置，就根据第几次看到的排个序，再比较第一次和第二次看到的是否是相同的，且不同于第三个数。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

vector<array<int, 3>> cc{
    {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6},
    {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6},
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    array<int, 9> q{};
    for (auto& i : q)
        cin >> i;
    array<int, 9> p{};
    iota(p.begin(), p.end(), 0);
    int ans = 0, tot = 0;
    do {
        ++tot;
        for (auto& c : cc) {
            sort(c.begin(), c.end(), [&](int a, int b) { return p[a] < p[b]; });
            if (q[c[0]] == q[c[1]] && q[c[0]] != q[c[2]]) {
                ++ans;
                break;
            }
        }

    } while (next_permutation(p.begin(), p.end()));
    cout << fixed << setprecision(10) << 1. * (tot - ans) / tot << '\n';

    return 0;
}

D - Minimum Width (abc319 D)

题目大意

给定若干个单词。写在黑板上，你要规定一个最小的黑板长度，使得单词写在黑板上时，其行数不超过\(m\)。

单词与单词之间有一个空格，一行的长度不能超过规定的长度。

解题思路

当长度很长时，我们可以一行写完，而当长度很小时，我们可能一行只能写一个单词。

由此容易发现长度与行数具有单调性。

因此我们可以二分长度，然后遍历所有单词写在黑板上，判断需要多少行即可。

注意二分的下界不要小于最长的单词长度。

神奇的代码

#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, m;
    cin >> n >> m;
    vector<int> len(n);
    for (auto& i : len)
        cin >> i;
    LL max_l = *max_element(len.begin(), len.end());
    auto check = [&](LL l) {
        int num = 1;
        LL cur = len[0];
        for (int i = 1; i < n; ++i) {
            if (cur + 1 + len[i] <= l) {
                cur = cur + 1 + len[i];
            } else {
                cur = len[i];
                num++;
            }
        }
        return num <= m;
    };
    LL l = max_l - 1, r = 1e18;
    while (l + 1 < r) {
        LL mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    cout << r << '\n';

    return 0;
}

E - Bus Stops (abc319 E)

题目大意

高桥想去青木家。

有\(n\)个公交站，第 \(i\)个公交站只在 \(p_i\)时间的倍数时发车，花费 \(t_i\)时间到第 \(i+1\)个公交站。

高桥从家到第一个公交站需要 \(x\)时间，从第 \(n\)个公交站到青木家需要 \(y\)时间。

有\(q\)个询问，每个询问问高桥从时刻 \(t\)出发，最早可在何时到达青木家。

注意\(p_i\)取值为 \([1,8]\)

解题思路

起初注意到\(p_i\)比较小，考虑到达一个公交站的时间，一开始考虑的是 \(dp[i][j]\)表示从第 \(j\)个公交站出发，此时时间 \(\% p_i\)的值为\(j\)，到达第 \(n\)个公交站最小的耗时。这样我们就知道在第 \(i\)个公交站需要等待多久才能发车了。

考虑从\(t\)时刻出发，到达第一个公交站的时间是 \(t + x\)，根据 \(p_1\)的倍数可以得到一个等待公交的时间，然后启程到下一个公交站。

容易发现我们从第一个公交站出发的时刻都是 \(p_1\)的倍数，但从不同倍数的时间出发，到达下一个公交站时的等待发车时间可能会不同。这是因为\((a \cdot p_1 + t_1) \% p_2\)的值会随着 \(a\)的不同而不同，而但从状态\(j\)无法得知转移到下一个状态时，其时间 \(\%p_{i+1}\)是多少。这意味着单纯记录时间\(\%p_i\)是不够的。

对于两个公交车站，一个每\(p_1\)时间发车，一个每 \(p_2\)时间发车，容易发现它们的发车状态存在一个周期，即 \(lcm(p_1, p_2)\)，即它们的最小公倍数，每这么多时间它们就一起发车。

考虑整个公交站，由于 \(p_i \in [1,8]\) ，它们的最小公倍数是\(840\)，也就是说，每隔\(840\)的时间，整个发车过程就循环往复，和一开始是一样的。因此我们只需事先求出\(0 \sim 839\)这每一时刻出发的到最后一个公交站的耗时，最终每个询问都会落在这 \(840\)种情况中的一个，也就可以直接得出结果。

知道了开始时间，求耗时就是一个模拟的过程，依次遍历每个公交站，然后求出等待时间，然后到下一个公交站继续求。

神奇的代码

#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, y;
    cin >> n >> x >> y;
    vector<array<int, 2>> bs(n - 1);
    for (auto& i : bs)
        cin >> i[0] >> i[1];
    array<LL, 840> dp{};
    for (int i = 0; i < 840; ++i) {
        LL cur = i;
        for (auto& [p, t] : bs) {
            int wait = (p - cur % p) % p;
            cur = (cur + wait + t);
        }
        dp[i] = cur - i;
    }
    int q;
    cin >> q;
    while (q--) {
        int s;
        cin >> s;
        cout << 0ll + s + x + dp[(s + x) % 840] + y << '\n';
    }

    return 0;
}