CSP模拟赛 #44

2024 最后一场 CSP 模拟赛。

A

给定 \(x,k\)，求最小的 \(y\) 满足 \(y\ge x\) 且除了 \(k\) 个数位，其他数位均相同。

\(1\le n\le 10^{17}, \ 0\le k\le 1\)

暴力枚举。

B

给定 \(n\) 个三元组 \((a_1,b_1,c_1), \dots (a_n, b_n, c_n)\)，每个数 \(\in [0, 9]\)。求有多少种排列三元组方案，设 \(A,B,C\) 为对应 \(a_{1\dots n},b_{1\dots n},c_{1\dots n}\) 依次连接起来的结果，满足 \(A,B,C\) 无前导零且 \(A + B = C\)，答案模 \(10^9 + 7\)。

\(2\le n\le 2\times 10^5\)

考虑 \((a_i, b_i, c_i)\)，设 \(p_i\) 为其是否需要前一位进 \(1\)，\(q_i\) 为是否向下一位进 \(1\)。连边 \(p_i\to q_i\)，相当于求欧拉回路数量。由于不能有前导零，枚举最后一条经过的边即可。

C

一个由 \(\mathtt {abc}\) 组成的长度为 \(n\) 的字符串 \(s\)，求有多少对二元组 \((i, j)\) 满足 \(i < j\) 且交换 \(s_i,s_j\) 后可以通过 CSP-S2023 消消乐 的方法消除整个字符串。

考虑分治，设当前分治区间为 \([l, r]\)，中点为 \(m\)，统计 \(i\in [l, m], \ j \in [m + 1, r]\) 的二元组对数。

选择了 \(i,j\)，我们设 \(h_i,\ h_j\) 分别为 \([1, m]\) 和 \([m + 1, n]\) 在交换后的栈的哈希值，那么需要统计 \(h_i = h_j\) 的对数。

栈有可撤销性，考虑将 \([m + 1, r]\) 加入后缀栈后分治 \([l, m]\)，右边同理。合并两个栈时，考虑二分 lcp 长度，合并哈希值。

时间复杂度 \(\mathcal O(n\log n)\)。

D

一个环形排列，从中砍 \(k\) 刀，求每段的 \(\max(\text{前缀最大值个数}, \text{后缀最大值个数})\) 之和最大是多少。

\(1\le k\le n\le 6\times 10^5\)

首先断环为链，钦定最大值所在段取的是后缀最大值，那么把最大值排在第一个位置，然后任意留最后一段陪葬。

设 \(f_{i, j}\) 表示前 \(j\) 个数分 \(i\) 段的答案，考虑优化。设 \(p_i, \ q_i\) 表示 \(a_i\) 左右和右边第一个比他大的数的位置。

那么 \(f_{i, j} = \max\limits{k\le i} \{f_{i - 1, k - 1} + \max(\sum\limits_{x = k} ^ j [k > p_x], \sum\limits_{x = k} ^ j [i < q_x])\}\)，显然可以线段树优化。

发现维护的形式是：后缀 \(+1\)，末尾加入一个数，求全局最大值。考虑设 \(c_k\) 为 \([k, i]\) 的最大值，维护 \(c\) 的差分数组，用并查集找到上一个差分数组中的非零位置。