AtCoder Beginner Contest 319

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;
}



F - Fighter Takahashi (abc319 F)

题目大意

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

问能否打死所有怪物。

解题思路

<++>

神奇的代码



G - Counting Shortest Paths (abc319 G)

题目大意

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

解题思路

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

神奇的代码


热门相关:总裁的天价小妻子   上将大叔,狼来了!   嫡嫁千金   精灵掌门人   慕少,你老婆又重生了