A – Legendary Players (abc319 A)题目大意

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

给定名字，问对应分数。

解题思路

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

神奇的代码
#include using namespace std;using LL = long long;vector 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 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 using namespace std;using LL = long long;vector<array> 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 q{};    for (auto& i : q)        cin >> i;    array 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 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 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 > 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 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> bs(n - 1);    for (auto& i : bs)        cin >> i[0] >> i[1];    array dp{};    for (int i = 0; i > q;    while (q--) {        int s;        cin >> s;        cout << 0ll + s + x + dp[(s + x) % 840] + y << '\n';    }    return 0;}

F – Fighter Takahashi (abc319 F)题目大意

给定一棵树，初始1攻击力。每个点有怪物或者药品，打怪需要你攻击力大于等于\(s_i\)，否则失败。打死怪后攻击力提升\(g_i\)。药品的话你的攻击会翻 \(g_i\)倍。

问能否打死所有怪物。

解题思路

神奇的代码

G – Counting Shortest Paths (abc319 G)题目大意

给定一个完全图，删去一些边，问从点\(1\)到点 \(n\)的最短路条数。

解题思路

点数小时可以直接\(BFS\)求解，点数大时枚举长度存在的情况，结果发现算错了需要删去的最小边数寄了。

神奇的代码