概述

本题要求对每组数据求出在 ~n \times n~ 的零矩阵上双方均采取最优策略时，游戏过程中值为 ~1~ 的元素个数的最大值。核心解法是二分出最大的轮数 ~k~，使先手在第 ~k~ 轮落子后能布下 ~k + 1~ 颗满足「任意 ~k \times k~ 子矩阵内至多一颗」的棋子，答案即 ~k + 2~；~n = 1~ 时需要单独处理。

分析

核心观察

只要棋盘上还有棋子，小乔每一轮都至少能抹掉一颗，因此小蓝每个回合最多让棋子数增加 ~1~；只有把小蓝的棋子布成「任意 ~i \times i~ 子矩阵内至多一颗」时，小乔第 ~i~ 轮才恰好只能抹掉一颗，棋子数才可能逐轮积累。这样的布局在 ~n \times n~ 棋盘上最多能放 ~\lceil n / i \rceil^2~ 颗棋子。

思路

记 ~c_i~ 为小蓝第 ~i~ 个回合落子后棋盘上 ~1~ 的个数，显然 ~c_1 = 2~。小乔第 ~i~ 个回合只能选一个 ~i \times i~ 子矩阵，她自然选其中棋子最多的那个；由于 ~i \le n~ 时每颗棋子都落在某个 ~i \times i~ 子矩阵内，故只要 ~c_i > 0~ 她就至少能抹掉一颗，于是

$$\displaystyle c_{i+1} \le c_i + 2 - 1 = c_i + 1 $$

若棋盘的布局满足「任意 ~i \times i~ 子矩阵内的棋子都不超过一颗」（下称 ~i~-稀疏），小乔第 ~i~ 轮就恰好只能抹掉一颗，此时上式取等号。

~i~-稀疏布局的规模上限为 ~\lceil n / i \rceil^2~。上界：把 ~n~ 行按连续的 ~i~ 行一组划分，共 ~\lceil n / i \rceil~ 组，列同理；同一「行组与列组」的乘积中的任意两个格子，都能被某段连续的 ~i~ 行与某段连续的 ~i~ 列同时包含，即落在同一个 ~i \times i~ 子矩阵内，因此每个组对至多贡献一颗棋子，总数不超过 ~\lceil n / i \rceil^2~。下界：在行 ~1, 1 + i, 1 + 2i, \dots~ 与列 ~1, 1 + i, 1 + 2i, \dots~ 的所有交点处各放一颗，任意 ~i \times i~ 子矩阵的 ~i~ 行中至多含一个这样的行下标，列同理，故每个 ~i \times i~ 子矩阵内恰好至多一颗，共可放 ~\lceil n / i \rceil^2~ 颗。

取满足

$$\displaystyle \lceil n / k \rceil^2 \ge k + 1 $$

的最大整数 ~k~。对 ~i = 1, 2, \dots, k~，先手都可以让小蓝第 ~i~ 个回合落子后的布局既 ~i~-稀疏又有 ~i + 1~ 颗棋子（~i + 1 \le \lceil n / i \rceil^2~）；小蓝每一轮多出的那次落子可以落在已有棋子的格子上，等价于不落子，所以这种逐轮累计的方案总可以执行。棋盘自始至终是确定的，小蓝可以在开局前就定好每一轮的目标布局，故小乔无法打乱这个方案：第 ~k~ 轮落子后有 ~k + 1~ 颗，小乔抹掉一颗剩 ~k~ 颗，小蓝第 ~k + 1~ 轮再落两颗，棋盘上就有 ~k + 2~ 颗，故 ~X \ge k + 2~。

再证 ~X \le k + 2~。若 ~i \le k~，由 ~c_{i+1} \le c_i + 1~ 与 ~c_1 = 2~ 得 ~c_i \le i + 1 \le k + 1~。对 ~i \ge k + 1~ 归纳：~c_{k+1} \le c_k + 1 \le k + 2~；设 ~c_i \le k + 2~，若 ~c_i \le k + 1~ 则 ~c_{i+1} \le c_i + 1 \le k + 2~；若 ~c_i = k + 2~，则由 ~k~ 的最大性 ~\lceil n / i \rceil^2 \le \lceil n / (k + 1) \rceil^2 \le k + 1 < c_i~，说明布局不是 ~i~-稀疏的，某个 ~i \times i~ 子矩阵内至少有 ~2~ 颗棋子，小乔抹掉至少两颗后 ~c_{i+1} \le c_i - 2 + 2 = k + 2~。于是整个过程中棋子数始终不超过 ~k + 2~，结合下界得 ~X = k + 2~。

判定式右端是 ~k + 1~ 而不是 ~k~：小蓝第 ~i~ 轮落子后棋盘上的棋子数是 ~i + 1~ 而不是 ~i~。判定 ~\lceil n / k \rceil^2 \ge k + 1~ 关于 ~k~ 单调（左端单调不增、右端单调递增），故可以对 ~k~ 二分。当 ~n = 1~ 时不存在满足判定的 ~k~，公式失效：此时棋盘只有一格，小蓝连两个不同的元素都选不出来，故 ~X = 1~。

具体示例

样例第一组 ~n = 2~：~x = 1~ 时 ~\lceil 2 / 1 \rceil^2 = 4 \ge 2~ 成立；~x = 2~ 时 ~\lceil 2 / 2 \rceil^2 = 1 \ge 3~ 不成立。故 ~k = 1~，答案 ~k + 2 = 3~，与样例一致。

样例第二组 ~n = 5~：依次检验 ~x = 1, 2, 3, 4~，左端为 ~25, 9, 4, 4~，右端为 ~2, 3, 4, 5~，前三个满足、第四个不满足，故 ~k = 3~，答案 ~k + 2 = 5~，与样例一致。也就是说，小蓝在前三轮把棋子布成 ~3~-稀疏的 ~4~ 颗，第四轮落子后有 ~5~ 颗，但在第 ~4~ 轮里 ~5 > \lceil 5 / 4 \rceil^2 = 4~，小乔必然能一次抹掉两颗，棋子数回落。

算法步骤

1. 读入 T。
2. 对每组数据读入 n。
3. 若 n 等于 ~1~，输出 ~1~，处理下一组。
4. 否则令 lo = 1、hi = n，循环执行：取上中位数 mid = (lo + hi + 1) / 2，令 c = (n + mid - 1) / mid；若 c * c >= mid + 1 则令 lo = mid，否则令 hi = mid - 1。
5. 循环结束时 lo 即为满足判定的最大整数，输出 lo + 2。
6. 把所有答案一次写出。

复杂度分析

• 时间：每组数据对 ~[1, n]~ 二分 ~O(\log n)~ 次，每次判定为常数次整数运算，总计 ~O(T \log n)~。
• 空间：除输出缓冲外为 ~O(1)~。

实现注意事项

• 判定式中的平方可达 ~10^{18}~（~n = 10^9~ 时 ~c~ 可取到 ~10^9~），C++ 必须用 long long 存储 n 与 c，用 int 会溢出。
• n = 1 必须特判为 ~1~：此时既不存在满足判定的 ~k~（输出的 ~k + 2~ 会偏大），先手也无法选出两个不同的元素。
• 二分必须取上中位数 (lo + hi + 1) / 2：若取下中位数，当 lo 与 hi 相邻且 lo 可行时区间不再收缩，会死循环。
• 二分的上界取 n 已经足够：由 ~\lceil n / x \rceil \ge n / x~ 与 ~\lceil n / x \rceil^2 \ge x + 1~ 可得 ~n \ge x \sqrt{x + 1} > x~，故可行解必然不超过 ~n~；又因 ~n \ge 2~ 时 ~x = 1~ 一定可行，二分区间总含有解。
• 判定只需一次整数除法和一次乘法，ceil(n / mid) 用 (n + mid - 1) / mid 计算，避免浮点误差。
• ~T~ 可达 ~10^5~，需整体读入并一次性输出（C++ 用 fwrite，Python 用 sys.stdin.buffer.read() 与 b"\n".join(...)），避免逐行输出带来的开销。
• 多组数据之间没有依赖，逐组独立二分即可，不需要预处理或缓存。

源代码

#include <cstdio>
#include <iostream>
#include <string>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 0;
    if (!(std::cin >> T)) return 0;

    std::string out;
    out.reserve(static_cast<std::size_t>(T) * 9);

    while (T--) {
        long long n = 0;
        std::cin >> n;

        if (n == 1) {  // 只有一格，先手最多只能放 1 颗棋子
            out += "1\n";
            continue;
        }

        long long lo = 1, hi = n;
        while (lo < hi) {
            long long mid = lo + (hi - lo + 1) / 2;  // 上中位数
            long long c = (n + mid - 1) / mid;       // ceil(n / mid)
            if (c * c >= mid + 1) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }

        out += std::to_string(lo + 2);
        out += '\n';
    }

    std::fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for i in range(1, t + 1):
        n = int(data[i])
        if n == 1:  # 只有一格，先手最多只能放 1 颗棋子
            out.append(b"1")
            continue
        lo, hi = 1, n
        while lo < hi:
            mid = (lo + hi + 1) >> 1  # 上中位数
            c = -(-n // mid)  # ceil(n / mid)
            if c * c >= mid + 1:
                lo = mid
            else:
                hi = mid - 1
        out.append(b"%d" % (lo + 2))
    sys.stdout.buffer.write(b"\n".join(out) + b"\n")


main()