CF做题记录

10.9

CF2144D Price Tags

题意

给定一个序列\(c\)，令\(a_i = \lceil \frac{c_i}{x} \rceil\)，\(x\)是任意大于\(1\)的正整数。

\(f(x) = \sum\limits^{n}_{i=1} a_i - ky\)，其中\(k\)是\(a\)与\(c\)相比新增数字的数量

求\(f(x)\)的最大值

思路

设\(c\)中最大值为\(A\)，首先容易发现\(x \in [1, A]\)
考虑当\(x\)固定时怎么做，
首先，计算出\(a\)，\(O(n)\)
接着，可以用双指针统计出\(k\)，\(O(n)\)
总复杂度\(O(nA)\)，爆炸

考虑优化，计算过程显然是没有什么优化空间了，但也许我们并不需要计算出\(a\)数组
我们只需要知道，对于每一个值\(v\)，\(c\)中是否存在除以\(x\)后是\(v\)的值即可

也就是说，是否存在\(c_i\), 使得\(v = \lceil \frac{c_i}{x} \rceil\)

那么，\(c_i \in [(v-1)x + 1,\ vx]\)

只需统计\(c\)数组在这段区域内的元素个数即可，用桶很好实现，时间复杂度\(O(\frac{A}{x})\)

对于统计过程，用桶也很好实现，按上述方法统计出\(v\)在\(a\)中的出现次数，减去\(v\)在\(c\)中的个数，与\(0\)取\(max\)就可以得到新增的元素了，时间复杂度\(O(\frac{A}{x})\)

总复杂度\(O(n + \sum\limits_{x=1}^{A} \frac{A}{x}) = O(n + A\text{log}A)\)（加上预处理桶的时间）

10.10

*CF2112D

题意

给定一棵\(n\)个节点无根树，试为每条边确定一个方向，得到一个有向图，使得图中满足存在一条从\(u\)到\(v\)的路径的点对\((u, v)\)的数量恰好等于\(n\)

思路

首先容易发现得到的有向图\(G = \{V, E\}\)是一个\(DAG\)，那么如果我们确定了每条边的方向，就可以用拓扑排序统计出每个点可以到达的点数。

设\(f_u\)为点\(u\)在图\(G\)能够到达的除自身以外的点数，则\(f_u = \sum\limits_{(u, v) \in E} (f_v + 1)\)

那么，就可以求出整个图中满足条件的点对数\(y\)

\[\begin{aligned} y &= \sum\limits_{u \in V} \sum\limits_{(u, v) \in E} (f_v + 1) \\ &= \sum\limits_{(u, v) \in E}(f_v + 1) \\&= \sum\limits_{(u, v) \in E}f_v + (n-1) \\&= \sum\limits_{v \in V} ind_v \times f_v + (n-1) \end{aligned} \]

其中，\(ind_v\)是节点\(v\)的入度

那么，根据条件，就有

\[n = y = \sum\limits_{v \in V} ind_v \times f_v + (n-1) \]

\[\therefore \sum\limits_{v \in V} ind_v \times f_v = 1 \]

观察式子，由于\(ind_v\)，\(f_v\)均为非负整数，所以求和式中至多有一项为\(1\)，其余均为\(0\)

因此，图中至多有一个节点的\(ind\)，\(f\)均为\(1\)（即在原树中度数为\(2\)），其余点要么入度为\(0\)，要么可以到达的点均为\(0\)（出度为\(0\)）

所以，只需找到树中的\(2\)度点，从该点开始搜索，确定每条边的方向即可