星港回执 题解

题意与关键信息

• 给定函数

$$f(x)= \begin{cases} f(f(x+11)), & x \le 100,\\ x-10, & x \ge 101. \end{cases}$$

• 输入若干行 $x$（$1 \le x \le 10^6$，以 $0$ 结束），询问数不超过 $2.5 \times 10^6$，对每个 $x$ 输出 $f(x)$。

从暴力到正解

朴素递归（$x \le 10$，40 分）

按定义直接写递归：

int f(int x) {
    if (x >= 101) return x - 10;
    return f(f(x + 11));
}

当 $x \le 10$ 时，内层 $f(x+11)$ 的参数不超过 $21$，递归深度很浅，直接模拟即可。但当 $x$ 接近 $100$ 时，例如 $f(100)=f(f(111))$，内层参数会先跳到 $101$ 以上再回落，递归过程并不直观——这一档考察的是"照抄定义"的准确性与对递归结构的耐心展开。

关键观察（无限制，正解）

先看几个关键值：

$$f(111)=101,\qquad f(110)=100,\dots,f(101)=91.$$

对 $x \in [91,100]$：

$$f(x)=f(f(x+11)),$$

而 $x+11 \in [102,111]$ 已落在 $x \ge 101$ 分支，故 $f(x+11)=x+1 \in [92,101]$。

• 若 $x+1 = 101$（即 $x=100$），则 $f(100)=f(101)=91$。
• 若 $x+1 \in [92,100]$，还需要 $f(x+1)$，而 $x+1$ 仍属于 $[91,100]$。

由 $f(100)=91$ 向上归纳：$f(99)=f(100)=91$，$f(98)=f(99)=91$，……得到

$$f(x)=91,\quad 91 \le x \le 100.$$

再向下归纳：若 $x \le 90$，则 $x+11 \in [12,101]$。只要 $x+11 \le 100$ 就继续套用上面的结论，最终得到

$$\boxed{f(x)=91,\quad 1 \le x \le 100.}$$

（这正是经典的 McCarthy 91 函数。）

正解

对每个询问 $O(1)$ 回答：

cout << (x >= 101 ? x - 10 : 91) << '\n';

复杂度

• 每个询问 $O(1)$，总时间复杂度 $O(Q)$，空间 $O(1)$，其中 $Q$ 为询问总数（$\le 2.5\times10^6$）。

易错点

1. 结束标记：读入遇到 $0$ 立即停止，$0$ 本身不产生输出。
2. $x \le 100$ 不是 $x-10$：只有 $x \ge 101$ 才直接减 $10$；$x=100$ 的答案是 $91$ 而非 $90$。
3. 递归写法可能栈溢出：若把递归写成"先算内层再套外层"，对任意 $x$ 深度都很浅；但若实现有误（例如忘记 $f(f(x+11))$ 的两层调用）会得到错误结果。
4. 大数据量输入输出：询问数可达 $2.5\times10^6$，务必使用快速 IO（ios::sync_with_stdio(false) 或 getchar 手写读入）。

参考代码

见 summercspj262A.cpp。