CodeForces 1594F Ideal Farm

pufanyi

题解

发布于：Oct 9, 2021

Farmer John 有 $s$ 只奶牛，和 $n$ 个独立的篱笆，每个篱笆里可以圈养一些奶牛。出于一种奇♂️怪的偏好，Farmer John 把篱笆排成了一排。第 $i$ 个篱笆圈养的奶牛数量为 $a_i$，显然我们有 $\sum_{i=1}^n a_i=s$。而且，处于 Farmer John 的癖好，他要求对于每个 $i$ 都有 $a_i>0$。

Bessie 认为一个农场是“幸运的”当且仅当你可以找到一个区间 $[l,r]$，使得 $\sum_{i=l}^ra_i=k$。

而得寸进尺的 Bessie 认为一个农场是“牛逼的”当且仅当不管 Farmer John 怎么安置他的奶牛，该农场都是“幸运的”。

现在有 $t\,(1\le t\le 10^5)$ 组询问，每组询问给出 $s, n$ 和 $k\,(1\le s,n,k\le {10}^{18},\,n\le s)$，询问这个农场是不是“牛逼的”。

由于是区间问题，我们考虑先将其转换为两点问题。考虑 $b_i=\sum_{j=1}^i a_i$，于是我们有 $\begin{cases}b_0=0\\b_n=s\end{cases}$。如果存在一对 $\left<i,j\right>$ 满足 $b_j-b_i=k$，那显然这个农场是幸运的。由于 $a_i>0$，每一个 $b_i$ 都是两两不同的。于是问题就转化成了，在 $1\sim s$ 中选出 $n$ 个数，使得这些数中不存在 $k$，且不存在一对 $\left<i,j\right>$ 满足 $j-i=k$。

下面我们贪心地考虑最多能选出多少个满足条件的数。

考虑到不能有 $k$ 这个条件，我们把 $k$ 的倍数和不是 $k$ 的倍数的数分开讨论，对于不是 $k$ 倍数的数，如果我们选了 $x$，那我们就不能选 $x+k$ 了（如果 $x+k\le s$ 的话）。于是我们考虑对每 $2k$ 个划分为一段，这样除了最后一段不满的，就有 $\left\lfloor\frac{s}{2k}\right\rfloor$ 段，而每一段我们可以贪心地选择 $1\sim k-1$，这样保证了最后留下的 $s\ \mathrm{mod}\ 2k$ 个数能尽量多取，于是这对于不是 $k$ 倍数的数，这 $\left\lfloor\frac{s}{2k}\right\rfloor$ 段可以选择 $\left\lfloor\frac{s}{2k}\right\rfloor\cdot(k-1)$ 个数。然后我们考虑是 $k$ 倍数，由于不能选择 $k$，我们只能选择 $2k$ 的倍数。这样这 $\left\lfloor\frac{s}{2k}\right\rfloor$ 段我们就能选取 $\left\lfloor\frac{s}{2k}\right\rfloor$ 个数。于是前 $\left\lfloor\frac{s}{2k}\right\rfloor$ 段一共最多能选取 $\left\lfloor\frac{s}{2k}\right\rfloor\cdot k$ 个数。

然后我们考虑最后留下的 $s\ \mathrm{mod}\ 2k$ 个数，我们不难发现最多只能选这里面前 $k-1$ 个数了（第 $k$ 个数不能选了是因为我们已经选了原序列中第 $k\cdot \left\lfloor\frac{s}{2k}\right\rfloor$ 个数了）。因此，这一部分最多能选 $\min\left\{s\ \mathrm{mod}\ 2k, k - 1\right\}$ 个数。

然而上面那段忘记了一个条件，那就是第 $s$ 个数是必须要选的，因为 $b_n=s$。但是大部分情况下这没有关系，因为如果第 $s$ 个数没有选的话，那我们肯定选择了第 $s-k$ 个数（因为我们是贪心选最多的，如果第 $s-k$ 个数和第 $s$ 个数都不选的话，那就不是最优的了，因为可以选一个使所选数加一），于是我们把第 $s-k$ 个数删去，选择第 $s$ 个数即可。唯一的影响在于如果当 $s=k$ 的时候，那既然第 $s$ 个数一定要选，那么答案就只能是 YES 了。

所以，我们最终只要比较 $\left\lfloor\frac{s}{2k}\right\rfloor\cdot k+\min\left\{s\ \mathrm{mod}\ 2k, k - 1\right\}$ 与 $n$ 的大小即可得出答案。

更新于：Jul 2, 2023

CodeForces

构造