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

A – 小红玩牌

算法：

    模拟。

思路：

    无。

关键代码：

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

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

B – 小红作弊

算法：

    模拟。

思路：

    无。

关键代码：

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

    int ans = 0;
    for (int i = 0; i < 13; ++i)
    {
        int x;
        cin >> x;

        ans += max(0, x + a[i] - 4);
    }

    cout << ans << endl;
}

C – 小红出对

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    map<pair<int, char>, int> m;
    map<pair<int, char>, vector<int>> hash;
    for (int i = 0; i < n; ++i)
    {
        int x;
        char c;
        cin >> x >> c;
        ++m[{x, c}];
        hash[{x, c}].push_back(i + 1);
    }

    map<int, priority_queue<pair<char, int>, vector<pair<char, int>>, greater<>>> mq;
    for (auto [x, y] : m)
        mq[x.first].push({x.second, y});

    int ans = 0;
    vector<pii> res;
    for (auto [val, q] : mq)
    {
        while (q.size() >= 2)
        {
            auto [_, cnt1] = q.top();
            q.pop();
            auto [__, cnt2] = q.top();
            q.pop();

            int cur1 = cnt1, cur2 = cnt2;
            int t = 1;
            ans += t;
            cur1 -= t;
            cur2 -= t;
            int a = hash[{val, _}].back();
            hash[{val, _}].pop_back();
            int b = hash[{val, __}].back();
            hash[{val, __}].pop_back();

            res.push_back({a, b});
        }
    }

    cout << ans * 2 << endl;
    for (auto [x, y] : res)
        cout << x << ' ' << y << endl;
}

D – 小红打牌

算法：

    组合数学，逆元。

思路：

    枚举每个满足 \(cnt_i, cnt_{i + 1} \le 3\) 的 \(i\)，剩下的 \(4\) 个考虑选择相同的或者不同的即可。

关键代码：

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;
}

ll inv(ll q, ll mod)
{
    return qmi(q, mod - 2, mod);
}

void miyan()
{
    int n;
    cin >> n;
    vector<ll> cnt(N, 0);
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        ++cnt[x];
    }

    ll val1 = 0, val2 = 0;
    for (int i = 1; i < N; ++i)
    {
        if (cnt[i] >= 2)
            ++val1;
        if (cnt[i] >= 4)
            ++val2;
    }

    ll ans = 0;
    for (int i = 1; i < N - 1; ++i)
    {
        if (cnt[i] < 3 || cnt[i + 1] < 3)
            continue;

        ll t1 = val1 - 2;
        ll t2 = val2;

        if (cnt[i] > 3)
            --t2;
        if (cnt[i + 1] > 3)
            --t2;

        ll cur = 0;
        if (val1 >= 2)
            cur = (cur + t1 * (t1 - 1) % MOD * inv(2, MOD) % MOD) % MOD;

        cur = (cur + t2) % MOD;

        if (cnt[i] >= 5)
            cur = (cur + t1) % MOD;
        if (cnt[i + 1] >= 5)
            cur = (cur + t1) % MOD;

        if (cnt[i] >= 7)
            cur = (cur + 1) % MOD;
        if (cnt[i + 1] >= 7)
            cur = (cur + 1) % MOD;

        if (cnt[i] >= 5 && cnt[i + 1] >= 5)
            cur = (cur + 1) % MOD;

        ans = (ans + cur) % MOD;
    }

    cout << ans << endl;
}

E,F – 小红出牌

算法：

    贪心。

思路：

    先考虑没有前 \(x\) 张牌的概念，考虑对于整个数组其顺子个数为多少。

    假设有连续的三个元素出现次数为 \(1, 3, 2\)，顺子个数为 \(3\) 个，如果第三个元素为 \(4\)，那么顺子个数为 \(4\) 个，不难发现数字 \(i\) 对答案的影响为 \(max(0, cnt[i] – cnt[i – 1])\)。

    考虑 \(x\)，定义 \(cnt\) 数组存储当前每个元素的出现次数，对于当前要添加的数字 \(a[i]\) 发现其只影响 \(cnt[a[i]], cnt[a[i] – 1], cnt[a[i] + 1]\)，那么只需再添加数字前减去其影响，将其个数增加后再添加上其影响即可。

关键代码：

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

    vector<int> b(n + 1, 0);

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans -= max(0, b[a[i]] - b[a[i] - 1]);
        ans -= max(0, b[a[i] + 1] - b[a[i]]);

        ++b[a[i]];

        ans += max(0, b[a[i]] - b[a[i] - 1]);
        ans += max(0, b[a[i] + 1] - b[a[i]]);

        cout << ans << ' ';
    }

    cout << endl;
}

G – 小红出千

算法：

    树状数组。

思路：

    最优解是滑动窗口。

    考虑将 \(a[i]\) 设为顺子的开头，计算数组需要变换多少元素可以变为长度为 \(n\) 且连续的顺子。

    对于计算部分，可以使用树状数组 + 离散化快速计算。

    计算出最小次数与最小开头后，将没用的元素修改掉即可。

关键代码：

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<int> a(n);
    for (auto &x : a)
        cin >> x;

    auto aa = a;
    auto b = a;
    for (auto x : a)
        b.push_back(x + n - 1);

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

    for (auto &x : a)
        x = ranges::lower_bound(b, x) - b.begin() + 1;

    BIT bit(N);

    for (int i = 0; i < n; ++i)
    {
        if (!bit.query(a[i], a[i]))
            bit.add(a[i], 1);
    }

    int ans = INT_MAX;
    int val = 0;
    for (int i = 0; i < n; ++i)
    {
        int R = ranges::lower_bound(b, aa[i] + n - 1) - b.begin() + 1;

        int cur = n - bit.query(a[i], R);

        if (cur < ans)
        {
            ans = cur;
            val = aa[i];
        }
    }

    cout << ans << endl;

    map<int, int> st;
    for (int i = 0; i < n; ++i)
        ++st[aa[i]];

    set<int> S;

    int L = val, R = val + n - 1;
    vector<int> res;
    for (int i = 0; i < n; ++i)
    {
        if (aa[i] >= L && aa[i] <= R && !S.count(aa[i]))
            S.insert(aa[i]);
        else
            res.push_back(i + 1);
    }

    for (int i = L; i <= R; ++i)
    {
        if (!st[i])
        {
            cout << res.back() << ' ' << i << endl;
            res.pop_back();
        }
    }
}