4.4
2026-04-04 多校联考 ---(湖南师大附中)
t1
A. 小 K 的疑惑 (puzzle)
原
给定两个正整数 \(n,b\)，求一个 \(k \gt 0\) 使得 \(n \mid k\)，且 \(k\) 在 \(b\) 进制下的非 \(0\) 位数最少。
\(1 \leq n \leq 10^7,2 \leq b \leq 10^7\)。
1
是 \(n\) 的倍数的限制，可以表达成 \(\bmod n\) 为 \(0\)。
而 \(b\) 进制的组织形式，自然是每次加入一个数 \([0,b)\)，然后整体乘 \(b\)。
不妨定义 \(f_i\) 表示膜 \(n\) 为 \(i\) 的 \(b\) 进制数的最少非 \(0\) 位置。
初始化就是 \(\forall i \in [1,b),f_{i \bmod n} = 1\)。然后一个 \(f_i\) 可以转移到 \(f_{bi \bmod i}\) 和 \(f_{i+j},j \in [0,b)\)。对后者的转移要加上代价 \(1\)。
用 01bfs 可以做到时间复杂度 \(O(bn)\)。
2
第一种转移的边数是 \(O(n)\) 的。第二种转移注意到都是向长度为 \(b\) 的一段区间。考虑按长度 \(b\) 分块。然后每次转移的都是某个块的前缀/后缀，用前后缀优化建图。
时间复杂度 \(O(n)\)，有一些常数。
3
注意到第二种转移每个点至多会被转移到一次。所以用并查集维护尚未被转移的点。
时间复杂度 \(O(n)\)。
trick：进制数的图论表达。
t2
B. 神 (god)
原
给定长度为 \(n\) 的排列。\(q\) 次询问。每次询问给定四元组 \((l_1,r_1,l_2,r_2)\)，满足 \(l_1 \le r_1 \lt l_2 \le r_2\)，且 \(r_1-l_1=r_2-l_2\)。询问将 \([l_1,r_1]\) 和 \([l_2,r_2]\) 区间中的数两两配对，使得左区间的数严格小于其右区间的配对数，的配对方案数。
保证序列逆序对数小于等于 \(10^5\)。
\(1 \leq n,q \leq 10^5\)。
1
先考虑如何计算这个东西。
将两个区间的数分别排序。然后从大到小枚举左区间的数，其能配对的数【右区间比它大的数的个数】减去【左区间已配对好的数的个数】。
前者可以双指针。后者是好算的。
时间复杂度 \(O(qn\log n)\)。
2
显然我们要利用逆序对不超过 \(10^5\) 的条件。
记 \(k\) 等于序列逆序对数。
将上面的式子用符号刻画一下。记 \(f_i = \sum_{j \in [l_1,r_1]}[a_j \gt a_i],g_i = \sum_{j \in [l_2,r_2]}[a_j \gt a_i]\)。答案就是 \(\prod_{l_1 \leq i \leq r_1}(g_i-f_i)\)
我们希望将 \(g_i\) 写成和逆序对有关的形式。记 \(p_i = \sum_{j \in [l_2,r_2]}[a_j \lt a_i],len = r_1-l_1+1\)，则答案就是 \(\prod_{l_1 \leq i \leq r_1}(len-p_i-f_i)\)。
注意到本质不同的 \(p_i\) 只有 \(\sqrt k\) 种，否则逆序对数就超了。而对于 \(p_i\) 相同的一系列 \(i\)，其贡献是一段连续数乘积。
所以答案可以写成 \(O(\sqrt k)\) 个阶乘的形式。我们称 \(p_i\) 相同的数为一个连续段。显然它们在值域上是连续的。
实现上，我们可以用主席树提取两个区间的数。然后优先考虑右子树，再考虑左子树。过程中维护 \(now,pre\) 表示【当前连续段的长度】和【已被计算的连续段长度】。如果右子树确实还有要计算的连续段的话，才往右子树递归。
时间复杂度 \(O(n \sqrt k \log n)\)。
trick：根号势能。
t3
C. permutation
原
给定正整数 \(n\)。求右多少种长度为 \(n\) 的排列。使得本质不同的前缀 \(gcd\) 数目最大。
\(1 \leq n \leq 10^6\)。
1
显然至多有 \(\log n\) 种本质不同的前缀 \(gcd\)。
一种想法是对着这 \(\log n\) 个位置暴搜。比如现在搜出来 \(\log n\) 个位置的前缀 \(gcd\) 分别是 \((x_1,x_2,\cdots,x_m)\)。显然要满足 \(x_{i+1} \mid x_i\)。然后我们关心每一段之间放多少数。这个也可以在暴搜时确定一下。
考虑一个 \((x_i,x_{i+1})\) 段，中间放了 \(ct_i\) 个数。显然为了使这一段 \(gcd\) 不发生变化，只能放 \(x_i\) 的倍数，同时不能放之前放过的数。注意到 \(x_i \mid x_{i-1}\)，所以之前放过的数必然也是 \(x_i\) 的倍数，所以直接减去之前放过的数即可。
而为了使 \(x_{i+1}\) 形成一个新的连续段，则这个位置必须放 \(x_{i+1}\) 的倍数但不是 \(x_i\) 的倍数。
据此，我们可以开始 \(dp\) 了。
定义 \(f_{i,j}\) 表示 gcd 为 \(i\)，前缀长度为 \(j\) 的方案数。注意到 \(f_i\) 的长度至多为 \(\dfrac{n}{i}\)，所以总状态数是 \(O(n \log n)\) 的。但是算上转移时间复杂度是 \(O(n^2)\) 的。
2
考虑怎样能使本质不同的前缀 \(gcd\) 最多。我们希望每次前缀 \(gcd\) 变化时，其减少的尽可能少。从因子的角度考虑，我们希望 \(p_1\) 的质因子尽可能多，然后每次变化只减少一个质因子。
进一步分析，\(p_1\) 只可能含有 \(2/3\) 这两种质因子。否则一定不如将其换成两个 \(2\) 相乘来的优秀。
那定义 \(f_{i,x,y}\) 表示 \(gcd\) 为 \(2^x3^y\)，长度为 \(i\) 的方案数。
时间复杂度 \(O(n\log^2 n)\)。
trick：前缀 \(gcd\) \(\log V\)；上界一定，最大化因子数，可选因子只有 \(2,3\)。
t4
D. 清理通道 (clear)
给定 \(n\) 个待消灭二元组 \((x_i,y_i)\)，以及 \(A+B\) 个使用二元组 \((a_i,0)\) 或者 \((0,a_i)\)。从时刻 \(1\) 开始，每个时刻，所有使用二元组都可以消灭一个【存在一维偏序被其偏序】的被消灭二元组，求消灭所有被消灭二元组的最小时刻。
1
朴素的想法分别将两维二元组排序。从小到大考虑一维，尽可能消灭另一维的最大值。
但这样不一定最优。因为当前时刻消灭情况对后续时刻有影响，当前时刻最优不一定后续时刻最优。
考虑二分一个时刻 \(t\)，这么做就对了。
实现上，可以扫描一维，用 ds 维护另一维的最大值（这里优先队列就很合适，因为支持加入元素，和删除最大值）。
时间复杂度 \(O(n \log n)\)。
trick：二分+贪心。