本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-12 20:15:08

感觉都是有些套路的思维题。

A

题意

给定一个 $n\times m$ 的矩阵 $M$。

矩阵的每一行都应该是一个长度为 $m$ 的由 $[0,m-1]$ 的整数构成的排列。

一列的价值是这一列所有数的 MEX，整个矩阵的价值是所有列的价值的 MEX，要求你为矩阵 M 的每个位置赋值，使得在矩阵合法的前提下，矩阵的价值最大。
$nm \le 2\cdot 10^5$。

解法

行列从 $0$ 编号方便一些。

考虑依次构造出 MEX 为 $0,1,2,\cdots,m-1$ 的列。

第一行先按照 MEX 顺序来： $m-1,0,1,2,3,\cdots,m-2$。
随后每一行，就将 $0$ 开头的升序序列向右移一位，左边空余的，则将剩下的数字降序填就行。

如果某一行出现了 $j$ 列的值刚好等于 $j$，那么也不要紧，和 $j-1$ 的值交换一下就没事了，反正同一行最多一个这样的位置。

B1

本题的简单版本，但其实和困难版没差多少。

题意

有 $n$ 个人，每个人初始有 $a_i$ 个糖果。
每个人必须给另一个人赠送 $2^x$ 个糖果，必须从另一个人收到 $2^y$ 个糖果，其中 $x,y$ 是非负整数。

其中，每个人可以自由选择把糖果赠送给谁，每个人收到和赠送的糖果数也可以任意选择，只需要满足上述性质

同时，赠送操作的顺序也是任意的。

问是否存在一种方案，使得最后所有人的糖果数量相同。

$n \le 2\cdot 10^5$，值域 $10^9$。

解法

最后每个人的糖果数量 $avg$ 可以直接算出来。

然后，每个人的 $x,y$ 也可以算出来（如果某个人的初始值等于 $avg$，可以忽略这个人）。

有解当且仅当对于任意 $2^x$，需要得到 $2^x$ 的人数与需要得到 $2^y$ 的人数相同，并且对于 $1 \le \forall i \le n, popcount(|a_i-avg|) \le 2$。

B2

困难版，赛时通过本题可以到达 Master。

题意

与 B1 的区别：在本题，每个人可以向不超过一个人赠送糖果，接受不超过一个人的糖果。

解法

事实上，只有在 $popcount(|a_i-avg|)=1$ 的时候才有区别，此时，在 B1 限制条件下，$a_i-avg$ 的值强制拆为 $2^p-2^q(p\neq q) $ 的形式，但在 B2，它不仅可以保持原来 B1 的形式（赠送 $2^q$，收获 $2^p$ 个），也可以仅仅是 $2^k$ 形式，即仅赠送或仅接受 $2^k$ 个糖果。

此时，考虑还是按照 B1 限制下的形式，如果方案不合法再转化为 B2 限制下的新形式。

从高位开始考虑，如果当前位接受与赠送数量不同，那么就转化形式。

C

感觉比 A 简单，但是 CF 评分 2400，并且场切这题最高可以到达黑红名。

题意

给定一个大小为 $n$ 的完全二叉树，点权范围是 $[1,m]$。

求所有 $m^n$ 个可能的情况，两两点对之间路径权值最大值的和的和。
$n \le 10^{18},m\le 10^5$。

解法

考虑 $1 \le \forall i \le m$，求出路径点权最大值为 $i$ 的方案数。

没法直接计算，可以用差分的方式，计算出路径点权最大值小于等于 $i$ 的方案数。

考虑固定点权最大值限制 $lim$，求解一下函数：

令 $f(n)$ 代表树的大小为 $n$ 的情况下，所有 $m^n$ 种可能下路径点对最大值小于等于 $lim$ 的点对数量总和。

可以拆为左子树，右子树的答案加和，然后计算左右子树之间的答案，以及根作为端点的答案。

令 $g(n)$ 代表树的大小为 $n$ 的情况下，所有 $m^n$ 种可能下，根作为路径端点且点权最大值小于等于 $lim$ 的路径数量总和。

$g(n)=(g(siz(ls))m^{siz(rs)}+g(siz(rs))m^{siz(ls)}+m^{n-1})lim$

$f(n)=f(siz(ls))m^{siz(rs)+1}+f(siz(rs))m^{siz(ls)+1}+g(siz(ls))g(siz(rs))lim+g(n)$。

单次计算时间复杂度 $O(log n)$。

难点在于记忆化。

上述函数需要调用 $m$ 次，考虑提前预处理会到达的 $n$，以及和 $lim$ 无关的项，将 $n$ 映射到 dfn，这样每次记忆化的时候就可以只用开一个 $O(\log n)$ 级别的数组就可以了。