B3785 题解

· · 题解

问题 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";
  }
}