链接：https://atcoder.jp/contests/abc393/tasks/abc393_a

A – Poisonous Oyster

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    string a, b;
    cin >> a >> b;

    if (a == "sick" && b == "sick")
        cout << 1 << endl;
    else if (a == "sick" && b == "fine")
        cout << 2 << endl;
    else if (a == "fine" && b == "sick")
        cout << 3 << endl;
    else
        cout << 4 << endl;
}

B – A..B..C

算法：

    模拟。

思路：

    无。

关键代码：

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

    int n = s.size();

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == 'B')
        {
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < n)
            {
                if (s[l] == 'A' && s[r] == 'C')
                    ++ans;
                --l, ++r;
            }
        }
    }

    cout << ans << endl;
}

C – Make it Simple

算法：

    图，\(STL\)。

思路：

    无。

关键代码：

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

    ll ans = 0;

    map<pii, int> hash;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        --u, --v;

        if (u == v || hash.count({u, v}) || hash.count({v, u}))
            ++ans;

        hash[{u, v}] = 1;
    }

    cout << ans << endl;
}

D – Swap to Gather

算法：

    贪心，前后缀。

思路：

    贪心策略：

• 对于当前位置，如果其为 '1' 尝试将所有 '1' 移动到其两边。
• 使用前后缀数组优化每次查询时间。

关键代码：

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

    s = ' ' + s;

    vector<ll> pre(n + 2, 0);
    ll cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        pre[i] = pre[i - 1];

        if (i > 1 && s[i - 1] == '0')
            pre[i] += cnt;

        if (s[i] == '1')
            ++cnt;
    }

    vector<ll> suf(n + 2, 0);
    cnt = 0;
    for (int i = n; i >= 1; --i)
    {
        suf[i] = suf[i + 1];

        if (i < n && s[i + 1] == '0')
            suf[i] += cnt;

        if (s[i] == '1')
            ++cnt;
    }

    ll ans = LLONG_MAX;
    for (int i = 1; i <= n; ++i)
        if (s[i] == '1')
            ans = min(ans, 1ll * pre[i] + suf[i]);

    cout << ans << endl;
}

E – GCD of Subset

算法：

    数论，\(GCD\)。

思路：

    存储每个数字出现次数。

    考虑枚举最大公约数 \(d\)，对于每个 \(d\)，统计其倍数的出现的次数，如果次数超过 \(k\)，那么 \(d\) 就可以当作倍数的答案。

关键代码：

void miyan()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    vector<int> m(N, 0);
    for (auto &x : a)
    {
        cin >> x;
        ++m[x];
    }

    vector<int> ans(N, 1);
    for (int d = 2; d < N; ++d)
    {
        ll cnt = 0;
        for (int i = d; i < N; i += d)
            cnt += m[i];

        if (cnt >= k)
            for (int i = d; i < N; i += d)
                ans[i] = d;
    }

    for (int i = 0; i < n; ++i)
        cout << ans[a[i]] << endl;
}

F – Prefix LIS Query

算法：

    \(LIS\)，离散化，树状数组。

思路：

    考虑将 \(r\) 分桶，分别处理每个 \(r\) 及其 \(x\)。

    按照 \(r = 1,2,…..,n\) 的顺序依次将当前 \(a[r]\) 加入的处理序列中。

    此时问题就转换为了：对于动态添加数字的序列，求总体值小于 \(x\) 的 \(LIS\)。

    使用 \(LIS\)：

• 定义 \(dp[val]\) 为子序列中全体值都小于 \(val\) 的 \(LIS\) 长度。
• 对于当前 \(a_r\)，其可以当作 \(dp[1 \text{ ~ } a_r – 1]\) 的新结尾，那么对于 \(a_r\) 其 \(LIS\) 长度为 \(max(dp[1 \text{ ~ } a_r – 1]) + 1\)。
• 此时 \(dp[a_r]\) 就可更新为 \(max(dp[1 \text{ ~ } a_r – 1]) + 1\)。
• 对于当前 \(r\) 的所有询问 \(x\)，只需查询 \(dp[x]\) 即可。
• 综上需要快速统计 \(max(dp[1 \text{ ~ } a_r – 1])\) 和得到 \(dp[x]\)，考虑使用树状数组优化 \(LIS\)。
• \(a_i\) 的值域较大，需要离散化处理。

关键代码：

int n, q;
vector<int> a;
vector<vector<pii>> Q;
vector<ll> tr;

void disc()
{
    vector<int> b;
    for (int i = 1; i <= n; ++i)
        b.push_back(a[i]);
    for (int i = 1; i <= n; ++i)
        for (auto [x, _] : Q[i])
            b.push_back(x);

    ranges::sort(b);
    b.erase(unique(all(b)), b.end());

    for (int i = 1; i <= n; ++i)
        a[i] = ranges::lower_bound(b, a[i]) - b.begin() + 1;
    for (int i = 1; i <= n; ++i)
        for (auto &[x, _] : Q[i])
            x = ranges::lower_bound(b, x) - b.begin() + 1;
}

ll lowbit(ll x) { return x & -x; }

void update(int x, ll val)
{
    for (int i = x; i <= n + q; i += lowbit(i))
        tr[i] = max(tr[i], val);
}

ll query(int x)
{
    ll ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans = max(ans, tr[i]);
    return ans;
}

void miyan()
{
    cin >> n >> q;
    a.resize(n + 1);
    Q.resize(n + 1);
    tr.resize(n + q + 1, 0);

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = 1; i <= q; ++i)
    {
        int r, x;
        cin >> r >> x;
        Q[r].push_back({x, i});
    }

    disc();

    vector<int> ans(q + 1);
    for (int i = 1; i <= n; ++i)
    {
        ll cur = query(a[i] - 1);
        update(a[i], cur + 1);

        for (auto [x, pos] : Q[i])
            ans[pos] = query(x);
    }

    for (int i = 1; i <= q; ++i)
        cout << ans[i] << endl;
}

G – Unevenness

    还没补。