2024郑州邀请赛

官方题解：Solution

F 优秀字符串

签到

void solve {
    int n;cin >> n;
    int cnt = 0;
    while (n--) {
        string s;cin >> s;
        if (s.size() == 5 && s[2] == s[4]) {
            set<char>st(s.begin(), s.begin() + 4);
            if (st.size() == 4) {
                cnt++;
            }
        }
    }
    cout << cnt << '\n';
}

J 排列与合数

void solve() {
    string s;cin >> s;
    for (int i = 4;i >= 0;i--) {
        if ((s[i] - '0') % 2 == 0) {
            swap(s[i], s[4]);
            cout << s << "\n";
            return;
        }
    }
    cout << "97531\n";
}

M 有效算法

给出长度为 $n$ 的正整数序列 $a_{n}$ 和 $b_{n}$ 。对于每个 $a_{i} (1 \leq i \leq n)$ ，进行恰好一次以下操作：

将 $a_{i}$ 变成满足 $| a_{i} - x | \leq k \times b_{i}$ 的任意整数 x。

请你求出最小的非负整数 $k$ ，使得存在至少一种方法使得操作后序列 $a_{n}$ 所有数都相等。

很明显的二分答案，若对于所有元素 $x$ 取值范围区间有交集则存在这个 $k$ ，否则不存在。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];
    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r >> 1;
        int x = 1, y = 1e18;
        for (int i = 1;i <= n;i++) {
            x = max(x, a[i] - mid * b[i]);
            y = min(y, a[i] + mid * b[i]);
        }
        if (x > y)l = mid + 1;
        else r = mid;
    }
    cout << l << '\n';
}

H 随机栈

Toxel 获得了一个随机的 “栈”。这个栈可被视为一个多重集 $S$ ，从一个非空的随机栈 $S$ 中取出一个元素时，有可能从中取出任何一个元素，其中每个元素被取出的概率是相等的。取出该元素后，该元素会从集合中删除。以 $1, 2, 2$ 为例，有 $\frac{1}{3}$ 的概率取出 1，使得集合变为 $2, 2$ ，有 $\frac{2}{3}$ 的概率取出 2，使得集合变为 $1, 2$ 。每次取出元素的事件相互独立。

Toxel 正在对这个集合做一些操作。集合初始时为空，它总共进行了 $2 n$ 次操作，其中 $n$ 次操作为插入， $n$ 次操作为取出。现在，Toxel 告诉了你它操作的顺序以及每次插入的数，且保证每次取出时，集合非空。Toxel 想知道，如果把每次取出数排成一个序列，那么这个序列递增的概率是多少？

这里，递增的严格定义是：取出数列的每一项（除最后一项）小. 于. 等. 于. 它的后一项。

由于答案可能不是整数，为了方便计算，你只需要求出这个值对 $998 244 353$ 取模的结果

即 $\frac{p}{q} \to p \times q^{- 1} \mod 998 244 353$ 。

与官方做法不同，用了 multiset 的方式，更加方便

#define int long long
constexpr int mod = 998244353;
int inv(int a, int b = mod - 2) {
    int ans = 1;
    while (b) {
        if (b & 1)ans = (ans * a) % mod;
        a = (a * a) % mod;b >>= 1;
    }
    return ans;
}
void solve() {
    int n;cin >> n;
    multiset<int>s;
    int p = 1, q = 1;
    int mx = -1;
    map<int, int>mp;
    for (int i = 1;i <= 2 * n;i++) {
        int x;cin >> x;
        if (x >= 0) {
            if (x < mx) {
                cout << "0\n";exit(0);
            }
            s.insert(x);mp[x]++;
        } else {
            int cnt = mp[*s.begin()];
            p = (p * cnt) % mod;
            q = (q * s.size()) % mod;
            mx = max(mx, *s.begin());
            mp[*s.begin()]--;
            s.erase(s.begin());
        }
    }
    cout << p * inv(q) % mod << '\n';
}

B 扫雷 1

Toxel 喜欢玩扫雷，但是他玩的扫雷游戏有名为 “地雷探测器” 的特殊道具。

具体来说，Toxel 会进行 $n$ 轮扫雷。每轮扫雷开始之前，Toxel 会获得 1 枚扫雷币。扫雷币在每轮扫雷结束后不会回收，可以保留至下一轮扫雷。Toxel 知道，在第 $i$ 轮（ $1 \leq i \leq n$ ）扫雷中，花费 $c_{i}$ 枚扫雷币可以购买一个地雷探测器，清除地图中的一个雷。地雷探测器在一轮扫雷中可以购买任意次。

现在 Toxel 想知道，在这 $n$ 轮扫雷中最多能购买多少个地雷探测器呢？

因为这题队友出锅，错失铜牌，我真服，签到都签不明白，趁早回家种田吧

贪心：在一段距离中取这段的最小值一定是最优的，一段一段来看即可。

#define int long long
void solve() {
    int n;cin >> n;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;a[i] = {x,i};
    }
    sort(a.begin() + 1, a.end(), [](auto x, auto y) {
        if (x.first == y.first)return x.second > y.second;
        return x.first < y.first;
        });
    int id = 0, cnt = 0, yu = 0;
    for (int i = 1;i <= n;i++) {
        auto [x, y] = a[i];
        if (y > id) {
            cnt += (y - id + yu) / x;
            yu = (y - id + yu) % x;
            id = y;
        }
    }
    cout << cnt << '\n';
}

L Toxel 与 PCPC II

Toxel 正在参加 PCPC（Pokémon Center Programming Contest）比赛。它写的一段代码中有不少 bug，正在调试。这份代码总共有 $n$ 行，而且经验丰富的 Toxel 已经知道了其中 $m$ 行代码有 bug，并锁定了这 $m$ 行的具体位置。但是 Toxel 还需要进行一些调试以了解错误的具体细节并修复它们。

Toxel 会进行多次调试。每次调试时，Toxel 可以任选一个 $i$ ，使得程序从第 1 行开始，顺序运行完第 $i$ 行后退出。Toxel 可以通过这 $i$ 行代码运行的一些输出结果来进行 debug。运行这 $i$ 行代码总共需要 $i$ 秒。接下来，Toxel 会一次性地 debug 这 $i$ 行代码，并修复所有这 i 行中的所有 bug。bug 数量越多，修复所需的时间也越多。设这 i 行代码中现存的 bug 数量为 $x$ ，那么 Toxel 需要 $x^{4}$ 秒来 debug 并完成修复。修复后，这 $i$ 行代码中将不再存在任何 bug。

PCPC 的赛场争分夺秒。请你帮 Toxel 计算一下，它最短需要多少秒才能完成 debug，修复整个代码中的所有漏洞？

简单 DP

#define int long long
void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(m + 1);
    for (int i = 1;i <= m;i++)cin >> a[i];
    vector<int> f(m + 2, 1e18);
    f[1] = 0;
    for (int i = 1;i <= m;i++) {
        for (int j = i + 1;j <= m + 1 && j - i <= 500;j++) {
            f[j] = min(f[j], f[i] + a[j - 1] + (j - i) * (j - i) * (j - i) * (j - i));
        }
    }
    cout << f[m + 1] << '\n';
}

A Once In My Life

对于小 A 而言，数位包含 $1 \sim 9$ ，并且至少两个数位是 $d (1 \leq d \leq 9)$ 的 十进制正整数 都是幸运数。

当 $d = 3$ 时，显然 $1234567890123$ 是小 A 的幸运数，但 $987654321$ 因为数位 $3$ 仅出现了一次而不是幸运数， $998244353$ 因为缺少数位 $1, 6, 7$ 而不是幸运数。

现在小 A 有一个正整数 $n$ ，并给出正整数 $d$ 。他想找到正整数 $k$ 使得二者的乘积 $n \cdot k$ 是幸运数。你能用计算机辅助他的计算 $k (k \leq 2 \times 10^{10})$ 吗？

构造

对于官方的题解：
$N = (1234567890 + d) \cdot 10^{⌈ \log_{10} n ⌉}$

$K = ⌈ \frac{N}{n} ⌉ \leq 2 \cdot 10^{9} \cdot \frac{10^{⌈ \log_{10} n ⌉}}{n} \leq 2 \cdot 10^{10}$

$K = ⌈ \frac{(1234567890 + d) \cdot 10^{⌈ \log_{10} n ⌉}}{n} ⌉$

cout << ((1234567890 + d) * (int)pow(10, ceil(log10(n))) + n - 1) / n << '\n';

这里其实写的太急躁，容易出问题，可以将 $10^{⌈ \log_{10} n ⌉}$ 的 $10$ 一个一个乘起来，这样不会丢失精度

K 树上问题

378 QAQ 有一棵由 $n$ 个节点组成的无根树，节点编号从 $1$ 到 $n$ ，每个节点有一个正整数点权。

378 QAQ 认为一个节点是美丽节点，当且仅当该节点作为根时，对于除根节点以外的所有节点，其点权都 不小于 其父亲节点的点权的 $\frac{1}{2}$ 。

请你计算出有多少个节点是美丽节点。

换根 DP 板子题, 得多体会如何推导换根的过程。

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 1;i < n;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);g[v].push_back(u);
    }
    vector<int> f(n + 1);
    auto dfs1 = [&](auto self, int u, int fa = -1) ->void {
        for (auto v : g[u]) {
            if (v == fa)continue;
            if (a[v] * 2 >= a[u])f[u]++;
            self(self, v, u);
            f[u] += f[v];
        }
        };
    dfs1(dfs1, 1);

    auto dfs2 = [&](auto self, int u, int fa = -1) ->void{
        for (auto v : g[u]) {
            if (v == fa)continue;
            f[v] = f[u] - (a[v] >= (a[u] + 1) / 2) + (a[u] >= (a[v] + 1) / 2);
            self(self, v, u);
        }
        };
    dfs2(dfs2, 1);
    int ans = 0;
    for (int i = 1;i <= n;i++)ans += (f[i] == n - 1);
    cout << ans << '\n';
}

C 中二病也要打比赛

给定一个数组 $A$ ，现在你需要构造一个映射 $f (1 \leq f_{1 \leq i \leq n} \leq n)$ ， $B_{i} = f (A_{i})$ ，使得构造出的 $f$ 满足 $B_{i}$ 单调不降。

求构造出的 $f (x) \neq x$ 的数量最少的 $f$

思维+LIS/数据结构/DP

LIS：最长上升子序列

对于本题：若没有出现数字相等的情况，则答案就是求最长上升子序列。

若有两个数字相等，则在这个区间内的所有数字映射的答案都相等，形式为 $2, \dots, 3, \dots 2, \dots 3, \dots$ (可能会有嵌套的情况)。

对于每一个这样的区间，进行降序排序，再求 LIS，就得到了最多的不变的个数。

关键是如何证明对每个这样的区间进行降序排序再 LIS 得到最多的不变的个数？Waiting...
应该是因为降序后让这个区间只能有一个数字算入进去

jiangly:

可以学习这种代码技巧，感觉很好用。

void solve() {
    int n;cin >> n;
    vector<int> a(n), l(n, n), r(n, -1);
    for (int i = 0;i < n;i++) {
        cin >> a[i];a[i]--;
        l[a[i]] = min(l[a[i]], i);//用于求对于每个数字的最左边到最右边的区间，若不存在，l_i=n,r_i=-1
        r[a[i]] = i;
    }

    vector<int> d(n);//用于求出有多少段以及每段的位置方便进行降序排序
    int tot = 0;
    for (int i = 0;i < n;i++) {
        if (l[i] <= r[i]) {
            d[l[i]]++;
            d[r[i]]--;
            tot++;
        }
    }
    for (int i = 1;i < n;i++)d[i] += d[i - 1];

    int lst = 0;
    for (int i = 1;i <= n;i++) {
        if (d[i - 1] == 0) {
            sort(a.begin() + lst, a.begin() + i, greater<int>());
            lst = i;
        }
    }
    vector<int> f;
    for (auto x : a) {
        auto it = lower_bound(f.begin(), f.end(), x);
        if (it == f.end()) {
            f.push_back(x);
        } else {
            *it = x;
        }
    }
    cout << tot - f.size() << '\n';
}

有大佬写的树状数组： 2024 CCPC 郑州邀请赛暨河南省赛题解 - sleeeeeping - 博客园

D 距离之比

给定在平面上互不重合的 $n$ 个点 $P_{1}, P_{2}, \dots P_{n}$ ，

(下标为 1 代表曼哈顿距离- $| x_{1} - x_{2} | + | y_{1} - y_{2} |$ ，2 代表欧几里得距离- $\sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}}$ )

求： $max_{1 \leq i \leq j \leq n} \frac{{| | P_{i} P_{j} | |}_{1}}{{| | P_{i} P_{j} | |}_{2}}$

简单数学：

2024CCPC郑州邀请赛暨河南省赛（A,B,C,D,F,G,H,J,K,L,M）

令 $\tan θ = \frac{| x_{i} - x_{j} |}{| y_{i} - y_{j} |}$ ,化简后 $\frac{{| | P_{i} P_{j} | |}_{1}}{{| | P_{i} P_{j} | |}_{2}} = | \sin θ + \cos θ | = \sqrt{2} \sin (θ \pm \frac{π}{4})$

当 $θ = 45^{\circ} or 135^{\circ}$ 时，才能达到最大。这时 $\tan θ = 1 \to | x_{i} - x_{j} | = | y_{i} - y_{j} |$

去掉绝对值可以得到 $x_{i} - y_{i} = x_{j} - y_{j} or x_{i} + y_{i} = x_{j} + y_{j}$

所以分别让按照横坐标按照 $x + y$ 和 $x - y$ 排序，取其中最大值即可。

#define int long long
void solve() {
    int n;cin >> n;
    vector<pair<int, int>> p(n);
    for (int i = 0;i < n;i++)cin >> p[i].first >> p[i].second;
    sort(p.begin(), p.end(), [](auto x, auto y) {
        return x.first + x.second < y.first + y.second;
        });
    double ans = 1;
    for (int i = 1;i < n;i++) {
        auto [x2, y2] = p[i];
        auto [x1, y1] = p[i - 1];
        ans = max(ans, (abs(x1 - x2) + abs(y1 - y2)) / hypot(x1 - x2, y1 - y2));
    }
    sort(p.begin(), p.end(), [](auto x, auto y) {
        return x.first - x.second < y.first - y.second;
        });
    for (int i = 1;i < n;i++) {
        auto [x2, y2] = p[i];
        auto [x1, y1] = p[i - 1];
        ans = max(ans, (abs(x1 - x2) + abs(y1 - y2)) / hypot(x1 - x2, y1 - y2));
    }

    cout << fixed << setprecision(15) << ans << '\n';
}