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

A – Not Acceptable

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if (c > a)
        cout << "No" << endl;
    else if (c < a)
        cout << "Yes" << endl;
    else
    {
        if (b >= d)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

B – Product Calculator

算法：

    模拟。

思路：

    直接硬乘会爆 \(ll\)，需要使用 \(int128\) 或者将乘法转为除法。

    乘法转除法：

\(now \times x < 10^k \;\;\Rightarrow\;\; now < \frac{10^k}{x}\)

    在判断大小的时候需要将除法转换为浮点数比较。

关键代码：

void solve()
{
    int n, k;
    cin >> n >> k;

    ull val = powl(10, k);

    ull now = 1;
    for (int i = 1; i <= n; ++i)
    {
        ull x;
        cin >> x;

        if (now >= (long double)val / x)
            now = 1;
        else
            now *= x;
    }

    cout << now << endl;
}

C – ~

经典 \(c > d\)

算法：

    贪心，找规律。

思路：

    定义数组 \(b\)，其中 \(b[i] = a[i + 1] > a[i]\)。

    通过 \(b\) 数组可知满足题目要求的序列为 \([1, a][0, b][1, c]\)。

    既两段任意长度（长度 \(a\)，\(c\)）的 \(1\) 中间夹着一段任意长度的 \(0\)，而这一段对答案的贡献为 \(a * c\)。

    例：如果数组某段为 \(1110011\)，那么满足的子段为 \(1001,11001,111001,10011,110011,1110011\)。

    既：\(a\) 中的每个 \(1\) 都可与 \(b\) 中的任意 \(1\) 配对。

关键代码：

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

    vector<int> b;
    b.reserve(n);
    for (int i = 1; i <= n - 1; ++i)
    {
        if (a[i] < a[i + 1])
            b.push_back(1);
        else
            b.push_back(0);
    }

    ll ans = 0;
    ll last = 0;
    ll now = 0;
    for (auto x : b)
    {
        if (x)
            ++now;
        else
        {
            ans += last * now;
            if (now)
            {
                last = now;
                now = 0;
            }
        }
    }

    if (now)
        ans += last * now;

    cout << ans << endl;
}

D – Garbage Removal

算法：

    模拟，\(STL\)。

思路：

    观察到 \(H\) 和 \(W\) 都非常大，但是 \(N\) 只有 \(2e5\)，可以使用一个数据结构维护每一行每一列的所有点，对于每次查询：

• 如果是清空行，那么就遍历该行所有点，在点对应的列中也删除该点，最后直接清空该行所有点即可。
• 列同理。

    使用 \(set\) 或者 \(map\) 都可。

关键代码：

void solve()
{
    int h, w, n;
    cin >> h >> w >> n;

    set<int> X[h + 1], Y[w + 1];
    for (int i = 0; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        X[x].insert(y);
        Y[y].insert(x);
    }

    int Q;
    cin >> Q;
    while (Q--)
    {
        int op, p;
        cin >> op >> p;
        if (op == 1)
        {
            cout << X[p].size() << endl;

            for (auto y : X[p])
                Y[y].erase(p);

            X[p].clear();
        }
        else
        {
            cout << Y[p].size() << endl;

            for (auto x : Y[p])
                X[x].erase(p);

            Y[p].clear();
        }
    }
}

E – Popcount Sum 3

    数位 \(dp\) 后面再补。