题解：P12131 [蓝桥杯 2025 省 B] 客流量上限

· · 题解

析

康到题目描述中的“i 可等于 j”，就直接手欠令 i = j。

则有：a_i ^ 2 \le i ^ 2 + 2025

分解因数，得：a_i ^ 2 \le i ^ 2 + 1 \times 2025

添项，得：a_i ^ 2 \le i ^ 2 + (1 + 1012 - 1012) \times (2025 + 1012 - 1012)

合并部分同类项，得：a_i ^ 2 \le i ^ 2 + (1013 - 1012) \times (1013 + 1012)

利用平方差公式，得：a_i ^ 2 \le i ^ 2 + 1013 ^ 2 - 1012 ^ 2

移项，得：a_i ^ 2 + 1012 ^ 2 \le i ^ 2 + 1013 ^ 2

:::success[引理] 试证明：对于任意 x，y，若其满足 1 \le x < y，则必有 (x - 1) ^ 2 + (y + 1) ^ 2 > x ^ 2 + y ^ 2。

证明：

\because 1 \le x < y \therefore y - x > 0 \therefore y - x + 1 > 0 \therefore 2 (y - x + 1) > 0 \therefore - 2 x + 2 y + 2 > 0 \therefore x ^ 2 - 2 x + y ^ 2 + 2 y + 2 > x ^ 2 + y ^ 2 \therefore x ^ 2 - 2 x + 1 + y ^ 2 + 2 y + 1 > x ^ 2 + y ^ 2 \therefore (x - 1) ^ 2 + (y + 1) ^ 2 > x ^ 2 + y ^ 2

:::

我们分步选择 a_1 至 a_{1012}，注意到每一个 a_i 都有 i + 1 种选择，分别为 1，2，直到 i + 1。但是在此之前我们会占用 i - 1 个数，所以实际可选为 2 个。这一部分的答案为 2 ^ {1012}。

归纳，后面的项也只有唯一选择，故方案数为 $2 ^ {1012}$。