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

题目按照通过人数降序排序。

B – 智乃的瓷砖

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<string> g(n, string(m, '/'));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (i == 0 && j == 0)
                continue;

            if (j == 0)
            {
                if (g[i - 1][j] == '/')
                    g[i][j] = '\\';
                else
                    g[i][j] = '/';
            }
            else
            {
                if (g[i][j - 1] == '/')
                    g[i][j] = '\\';
                else
                    g[i][j] = '/';
            }
        }
    }

    for (auto s : g)
    {
        for (auto c : s)
            cout << c;

        cout << endl;
    }
}

J – 智乃的幻方

算法：

模拟。

思路：

无。

关键代码：

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

    int sum = accumulate(all(a[0]), 0);
    int cnt1 = 0, cnt2 = 0;
    set<int> S;
    for (int i = 0; i < 3; ++i)
    {
        cnt1 += a[i][i];
        cnt2 += a[i][2 - i];

        int tot1 = 0, tot2 = 0;
        for (int j = 0; j < 3; ++j)
        {
            S.insert(a[i][j]);
            tot1 += a[i][j];
            tot2 += a[j][i];
        }

        if (tot1 != sum || tot2 != sum)
        {
            cout << "No" << endl;
            return;
        }
    }

    if (cnt1 != sum || cnt2 != sum)
    {
        cout << "No" << endl;
        return;
    }

    if (S.size() == 9 && *S.begin() == 1 && *S.rbegin() == 9)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

G – 智乃的箭头魔术

算法：

模拟。

思路：

无。

关键代码：

void miyan()
{
    string s = "0112233445142015320125410214530214510214102302142025101203201451451522302514203214510021454101002532";

    int now = 0;
    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == '0')
        {
            if (now == 0)
                now = 3;
            else if (now == 1)
                now = 2;
            else if (now == 2)
                now = 1;
            else
                now = 0;
        }
        else if (s[i] == '1')
        {
            if (now == 0)
                now = 0;
            else if (now == 1)
                now = 3;
            else if (now == 2)
                now = 2;
            else
                now = 1;
        }
        else if (s[i] == '2')
        {
            if (now == 0)
                now = 1;
            else if (now == 1)
                now = 0;
            else if (now == 2)
                now = 3;
            else
                now = 2;
        }
        else if (s[i] == '3')
        {
            if (now == 0)
                now = 2;
            else if (now == 1)
                now = 1;
            else if (now == 2)
                now = 0;
            else
                now = 3;
        }
        else if (s[i] == '4')
        {
            if (now == 0)
                now = 1;
            else if (now == 1)
                now = 2;
            else if (now == 2)
                now = 3;
            else
                now = 0;
        }
        else
        {
            if (now == 0)
                now = 3;
            else if (now == 1)
                now = 0;
            else if (now == 2)
                now = 1;
            else
                now = 2;
        }

        cout << now;
    }
}

D – 智乃的果子

算法：

贪心，堆。

思路：

经典贪心题目。

原题：https://www.luogu.com.cn/problem/P1090

贪心策略：从最小的开始合并。

过程使用堆模拟即可，细节看代码。

关键代码：

using pll = pair<ll, ll>;

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

    priority_queue<pll, vector<pll>, greater<>> q;
    for (int i = 0; i < n; ++i)
    {
        ll c, w;
        cin >> c >> w;
        q.push({w, c});
    }

    ll ans = 0;
    while (q.size())
    {
        auto [w, c] = q.top();
        q.pop();

        while (q.size() && q.top().first == w)
        {
            auto [nw, nc] = q.top();
            q.pop();

            c += nc;
        }

        ll t = c / 2;

        if (t)
        {
            ans = (ans + 2ll * t % MOD * w % MOD) % MOD;

            q.push({w * 2ll, t});
        }

        if ((c & 1) && q.size())
        {
            auto [nw, nc] = q.top();
            q.pop();

            ans = (ans + w + nw) % MOD;

            q.push({w + nw, 1});

            if (nc > 1)
                q.push({nw, nc - 1});
        }
    }

    cout << ans << endl;
}

F – 智乃的算法竞赛群友

算法：

贪心，\(dp\)。

思路：

只有三种填充策略：

• 填充 \(qcjjkktd\)，贡献 \(a + b\) 快乐值；
• 填充 \(qcjjkkt\)，贡献 \(a\) 快乐值；
• 填充 \(td\)，贡献 \(b\) 快乐值。

三种填充的长度分别为 \(2, 7, 8\)，其最大公约数为 \(56\)，因此对于长度为 \(56 * k\) 的区间，可以直接贪心使用任意一种策略填满。

而剩余的部分长度必然小于 \(56\)，可以直接暴力填充，考虑 \(dp\) 填充剩余的部分。

定义 \(dp[i]\) 为填充前 \(i\) 个位置的最大快乐值是多少。

容易得到状态转移公式为：\(dp[i] = max({dp[i – 2] + b, dp[i – 7] + a, dp[i – 8] + a + b})\)。

注意边界情况。

剩余的长度小于 \(56\) 可能会出一些问题，考虑剩余的长度再加上 \(56\)。

关键代码：

void miyan()
{
    ll n, a, b;
    cin >> n >> a >> b;

    ll ans = 0;
    if (n > 112)
    {
        ll m = (n / 56 - 1) * 56;

        ans = max({m / 2 * b, m / 7 * a, m / 8 * (a + b)});

        n -= m;
    }

    vector<ll> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        if (i >= 2)
            dp[i] = max(dp[i], dp[i - 2] + b);
        if (i >= 7)
            dp[i] = max(dp[i], dp[i - 7] + a);
        if (i >= 8)
            dp[i] = max(dp[i], dp[i - 8] + a + b);
    }

    cout << ans + dp[n] << endl;
}

E – 智乃的最大子段和取模

算法：

\(STL\)，贪心，二分，分类讨论。

思路：

注意：题目为 \(0-based\)，以下题解为 \(1-based\)。

在模 \(p\) 意义下 \([l, r]\) 子段和为 \((s[r] – s[l – 1] + p) \text{ mod } p\)（\(s[x]\) 表示数组下标 \([1, x]\) 范围的和），对于每个 \(r\) 我们可以找到满足条件最大的 \(l\) 并更新全局答案，使得 \((s[r] – s[l – 1] + p) \text{ mod } p\) 的值最大。

在模 \(p\) 的意义下，\(s[l – 1]\) 的值可能大于 \(s[r]\)、也可能小于或者等于 \(s[r]\)，分类讨论：

• 当 \(s[r] = s[l – 1]\) 时，子段和为 \(0\)，可以直接忽略该情况；
• 当 \(s[r] > s[l – 1]\) 时，子段和为 \(s[r] – s[l – 1]\)，想让子段和最大，就要最小化 \(s[l – 1]\)，由于 \(s[0] = 0\)，因此 \(l – 1\) 可以直接选择 \(0\)，那么这种情况的最优解就是 \([1, r]\)；
• 当 \(s[r] < s[l – 1]\) 时，子段和为 \(s[r] + p – s[l – 1]\)，想让子段和最大，需要让 \(s[l – 1]\) 满足大于 \(s[r]\)，且尽可能小，因此直接找大于 \(s[r]\) 的第一个 \(s[l – 1]\) 即可。

对于第三种情况可以使用 \(map\) 优化寻找过程，使得题目可以在 \(O(logn)\) 时间内找到满足条件的 \(s[l – 1]\)。

关键代码：

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

    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        sum[i] = (sum[i - 1] + a[i]) % p;

    int ans = 0, L = 0, R = 0;
    map<int, int> hash;
    hash[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        int cur = sum[i] - 0;
        if (cur > ans)
        {
            ans = cur;
            L = 1, R = i - 1;
        }

        auto it = hash.upper_bound(sum[i]);

        if (it != hash.end())
        {
            auto [val, pos] = *it;

            int cur = (1ll * sum[i] + p - val) % p;

            if (cur > ans)
            {
                ans = cur;
                L = pos, R = i - 1;
            }
        }

        if (!hash.count(sum[i]))
            hash[sum[i]] = i;
    }

    cout << L << ' ' << R << ' ' << ans << endl;
}

I – 智乃挖坑

算法：

等差数列差分，二分。

思路：

对于每次挖坑的序偶 \(<p, f>\) 其实就是在数组上进行两次等差数列修改，既 \((1, f)\) 和 \((f – 1, 1)\)：

• 其中 \((1, f)\) 为在数组下标 \([p – f + 1, p]\) 范围上减去一个首项为 \(1\)，尾项为 \(f\)，公差为 \(1\) 的等差数列；
• \((f – 1, 1)\) 同理；
• 未考虑边界情况，读者请自行考虑。

以上直接套用等差数列差分模板即可，其可以在 \(O(1)\) 时间内对数组进行等差数列修改。

等差数列差分讲解：前缀和详解及其拓展 – MiyanLog

对于第几次挖坑挖出边界，可以使用二分答案找出最后一次未挖出边界的操作的下标。

具体实现看代码。

关键代码：

using pll = pair<ll, ll>;

void miyan()
{
    ll n, m, h;
    cin >> n >> m >> h;

    vector<pll> a(m + 1);
    for (int i = 1; i <= m; ++i)
        cin >> a[i].first >> a[i].second;

    auto add = [&](vector<ll> &b, int l, int r, ll s, ll e) -> void
    {
        ll d = 0;
        if (l < r)
            d = (e - s) / (r - l);

        b[l] += s;
        b[l + 1] += d - s;
        b[r + 1] += -e - d;
        b[r + 2] += e;
    };

    auto check = [&](int x) -> bool
    {
        vector<ll> b(n + 3, 0);
        for (int i = 1; i <= x; ++i)
        {
            auto [p, f] = a[i];

            int L1 = max(1ll, p - f + 1);
            int R1 = p;
            ll s1 = f - p + L1;
            ll e1 = f;

            add(b, L1, R1, s1, e1);

            if (p < n && f > 1)
            {
                int L2 = p + 1;
                int R2 = min(n, p + f - 1);

                ll s2 = f - 1;
                ll e2 = f + p - R2;

                add(b, L2, R2, s2, e2);
            }
        }

        for (int i = 1; i <= n; ++i)
            b[i] += b[i - 1];
        for (int i = 1; i <= n; ++i)
            b[i] += b[i - 1];

        for (int i = 1; i <= n; ++i)
            if (b[i] > h)
                return 0;

        return 1;
    };

    int l = 0, r = m;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    if (l == n)
        cout << "No" << endl;
    else
        cout << "Yes" << endl
             << l + 1 << endl;
}