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

A – 小红的点构造

算法：

    构造，贪心。

思路：

    无。

关键代码：

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

    cout << x + 1 << ' ' << y + 1 << 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, greater<int>());

    for (auto x : a)
        cout << x << ' ';
    cout << endl;
}

C – 小红下象棋

算法：

    模拟。

思路：

    无。

关键代码：

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

    int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
    int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

    set<pii> s;
    for (int i = 0; i < n; ++i)
    {
        auto [xx, yy] = a[i];
        for (int j = 0; j < 8; ++j)
        {
            int a = xx + dx[j], b = yy + dy[j];

            s.insert({a, b});
        }
    }

    if (s.count({x, y}))
    {
        cout << "B" << endl;
        return;
    }

    int cnt = 0;
    for (int i = -1; i <= 1; ++i)
    {
        for (int j = -1; j <= 1; ++j)
        {
            if (!i && !j)
                continue;

            if (s.count({x + i, y + j}))
                ++cnt;
        }
    }

    if (cnt == 8)
        cout << "A" << endl;
    else
        cout << "C" << endl;
}

D – 小红的区间查询

算法：

    数论。

思路：

    要求找满足以下等式的 \(x\) 的数量：

    \(x – a \equiv 0 \pmod{x – b}\)

    消除等式前面变量 \(x\)，使用 \(x – b + b\) 替换 \(x\) 得：

\(x – b + b – a \equiv 0 \pmod{x – b} \Rightarrow b – a \equiv 0 \pmod{x – b}\)

    \(x\) 的范围为 \([l, r]\)，所以 \(x – b\) 范围为 \([l – b, r – b]\)。

    此时问题转化为，\([l – b, r – b]\) 范围内有多少元素是 \(b – a\) 因子。

    题目是多组测试数据，不能每组测试数据都暴力找，考虑预处理。

    定义 \(divs[i][j]\) 为 \(divs[i][j]\) 是 \(i\) 的因子，使用筛法将每个数字都存到其倍数中。

    对于每组测试数据，在 \(divs[b – a]\) 中二分有多少个数字属于\([l – b, r – b]\)。

关键代码：

vector<vector<int>> v(N + 1);
void init()
{
    for (int i = 1; i <= N; ++i)
        for (int j = i; j <= N; j += i)
            v[j].push_back(i);
}

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

    ll d = b - a;
    ll L = l - b, R = r - b;

    int pos1 = ranges::lower_bound(v[d], L) - v[d].begin();
    int pos2 = ranges::upper_bound(v[d], R) - v[d].begin();

    cout << pos2 - pos1 << endl;
}

E – 小红的gcd

算法：

    \(dp\)。

思路：

    数字三角形模型。

    路径开头和结尾是矩阵起点和终点，那么就可确定好串中的第一段和最后一段的字符。

    \(n * n <= 1e6\) 且是求路径总数，考虑二维 \(dp\)。

    定义 \(dp[i][j]\) 为到达 \((i, j)\) 点的路径总数。

    由于移动只能向右和向下移动，那么 \((i, j)\) 点必然是第 \(i + j – 1\) 个到达的点；如果 \((i, j)\) 在好串中对应的字符不一样，那么 \((i, j)\) 点就不可达。

    将矩阵分为三部分处理进行状态转移即可，状态转移比较简单，看代码理解即可。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<string> g(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> g[i];
        g[i] = ' ' + g[i];
    }

    int k = (2 * n - 1) / 3;

    char sta = g[1][1], en = g[n][n];

    vector dp(n + 1, vector<ll>(n + 1, 0));
    dp[1][1] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            int cur = i + j - 1;

            if (cur <= k)
            {
                if (g[i][j] == sta)
                {
                    if (g[i - 1][j] == sta)
                        dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                    if (g[i][j - 1] == sta)
                        dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
                }
            }
            else if (cur <= 2 * k)
            {
                if (g[i][j] != sta && g[i][j] != en)
                {
                    if (cur == k + 1)
                    {
                        if (g[i - 1][j] == sta)
                            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                        if (g[i][j - 1] == sta)
                            dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
                    }
                    else
                    {
                        if (g[i - 1][j] == g[i][j])
                            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                        if (g[i][j - 1] == g[i][j])
                            dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
                    }
                }
            }
            else
            {
                if (g[i][j] == en)
                {
                    if (cur == 2 * k + 1)
                    {
                        if (g[i - 1][j] != sta && g[i - 1][j] != en)
                            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                        if (g[i][j - 1] != sta && g[i][j - 1] != en)
                            dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
                    }
                    else
                    {
                        if (g[i - 1][j] == en)
                            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                        if (g[i][j - 1] == en)
                            dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
                    }
                }
            }
        }
    }

    cout << dp[n][n] % MOD << endl;
}

F – 小红的树构造

算法：

    树，构造。

思路：

    先考虑边界情况：

• 当 \(k == n – 1\) 时，只有一个根节点，其余全为叶子节点。
• 当 \(k == 1\) 时，需要构造出两个非叶子节点度数互质，这样的树点数最小为 \(5\)，\(n < 5\) 且 \(k == 1\) 时无解。

    树，\(n\) 个点，\(n – 1\) 条边，\(2 * n – 2\) 度。

    设存在 \(x\) 个叶子节点，\(n – x = y\) 个非叶子节点，非叶子节点度数总和 \(n + n – 2 – x = n + y – 2\) 度，所有非叶子节点度的 \(gcd = k\)，那么每个非叶子节点的度都是 \(k\) 的倍数，那么 \((n + y – 2) % k == 0\)。

    将 \(n + y – 2\) 按 \(k\) 为一单位分为 \(d\) 份，每个非叶子节点会被分配得到整数份。

    考虑枚举 \(x\)：

• 如果当前 \(x\) 满足 \(n + y – 2\) 是 \(k\) 的倍数且 \((n + y – 2) / k\) 大于等于 \(y\)，就说明当前 \(x\) 存在合法构造；
• 为 \(y – 1\) 个非叶子节点每个分配 \(k\) 度，最后一个非叶子节点分配 \((n + y – 2) – k * (y – 1)\) 度；
• 将所有非叶子节点连成一条链，除去两端的叶子节点消耗 \(1\) 度外，剩余每个消耗 \(2\) 度，共消耗 \(2 * y – 2\) 度；
• 最后非叶子节点共剩余 \((n + y – 2) – 2 * y – 2 = n – y = x\) 度，根据非叶子节点的度数连接对应个数的叶子节点即可。

关键代码：

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

    if (k == 1)
    {
        if (n < 5)
        {
            cout << "No" << endl;
            return;
        }

        cout << "Yes" << endl;
        cout << 1 << ' ' << 2 << endl;
        cout << 3 << ' ' << 2 << endl;
        cout << 4 << ' ' << 2 << endl;
        cout << 4 << ' ' << 5 << endl;

        for (int i = 6; i <= n; ++i)
            cout << 5 << ' ' << i << endl;

        return;
    }

    if (k == n - 1)
    {
        cout << "Yes" << endl;
        for (int i = 2; i <= n; ++i)
            cout << 1 << ' ' << i << endl;

        return;
    }

    for (int x = 2; x <= n - 2; ++x)
    {
        int y = n - x;

        int du = n + y - 2;

        if (du % k)
            continue;
        if (du / k < y)
            continue;

        cout << "Yes" << endl;

        vector<int> cnt(n + 1, 0);
        for (int i = x + 1; i < n; ++i)
        {
            cnt[i] = k;
            du -= k;
        }

        cnt[n] = du;

        for (int i = x + 1; i < n; ++i)
        {
            cout << i << ' ' << i + 1 << endl;
            --cnt[i], --cnt[i + 1];
        }

        int u = 1;
        for (int i = x + 1; i <= n; ++i)
        {
            while (cnt[i])
            {
                --cnt[i];
                cout << i << ' ' << u++ << endl;
            }
        }

        return;
    }

    cout << "No" << endl;
}