题目重述

本题为交互型算法题，背景是调整老虎机的 $n$ 个转轮（$3 \leq n \leq 50$），使所有转轮显示相同符号以赢得大奖。核心规则如下：

• 每个转轮有 $n$ 个不同符号，且所有转轮的符号排列顺序完全相同；
• 每次操作可旋转任意转轮任意步数，操作后会收到反馈：当前显示序列中不同符号的数量 $k$；
• 目标是让 $k=1$（所有符号相同），最多允许 $10000$ 次操作；
• 评测机非自适应，初始配置固定，且初始状态 $k>1$。

核心观察

解题的关键突破口是所有转轮的符号排列顺序一致：

• 每个转轮的显示符号可表示为“基准符号（如1号转轮的符号） + 偏移量”（偏移量为旋转步数模 $n$，因为旋转 $n$ 步相当于无旋转）；
• 若所有转轮与基准转轮（选1号转轮为基准）的偏移量相同，则所有转轮显示的符号必然一致，即 $k=1$。

因此，问题可转化为：以1号转轮为基准，精准测量其余转轮与基准的偏移量，再校准偏移量至一致。

解题策略分步解析

1. 交互操作封装：query函数

目的

简化重复的交互流程，处理无效操作，及时终止程序（达成目标时）。

代码逻辑与设计原因

const auto query = [&](const int &pos, int dif) -> void {
    dif %= n;  // 旋转n步等价于无旋转，取模减少无效操作
    if (dif == 0) return;  // 跳过无意义的旋转
    cout << pos << ' ' << dif << endl;  // 输出操作
    cin >> k;  // 读取新的k值
    if (k == 1) exit(0);  // 达成目标，直接退出
};

• 取模 $n$：避免旋转步数为 $n$ 的倍数（无效操作），减少交互次数；
• 即时退出：若操作后 $k=1$，无需继续执行，符合题目要求。

2. 初步校准阶段

目的

对第 $2 \sim n$ 个转轮进行初步调整，找到其与基准转轮（1号）的偏移方向，为后续精准测量铺垫。

代码逻辑

for (int i = 2, mxk, mxpos; i <= n; ++i) {
    mxk = k, mxpos = 0;
    // 旋转i号转轮n-1次（覆盖所有非零偏移状态）
    for (int j = 1; j < n; ++j) {
        query(i, 1);  // 每次旋转1步
        if (k >= mxk) mxk = k, mxpos = j;  // 记录k的最大值及对应步数
    }
    query(i, mxpos + 1);  // 基于最大值调整i号转轮
}

设计原因

• 旋转 $n-1$ 次：覆盖转轮的所有非零偏移状态（因为 $n$ 步为一个周期）；
• 记录 $k$ 的最大值：$k$ 越大，说明当前转轮 $i$ 与基准转轮的符号差异越大，由此可定位偏移方向，为后续精准测量偏移量提供参考。

3. 精准偏移测量阶段

目的

精准测量第 $2 \sim n$ 个转轮与1号基准转轮的偏移量，存入数组 $a[i]$。

代码逻辑

int a[53];  // 存储各转轮与基准的偏移量
for (int i = 2, mxk, mxpos; i <= n; ++i) {
    query(i, 1);  // 微调i号转轮，进入测量状态
    mxk = k, mxpos = 0;
    // 旋转基准转轮n-1次，遍历所有偏移匹配状态
    for (int j = 1; j < n; ++j) {
        query(1, 1);
        if (k >= mxk) mxk = k, mxpos = j;  // 记录关键偏移步数
    }
    a[i] = mxpos;  // 保存i号转轮与基准的偏移量
    query(1, 1), query(i, -1);  // 回退操作，恢复初始测量状态
}

设计原因

• 旋转基准转轮：通过调整基准转轮的偏移，找到与转轮 $i$ 符号差异最大的位置（$k$ 最大），该位置对应的步数即为两者的精准偏移量；
• 回退操作：避免单次测量的调整影响后续转轮的测量，保证偏移量测量的准确性。

4. 最终对齐阶段

目的

根据测量的偏移量 $a[i]$，校准所有转轮与基准转轮的偏移量，使所有转轮显示相同符号。

代码逻辑

for (int i = 2; i <= n; ++i)
    query(i, -a[i]);  // 反向旋转偏移量，抵消差异

设计原因

反向旋转 $a[i]$ 步后，转轮 $i$ 与基准转轮的偏移量完全一致，因此所有转轮显示的符号相同，最终 $k=1$。

正确性分析

1. 核心性质支撑：所有转轮符号排列顺序一致，偏移量一致则符号一致，这是方案成立的根本前提；
2. 测量逻辑有效：通过旋转遍历所有偏移状态，$k$ 的最大值能准确反映转轮间的偏移关系，保证偏移量测量的精准性；
3. 操作次数合规：$n \leq 50$，总操作数为 $O(n^2)$（$50^2 = 2500 < 10000$），远低于题目限制。

复杂度分析

• 交互次数（时间复杂度）：$O(n^2)$，完全满足题目 $10000$ 次操作的限制；
• 空间复杂度：$O(n)$，仅需数组 $a$ 存储偏移量，空间开销可忽略。

总结

本题的解题核心是抓住“转轮符号排列一致”的关键性质，将复杂的交互问题转化为偏移量校准问题。代码通过“封装交互→初步校准→精准测量→最终对齐”的分阶段策略，既保证了逻辑的正确性，又控制了操作次数在限制范围内。

这种解题思路的本质是：利用题目特征简化问题核心，将大问题拆解为可分步解决的子问题，是处理交互型算法题的典型思路。对于类似的交互题，可优先分析题目隐含的结构性质，再设计分阶段的策略逐步达成目标。