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

A – 模糊匹配

算法：

模拟。

思路：

无。

关键代码：

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

    for (int i = 0; i < n; ++i)
    {
        if (s[i] == t[i])
            continue;

        if ((s[i] == '0' || s[i] == 'O') && (t[i] == '0' || t[i] == 'O'))
            continue;

        if ((s[i] == '1' || s[i] == 'l' || s[i] == 'I') && (t[i] == '1' || t[i] == 'l' || t[i] == 'I'))
            continue;

        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
}

B – 只留专一数

算法：

贪心，质因数分解。

思路：

手玩样例发现，只要存在任意一个数字，其质因数分解后质因子只有一个，那么就满足最后 \(a_1\) 是专一数。

特殊的，\(1\) 也满足要求。

关键代码：

vector<int> prime, minp, maxp;
void get_prime(int n)
{
    minp.resize(n + 1);
    maxp.resize(n + 1);
    for (int i = 2; i <= n; i++)
    {
        if (!minp[i])
        {
            minp[i] = maxp[i] = i;
            prime.push_back(i);
        }
        for (auto j : prime)
        {
            if (j > minp[i] || j > n / i)
                break;
            minp[i * j] = j;
            maxp[i * j] = maxp[i];
        }
    }
}

vector<array<int, 2>> factorize(int n)
{
    vector<array<int, 2>> ans;
    while (n > 1)
    {
        int now = minp[n], cnt = 0;
        while (n % now == 0)
        {
            n /= now;
            cnt++;
        }
        ans.push_back({now, cnt});
    }
    return ans;
}

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

    for (int i = 0; i < n; ++i)
    {
        if (factorize(a[i]).size() <= 1)
        {
            cout << "YES" << endl;
            return;
        }
    }

    cout << "NO" << endl;
}

C – 左右左右左左右，左右左左右

算法：

模拟，贪心。

思路：

每次尝试添加 \(a_0\) 或者 \(a_1\)，每次都取总贡献最小的即可。

具体实现看代码。

关键代码：

void miyan()
{
    int n, a0, a1;
    cin >> n >> a0 >> a1;

    string ans;
    ll val0 = 0, val1 = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (abs((val1 + a0) - val0) >= abs(val1 - (val0 + a1)))
        {
            val0 += a1;
            ans += '0';
        }
        else
        {
            val1 += a0;
            ans += '1';
        }
    }

    cout << ans << endl;
}

D – 进退的艺术

算法：

二分，差分，前缀和，排序。

思路：

经典二分前缀和题目，不过多赘述。

关键代码：

void miyan()
{
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> b(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> b[i].first;
        b[i].second = i;
    }

    ranges::sort(b);

    vector<ll> c(n), s(n + 1, 0);
    for (int i = 0; i < n; ++i)
    {
        c[i] = b[i].first;
        s[i + 1] = s[i] + c[i];
    }

    vector<ll> ans(n);
    for (int i = 0; i < n; ++i)
    {
        ll cur = c[i];
        int R = upper_bound(c.begin(), c.end(), m - cur) - c.begin() - 1;

        ll cnt = R + 1;
        if (R >= i)
            cnt--;

        ll sco = cnt * cur;

        int L = R + 1;
        if (L < n)
        {
            ll sum = s[n] - s[L];
            if (i >= L)
                sum -= cur;
            sco -= sum;
        }

        ans[b[i].second] = sco;
    }

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

E – 扫雷难度调节

算法：

构造。

思路：

将地图分为独立的 \(9\) 宫格（长度不足以到达 \(9\) 宫格的位置，取剩余的一部分），将地雷放到 \(9\) 宫格中心，以最大化数字格数量，此时数字格个数是地图最大数字格个数，不难想到计算公式 \(count = n * m – \lceil \frac{n}{3} \rceil * \lceil \frac{m}{3} \rceil\)，如果 \(count\) 小于题目要求个数（设该个数为 \(k\)），那么题目无解；如果 \(count\) 题目大于 \(k\)，则在任意位置多输出 \(count – k\) 个地雷格即可。

关键代码：

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

    ll maxx = n * m - ((n + 2) / 3) * ((m + 2) / 3);
    if (maxx < k)
    {
        cout << -1 << endl;
        return;
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if ((i % 3 == 1 || (i % 3 == 0 && i + 1 == n)) && (j % 3 == 1 || (j % 3 == 0 && j + 1 == m)))
                cout << 1;
            else if (maxx > k)
            {
                --maxx;
                cout << 1;
            }
            else
                cout << 0;
        }

        cout << endl;
    }
}

F – 徽章计数

算法：

组合数学。

思路：

对于每个数值 \(x\)，如果有 \(cnt[x]\) 个小朋友，那么值为 \(x\) 的小朋友会被分为 \(\frac{cnt[x]}{x}\) 组。

考虑无解的情况：

• \(cnt[x]\) 无法被 \(x\) 整除；
• \(\sum \frac{cnt[x]}{x} > m\)。

对于每个数值 \(x\)，需要将 \(cnt[x]\) 个小朋友划分为 \(k = \frac{y}{x}\)​ 个大小为 \(x\) 的组，令 \(y = cnt[x]\)。

• 先对这 \(y\) 个小朋友进行全排列，方案数为 \(y!\)；
• 将排列分为 \(k\) 组，每隔 \(x\) 个分为一组，共有 \(1\) 种方案；
• 每组内的小朋友顺序无关（既每一组内的小朋友顺序任意），所以需要除去每组的排列数 \(x!\)，共除以 \(x!^{k}\)；
• 组与组之间的顺序无关，需要再除以 \(k​!\)；
• 因此数值 \(x\) 的方案数为 \(\frac{y!}{x!^{k} * k!}\)。

对于 \(\sum \frac{cnt[x]}{x}\) 组小朋友，需要从 \(m\) 个徽章中选出 \(\sum \frac{cnt[x]}{x}\) 个分配给小朋友，那么小朋友之间徽章分配方案数为 \(P(m, \sum \frac{cnt[x]}{x}) \)种。

因此总的方案数为 \(\sum \frac{y!}{x!^{k} * k!} * P(m, \sum \frac{cnt[x]}{x})\)。

计算过程中对答案取模即可。

关键代码：

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

vector<ll> fact(N), inv(N);
void init()
{
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv[N - 1] = qmi(fact[N - 1], MOD - 2, MOD);
    for (int i = N - 2; i >= 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
}

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

    map<int, ll> cnt;
    for (auto &x : a)
        ++cnt[x];

    ll sum = 0;
    ll tot = 0;
    for (auto &[x, y] : cnt)
    {
        if (y % x)
        {
            cout << 0 << endl;
            return;
        }

        tot += y / x;
        sum += y;
    }

    if (sum != n)
    {
        cout << 0 << endl;
        return;
    }

    ll ans = 1;
    while (tot--)
    {
        ans = (ans * m) % MOD;
        --m;
    }

    for (auto [x, y] : cnt)
    {
        ll k = y / x;
        ll Y = fact[y];
        ll X = qmi(inv[x], k, MOD);
        ll K = inv[k];
        ans = ans * Y % MOD * X % MOD * K % MOD;
    }

    cout << ans << endl;
}