Codeforces Round 896 (Div. 1) A-C 题解

· · 题解

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

A

题意

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

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

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

#### 解法 行列从 $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 单次计算时间复杂度 $O(log n)$。 难点在于记忆化。 上述函数需要调用 $m$ 次，考虑提前预处理会到达的 $n$，以及和 $lim$ 无关的项，将 $n$ 映射到 dfn，这样每次记忆化的时候就可以只用开一个 $O(\log n)$ 级别的数组就可以了。