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

A – Handmaid

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    string s;
    cin >> s;

    s[0] = s[0] - 'A' + 'a';

    cout << "Of" << s << endl;
}

B – Greedy Draft

算法：

模拟。

思路：

无。

关键代码：

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

    vector<int> st(m + 1, 0);
    for (int i = 0; i < n; ++i)
    {
        int len;
        cin >> len;

        vector<int> a;
        while (len--)
        {
            int x;
            cin >> x;

            if (st[x])
                continue;

            a.push_back(x);
        }

        int ans = 0;
        if (a.size())
        {
            st[a.front()] = 1;
            ans = a.front();
        }

        cout << ans << endl;
    }
}

C – Omelette Restaurant

算法：

模拟。

思路：

队列模拟即可。

关键代码：

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

    vector<int> a(n), b(n);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;

    queue<pii> q;
    for (int i = 0; i < n; ++i)
    {
        q.push({i, a[i]});

        int need = b[i];
        while (q.size() && need)
        {
            auto [day, cnt] = q.front();

            int t = min(need, cnt);
            need -= t;
            cnt -= t;

            if (cnt)
                q.front().second = cnt;
            else
                q.pop();
        }

        while (q.size() && q.front().first + d <= i)
            q.pop();
    }

    ll ans = 0;
    while (q.size())
    {
        ans += q.front().second;
        q.pop();
    }

    cout << ans << endl;
}

D – Max Straight

算法：

\(dp\)。

思路：

简单 \(dp\)。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    map<int, int> dp;
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int x = a[i];

        if (!dp.count(x))
            dp[x] = 1;
        if (dp.count(x - 1))
            dp[x] = max(dp[x], dp[x - 1] + 1);

        ans = max(ans, dp[x]);
    }

    cout << ans << endl;
}

E – Multiple-Free Sequences

算法：

搜索，多源 \(bfs\)。

思路：

重要观察：没有 \(m\) 的倍数 \(=\) 模 \(m\) 不为 \(0\)，将计算引入模数 \(m\)。

定义状态为 \((u, v)\)，那么共有 \(m ^ 2\) 个状态。

当前状态 \((u, v)\) 下一个状态 \((u’, v’)\)，其中 \(u’ = v, v’ \equiv (A \times v + B \times u)(\mod m)\)。

从 \((u, v)\) 开始找带有 \(0\) 的状态不容易，非常容易陷入死循环。

考虑反向找，既从带有 \(0\) 的状态逆向搜索其他状态，既已知 \((u’, v’)\)，找 \((u, v)\)。

当已知 \((u’, v’)\) 时，\(v = u’, B \times u \equiv v’ – A \times v(\mod m)\)，由于带有模数 \(m\)，难以还原 \(B \times u\) 在模 \(m\) 意义下 \(u\) 的值，考虑以下方法：

• 定义二维数组 \(pre\)，其中第一维为 \(B \times u(\mod m)\)，第二维为 \(B \times u(\mod m)\) 的 \(u\) 值，此时只需已知 \(B \times u\)，就可以确定有哪些 \(u\) 值。

搜索起点就为所有的 \((u, 0)\) 和 \((v, 0)\)，答案就为 \(m ^ 2 – 搜索到的节点\)。

搜索过程不过多赘述，看代码即可。

关键代码：

void miyan()
{
    int m, a, b;
    cin >> m >> a >> b;

    vector<vector<int>> pre(m);
    for (int u = 0; u < m; ++u)
        pre[(b * u) % m].push_back(u);

    vector st(m, vector<int>(m, 0));
    queue<pii> q;
    for (int u = 0; u < m; ++u)
    {
        q.push({u, 0});
        q.push({0, u});
        st[0][u] = 1;
        st[u][0] = 1;
    }

    while (q.size())
    {
        auto [uu, vv] = q.front();
        q.pop();

        int v = uu;
        int Bu = (vv - a * v % m + m) % m;
        for (auto u : pre[Bu])
        {
            if (!st[u][v])
            {
                st[u][v] = 1;
                q.push({u, v});
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < m; ++i)
        ans += accumulate(all(st[i]), 0);

    cout << m * m - ans << endl;
}

F – Reachable Set 2

还没补。