链接：https://ac.nowcoder.com/acm/contest/122724

A – ICPC Rank

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int x, y, p1, p2;
    cin >> x >> y >> p1 >> p2;

    if (x > y)
        cout << 'A' << endl;
    else if (x < y)
        cout << 'B' << endl;
    else
    {
        if (p1 < p2)
            cout << 'A' << endl;
        else if (p1 > p2)
            cout << 'B' << endl;
        else
            cout << 'C' << endl;
    }
}

B – 小苯的序列极值

算法：

    排序，贪心。

思路：

    无。

关键代码：

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

    ranges::sort(a);

    cout << a[n - 1] - a[0] << endl;
}

C – 小苯的平方数

算法：

    打表。

思路：

    打表发现只有 1 和 9 满足条件。

关键代码：

void miyan()
{
    int l, r;
    cin >> l >> r;

    int ans = 0;
    if (1 >= l && 1 <= r)
        ++ans;
    if (9 >= l && 9 <= r)
        ++ans;

    cout << ans << endl;
}

D – 小苯的左右移动

算法：

    贪心，快速幂。

思路：

    右移会清除末尾的 \(1\)，左移只会添加 \(0\)，清除的 \(1\) 加不回来，判断右移最大到达的位置，后续正常处理即可。

关键代码：

ll qmi(ll a, ll b, ll p)
{
    ll ans = 1 % p;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }

    return ans;
}

void miyan()
{
    ll n, k;
    cin >> n >> k;

    ll cur = 0;
    ll maxx = 0;
    for (int i = 1; i <= n; ++i)
    {
        ll x;
        cin >> x;

        if (i & 1)
            cur -= x;
        else
            cur += x;

        maxx = max(maxx, cur);
    }

    cur = -cur;

    while (k > 0 && maxx > 0)
    {
        --maxx;
        k >>= 1;
        ++cur;
    }

    k %= MOD;

    ll ans = 0;
    if (cur > 0)
        ans = k * qmi(2, cur, MOD) % MOD;

    cout << ans << endl;
}

E – 小苯的三角计数

算法：

    枚举，二分。

思路：

    分三种情况考虑：

• 三条边都不一样的情况，双层循环枚举两条边，二分另外一条边的可行区间下标，注意二分出的区间中可能包含另外两条边，需要判断一下，最后这种情况会统计三份，需要除 \(3\)。
• 有两条边一样的情况，枚举有两条及以上数量的边，二分另外一条的可行区间下标，仍需注意区间中可能包含枚举的条，需判断。
• 最后就是三条边都一样的情况，枚举有三条及以上数量的边，累加进答案即可。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> val(n);
    vector<pii> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i].first >> a[i].second;
        val[i] = a[i].first;
    }

    ranges::sort(a);
    ranges::sort(val);

    ll ans = 0;
    ll cnt1 = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            int l = abs(a[i].first - a[j].first);
            int r = a[i].first + a[j].first;

            int L = ranges::upper_bound(val, l) - val.begin();
            int R = ranges::lower_bound(val, r) - val.begin() - 1;

            cnt1 += R - L + 1;
            if (i >= L && i <= R)
                --cnt1;
            if (j >= L && j <= R)
                --cnt1;
        }
    }

    ans += cnt1 / 3;

    ll cnt2 = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i].second == 1)
            continue;

        int l = abs(a[i].first - a[i].first);
        int r = a[i].first + a[i].first;

        int L = ranges::upper_bound(val, l) - val.begin();
        int R = ranges::lower_bound(val, r) - val.begin() - 1;

        cnt2 += R - L + 1;
        if (i >= L && i <= R)
            --cnt2;
    }

    ans += cnt2;

    for (int i = 0; i < n; ++i)
        if (a[i].second >= 3)
            ++ans;

    cout << ans << endl;
}

F – 小苯的极大支配

算法：

    树状数组。

思路：

    问题转化：

• 将问题转化为最大保留多少数字。

    预处理：

• 统计每个数字的出现次数。
• 按出现次数分组，并排序每组数字。
• 升序枚举出现次数 \(cnt\)：
  • 对每个 \(cnt\)，贪心选择最大的 \(x\) 作为极大支配数。
  • 计算保留的数字总数：
  • 同 \(cnt\) 的其他数字：每个保留 \(cnt-1\) 个，总保留数为 \(vec.size() * cnt – vec.size() + 1\)。
  • 出现次数 \(< cnt\) 的数字：保留小于 \(x\) 的全部数字。
  • 出现次数 \(> cnt\) 的数字：只保留比 \(x\) 小的数字每个 \(cnt-1\) 个。

    树状数组维护：

• \(b1\)：维护出现次数 \(< cnt\) 的数字的总出现次数（动态更新）。
• \(b2\)：维护出现次数 \(> cnt\) 的数字的存在性（存在记为\(1\)，否则\(0\)）。

    最后答案就为最少删除数 \(= n – maxx\)。

关键代码：

struct BIT
{
    int n;
    vector<ll> tr;
    BIT(int _N)
    {
        n = _N;
        tr.resize(n + 1, 0);
    }

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

    void add(int x, ll v)
    {
        for (int i = x; i <= n; i += lowbit(i))
            tr[i] += v;
    }

    ll query(int l, int r)
    {
        auto ask = [&](int x)
        {
            ll ans = 0;
            for (int i = x; i; i -= lowbit(i))
                ans += tr[i];
            return ans;
        };
        return ask(r) - ask(l - 1);
    }
};

void miyan()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; ++i)
        cin >> a[i];

    map<ll, ll> m;
    for (ll i = 0; i < n; ++i)
        ++m[a[i]];

    map<ll, vector<ll>> hash;
    for (auto [x, y] : m)
        hash[y].push_back(x);

    for (auto &[_, vec] : hash)
        ranges::sort(vec, greater<>());

    BIT b1(n + 1), b2(n + 1);
    for (auto [cnt, vec] : hash)
        for (auto x : vec)
            b2.add(x, 1);

    ll ans = 0;
    for (auto [cnt, vec] : hash)
    {
        for (auto x : vec)
            b2.add(x, -1);

        int x = vec[0];

        ll cur1 = vec.size() * cnt - vec.size() + 1;
        ll cur2 = b1.query(1, x - 1);
        ll cur3 = b2.query(1, x - 1) * (cnt - 1);

        ans = max(ans, cur1 + cur2 + cur3);

        for (auto x : vec)
            b1.add(x, cnt);
    }

    cout << n - ans << endl;
}