[蓝桥杯]高僧斗法

高僧斗法

题目描述

古时丧葬活动中经常请高僧做法事。仪式结束后，有时会有"高僧斗法"的趣味节目，以舒缓压抑的气氛。

节目大略步骤为：先用粮食（一般是稻米）在地上"画"出若干级台阶（表示 NN 级浮屠）。又有若干小和尚随机地"站"在某个台阶上。最高一级台阶必须站人，其它任意。(如下图所示)

两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶，但会被站在高级台阶上的小和尚阻挡，不能越过。两个小和尚也不能站在同一台阶，也不能向低级台阶移动。

两法师轮流发出指令，最后所有小和尚必然会都挤在高段台阶，再也不能向上移动。轮到哪个法师指挥时无法继续移动，则游戏结束，该法师认输。

对于已知的台阶数和小和尚的分布位置，请你计算先发指令的法师该如何决策才能保证胜出。

输入描述

输入数据为一行用空格分开的 NN 个整数，表示小和尚的位置。台阶序号从 1 算起，所以最后一个小和尚的位置即是台阶的总数。（N<100,台阶总数<1000）（N<100,台阶总数<1000）

输出描述

输出为一行用空格分开的两个整数: A,BA,B，表示把 AA 位置的小和尚移动到 BB 位置。若有多个解，输出 AA 值较小的解，若无解则输出 -1。

输入输出样例

示例

输入

1 5 9

输出

1 4

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 277  |  总提交次数: 407  |  通过率: 68.1%

难度: 中等   标签: 2013, 国赛, 博弈

核心思路：Nim博弈模型转换

1. ​​问题转换​​：

   • 将小和尚按位置升序排序（如输入 1 5 9 排序后为 [1, 5, 9]）。
   • ​​两两分组​​：从低到高每两个小和尚为一组（位置索引0和1一组、2和3一组...），若小和尚数量为奇数，则忽略最后一个（最高台阶的和尚不可移动）
   • ​​计算间隔​​：每组两个和尚之间的台阶数为 b[i] = a[2i+1] - a[2i] - 1（例如 1 和 5 的间隔为 5-1-1=3）。

2. ​​Nim博弈规则​​：

   • 所有组的间隔值构成一个Nim堆，计算异或值 XOR = b[0] ^ b[1] ^ ... ^ b[m-1]。
   • ​​先手必胜条件​​：XOR ≠ 0；若 XOR = 0 则先手必败，输出 -1

3. ​​寻找必胜策略​​：

   • 遍历每组，计算目标间隔 target = XOR ^ b[i]。
   • 若 target < b[i]，可通过移动该组第一个和尚减少间隔：
     • 移动步数 step = b[i] - target。
     • 新位置 B = a[2i] + step。
   • ​​输出要求​​：取 A（移动前位置）最小的解，因此按分组顺序遍历，找到首个可行解即输出

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<int> positions;
    int pos;
    
    // 读取并排序小和尚位置
    while (ss >> pos) {
        positions.push_back(pos);
    }
    sort(positions.begin(), positions.end());
    int n = positions.size();

    // 计算分组间隔（两两分组）
    vector<int> gaps;
    for (int i = 0; i < n - 1; i += 2) {
        gaps.push_back(positions[i + 1] - positions[i] - 1);
    }

    // 计算初始 Nim 异或值
    int nimXOR = 0;
    for (int gap : gaps) {
        nimXOR ^= gap;
    }

    // 先手必败情况
    if (nimXOR == 0) {
        cout << -1 << endl;
        return 0;
    }

    // 寻找必胜策略（优先移动位置最小的和尚）
    for (int i = 0; i < n - 1; i++) {
        int maxStep = positions[i + 1] - positions[i] - 1;
        
        for (int step = 1; step <= maxStep; step++) {
            if (i % 2 == 0) {  // 移动分组的前一个和尚
                int groupIdx = i / 2;
                int newGap = gaps[groupIdx] - step;
                if (newGap < 0) continue;
                if ((nimXOR ^ gaps[groupIdx] ^ newGap) == 0) {
                    cout << positions[i] << " " << positions[i] + step << endl;
                    return 0;
                }
            } else {  // 移动分组的后一个和尚
                int groupIdx = (i - 1) / 2;
                int newGap = gaps[groupIdx] + step;
                if ((nimXOR ^ gaps[groupIdx] ^ newGap) == 0) {
                    cout << positions[i] << " " << positions[i] + step << endl;
                    return 0;
                }
            }
        }
    }

    // 理论不应执行到此（Nim 模型保证有解）
    cout << -1 << endl;
    return 0;
}

核心算法解析

1. ​​问题转换​​

   • 将小和尚位置升序排序（如输入 1 5 9 → 排序 [1,5,9]）
   • ​​两两分组​​：(1,5) 为一组（忽略最后单个和尚）
   • ​​计算间隔​​：每组台阶差减 1（5-1-1=3）

2. ​​Nim 博弈模型​​

   • 计算所有间隔的异或值：XOR = 3 ^ (下一组间隔)...
   • ​​必胜条件​​：XOR ≠ 0（先手可赢）；XOR=0 则输出 -1

3. ​​寻找最优移动​​

   • ​​缩短间隔​​：移动每组前一个和尚（如 1→4 使间隔 3→0）
   • ​​增加间隔​​：移动后一个和尚（如 5→6 影响前组间隔）
   • ​​优先级​​：优先尝试 A 值更小的移动（外层循环从低到高遍历分组）

关键优化与边界处理

1. ​​位置重复校验​​
   输入时隐式处理了位置重复（sort 后相邻位置差为 0 时，maxStep 为负，循环跳过）。

2. ​​移动策略全覆盖​​：

   • ​​前和尚移动​​：减少当前组间隔（gaps[groupIdx] - step）
   • ​​后和尚移动​​：增加前组间隔（gaps[groupIdx] + step）
   • 按位置升序遍历，确保输出 A 值最小的解

3. ​​极端输入处理​​：

   • ​​单和尚情况​​：n=1 时分组间隔为空，nimXOR=0 直接输出 -1
   • ​​最大台阶​​：positions[i+1]-positions[i]-1 自动处理边界
   • ​​密集位置​​：如 [1,2,3,4] 所有 maxStep=0，跳过移动

4. ​​性能保障​​：

   • 时间复杂度：O(n⋅maxStep)，最坏 100×1000=105 次操作
   • 空间复杂度：O(n)，仅存储位置和间隔

测试用例验证