自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:15:01，当前版本为作者最后更新于2023-06-11 21:46:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

问题 1

(a + b - 1) / b 在 $b > 0$ 时是一个非常合理且正确的对 $\dfrac a b$ 上取整求值的方法：

$$\left\lfloor\dfrac{a + b - 1}{b}\right\rfloor = \left\lfloor\dfrac{a}{b}\right\rfloor + \left\lfloor\dfrac{a \bmod b + b - 1}{b}\right\rfloor = \begin{cases}\frac{a}{b}, &a \bmod b = 0 \\ \left\lfloor\frac{a}{b}\right\rfloor + 1, & a \bmod b \neq 0\end{cases} $$

这两种情况都恰好等于 $\left\lceil\dfrac{a}{b}\right\rceil$。

但是，这一方法在分母小于 $0$ 时并不适用。hack 的思路之一是，当 $b \mid a$ 时，给 $a$ 加上 $b - 1$ 会让分子减小，而原先的商是整除的结果，在分子减小后，商（的绝对值）会减小，于是就得不到正确的结果了。

因此，任给出一组 $b < c$ 且 $(b - c) \mid a$ 的数据即可。

思考题：上述方法在分子为负、分母为正时能否使用？

问题 2

题意简述：

std::cerr 每调用一次就会刷新一次缓冲区，而刷新缓冲区次数太多就会导致超时。

关注到目标代码中有一句

if (s.find("std::cerr") != std::string::npos) {
  std::cerr << cur << '\n';
  ++ans;
}

其中 s.find(t) 返回的是 $t$ 作为 $s$ 的子串第一次出现位置的首下标。当 $t$ 不是 $s$ 的子串时返回 std::string::npos。因此，当输入的 $s$ 含有 std::cerr 作为子串时，就会执行大括号内的内容，否则不会执行。if 每执行一次，就会调用一次 std::cerr。要让程序超时，只需要让程序尽可能多地调用 std::cerr。

于是，只需要令所有输入字符串均为 $\texttt{std::cerr}$ 即可。这是一个长度为 $9$ 的字符串，输入总长度不能超过 $2 \times 10^6$，所以你最多可以输出 $222,222$ 个这样的串。

Code

#include <iostream>

int main() {
  using std::cin, std::cout;
  int x;
  std::cin >> x;
  if (x == 1) std::cout << "9 5 8\n";
  else {
    cout << 222222 << '\n';
    for (int i = 1; i <= 222222; ++i)
    cout << "std::cerr\n";
  }
}