【题解】 Dwango Programming Contest 6th

比赛链接: https://atcoder.jp/contests/dwacon6th-prelims

A. Falling Asleep

模拟。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
int n;
std::string x;
std::vector<std::string> s;
std::vector<int> t;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    s.resize(n);
    t.resize(n);
    for (int i = 0; i < n; ++i)
        std::cin >> s[i] >> t[i];
    std::cin >> x;
    std::cout << std::accumulate(std::find(s.begin(), s.end(), x) - s.begin() + 1 + t.begin(), t.end(), 0) << "\n";
    return 0;
}

B. Fusing Slimes

#include <iostream>
#include <vector>
constexpr int P = 1'000'000'007;
int n;
std::vector<int> x;
int power(int a, int b)
{
    int ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans = 1LL * ans * a % P;
        a = 1LL * a * a % P;
        b >>= 1;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    x.resize(n);
    for (int i = 0; i < n; ++i)
        std::cin >> x[i];
    int ans = 0;
    for (int i = 1, j = 0; i < n; ++i)
    {
        j = (j + power(i, P - 2)) % P;
        ans = (ans + 1LL * j * (x[i] - x[i - 1])) % P;
    }
    for (int i = 1; i < n; ++i)
        ans = 1LL * ans * i % P;
    std::cout << ans << "\n";
    return 0;
}

C. Cookie Distribution

#include <iostream>
#include <vector>
constexpr int P = 1'000'000'007;
int n, k;
std::vector<int> a;
std::vector<std::vector<int>> c, dp;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> k;
    a.resize(k);
    for (int i = 0; i < k; ++i)
        std::cin >> a[i];
    c.assign(n + 1, std::vector<int>(n + 1));
    for (int i = 0; i <= n; ++i)
    {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
    }
    dp.assign(k + 1, std::vector<int>(n + 1));
    dp[0][0] = 1;
    for (int i = 0; i < k; ++i)
        for (int j = 0; j <= n; ++j)
            for (int l = 0; l <= n - j && l <= a[i]; ++l)
                dp[i + 1][j + l] = (dp[i + 1][j + l] + 1LL * dp[i][j] * c[n - j][l] % P * c[n - l][a[i] - l]) % P;
    std::cout << dp[k][n] << "\n";
    return 0;
}

D. Arrangement

考虑贪心：

• 如果有一个点的入度等于剩余点数 -1 ，则必须选。
• 否则选剩下能选的最小的点。

但是这样可能在最后几步产生无解的情况，只需要将最后几个点改为暴力枚举即可。

#include <iostream>
#include <vector>
#include <set>
constexpr int P = 1'000'000'007;
int n;
std::vector<int> a, deg, ans, b;
std::set<int> s;
std::set<std::pair<int, int>> d;
std::vector<bool> used;
void dfs(int c, int lim)
{
    if (c == n)
    {
        for (int i = 0; i < n; ++i)
            std::cout << ans[i] + 1 << " \n"[i == n - 1];
        exit(0);
    }
    for (int i = 0; i < int(b.size()); ++i)
    {
        if (used[b[i]] || b[i] == lim)
            continue;
        ans[c] = b[i];
        used[b[i]] = true;
        dfs(c + 1, a[b[i]]);
        used[b[i]] = false;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    if (n == 2)
    {
        std::cout << -1 << "\n";
        return 0;
    }
    a.resize(n);
    deg.resize(n);
    ans.resize(n);
    used.resize(n);
    for (int i = 0; i < n; ++i)
    {
        std::cin >> a[i];
        --a[i];
        ++deg[a[i]];
    }
    for (int i = 0; i < n; ++i)
        s.insert(i);
    for (int i = 0; i < n; ++i)
        d.emplace(-deg[i], i);
    int lim = -1;
    for (int i = 0; i < n - 5; ++i)
    {
        int u;
        if (-d.begin()->first == n - i - 1)
        {
            u = d.begin()->second;
        }
        else if (*s.begin() != lim)
        {
            u = *s.begin();
        }
        else
        {
            u = *std::next(s.begin());
        }
        s.erase(u);
        d.erase({-deg[u], u});
        used[u] = true;
        if (!used[a[u]])
        {
            d.erase({-deg[a[u]], a[u]});
            --deg[a[u]];
            d.emplace(-deg[a[u]], a[u]);
        }
        lim = a[u];
        ans[i] = u;
    }
    b.assign(s.begin(), s.end());
    dfs(std::max(0, n - 5), lim);
    std::cout << -1 << "\n";
    return 0;
}

E. Span Covering

#include <iostream>
#include <vector>
#include <cassert>
constexpr int P = 1'000'000'007;
int n, x;
std::vector<int> cl, factorial, invFactorial;
std::vector<std::vector<int>> dp;
int power(int a, int b)
{
    int ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans = 1LL * ans * a % P;
        a = 1LL * a * a % P;
        b >>= 1;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> x;
    ++x;
    cl.resize(x + 1);
    for (int i = 0; i < n; ++i)
    {
        int l;
        std::cin >> l;
        ++cl[l];
    }
    dp.assign(x + 1, std::vector<int>(x + 1));
    dp[0][0] = P - 1;
    factorial.resize(x + 1);
    invFactorial.resize(x + 1);
    factorial[0] = 1;
    for (int i = 1; i <= x; ++i)
        factorial[i] = 1LL * factorial[i - 1] * i % P;
    for (int i = 0; i <= x; ++i)
        invFactorial[i] = power(factorial[i], P - 2);
    for (int l = x; l >= 1; --l)
    {
        for (int c = x / l; c >= 0; --c)
        {
            for (int s = 0; s <= x; ++s)
            {
                if (dp[c][s] == 0)
                    continue;
                for (int i = 1; i * l + s <= x; ++i)
                {
                    if (i % 2 == 0)
                    {
                        dp[c + i][s + i * l] = (dp[c + i][s + i * l] + 1LL * dp[c][s] * invFactorial[i]) % P;
                    }
                    else
                    {
                        dp[c + i][s + i * l] = (dp[c + i][s + i * l] + 1LL * (P - dp[c][s]) * invFactorial[i]) % P;
                    }
                }
            }
        }
        for (int i = 0; i < cl[l]; ++i)
            for (int c = 0; c <= x; ++c)
                for (int s = 0; s <= x; ++s)
                    dp[c][s] = 1LL * dp[c][s] * (s - l * c) % P;
    }
    int ans = 0;
    for (int c = 0; c <= x; ++c)
        ans = (ans + 1LL * factorial[c] * dp[c][x]) % P;
    std::cout << ans << "\n";
    return 0;
}