链接：https://atcoder.jp/contests/abc404

A – Not Found

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    string s;
    cin >> s;
    vector<int> cnt(26, 0);
    for (auto c : s)
        cnt[c - 'a'] = 1;

    for (int i = 0; i < 26; ++i)
    {
        if (!cnt[i])
        {
            cout << char(i + 'a') << endl;
            return;
        }
    }
}

B – Grid Rotation

算法：

    模拟。

思路：

    存在的贡献的旋转只为前三次，后面会重复，对于每次旋转判断其修改成一样的代价，取最小值即可。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<string> s(n), t(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];
    for (int i = 0; i < n; ++i)
        cin >> t[i];

    auto ture = [&]() -> void
    {
        auto a = s;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                s[i][j] = a[n - j - 1][i];
    };

    auto check = [&]() -> ll
    {
        ll cnt = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (s[i][j] != t[i][j])
                    ++cnt;

        return cnt;
    };

    ll ans = INT_MAX;
    for (int i = 0; i < 4; ++i)
    {
        ans = min(ans, i + check());

        ture();
    }

    cout << ans << endl;
}

C – Cycle Graph?

算法：

    \(dfs\)，图论

思路：

    想判断整个图是不是一个环，需要判断：

• 每个点的度数都为 \(2\)。
• 整个图是连通的。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;

    vector<int> du(n + 1, 0);
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        ++du[u], ++du[v];
    }

    if (!m)
    {
        cout << "No" << endl;
        return;
    }

    ll cnt = 1;
    bool ok = 0;
    vector<int> st(n + 1, 0);
    auto dfs = [&](auto &&self, int u, int f) -> void
    {
        for (auto v : g[u])
        {
            if (ok)
                return;
            if (v == f)
                continue;
            if (st[v])
            {
                ok = 1;
                return;
            }

            ++cnt;
            st[v] = 1;
            self(self, v, u);
        }

        if (ok)
            return;
    };

    st[1] = 1;
    dfs(dfs, 1, 0);

    if (cnt != n)
    {
        cout << "No" << endl;
        return;
    }

    for (int i = 1; i <= n; ++i)
    {
        if (du[i] != 2)
        {
            cout << "No" << endl;
            return;
        }
    }

    cout << "Yes" << endl;
}

D – Goin’ to the Zoo

算法：

    暴搜。

思路：

    对于每个动物园参考次数只有三个可能：\(0\) \(1\) \(2\)。

    由于 \(n\) 只为 \(10\)，直接暴搜每个动物园参考次数即可。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<ll> c(n);
    for (auto &x : c)
        cin >> x;

    vector<vector<int>> a(n);
    for (int i = 0; i < n; ++i)
        a[i].reserve(m);

    for (int i = 0; i < m; ++i)
    {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j)
        {
            int x;
            cin >> x;
            --x;
            a[x].push_back(i);
        }
    }

    ll ans = 1e18;
    vector<int> cnt(m, 0);
    auto dfs = [&](auto &&self, int u, ll res) -> void
    {
        if (res >= ans)
            return;

        bool ok = 1;
        for (int i = 0; i < m; ++i)
        {
            if (cnt[i] < 2)
                ok = 0;
        }

        if (ok)
            ans = res;

        if (u == n)
            return;

        for (int i = 0; i <= 2; ++i)
        {
            for (auto x : a[u])
                cnt[x] += i;

            self(self, u + 1, res + c[u] * i);

            for (auto x : a[u])
                cnt[x] -= i;
        }
    };

    dfs(dfs, 0, 0);

    cout << ans << endl;
}

E – Bowls and Beans

算法：

    贪心。

思路：

    贪心策略：

• 对于当前有豆子的 \(i\) ：优先给有豆子并且 \(i – c[i]\) 最小的，如果都没有豆子则给 \(i – c[i]\) 最小的。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> c(n), a(n);
    for (auto &x : c | views::drop(1))
        cin >> x;
    for (auto &x : a | views::drop(1))
        cin >> x;

    for (int i = 1; i < n; ++i)
        c[i] = i - c[i];

    ll ans = 0;
    for (int i = n - 1; i >= 1; --i)
    {
        if (a[i])
        {
            ++ans;

            ll pos = -1;
            for (int j = c[i]; j < i; ++j)
                if (a[j] && (pos == -1 || c[j] < c[pos]))
                    pos = j;

            if (pos == -1)
            {
                for (int j = c[i]; j < i; ++j)
                    if (pos == -1 || c[j] < c[pos])
                        pos = j;
            }

            a[pos] += a[i];
        }
    }

    cout << ans << endl;
}

F – Lost and Pound

    还没补。