题解 1459: 蓝桥杯2013年第四届真题-高僧斗法 JAVA版

解题思路:本题为Nim博弈的演变，阶梯博弈的简化版。具体的Nim博弈不再赘述，就是一个通过求异或来判断是否达到了必胜/必败态，阶梯博弈的偶数阶梯与Nim博弈相同，而奇数阶梯博弈需要舍弃顶层阶梯，将顶层阶梯看作一个不能移动的阶梯(对于本题来说，本来就不能移动。。。。)，进而对于本题来说，不需要考虑奇偶阶梯。

注意事项:

代码中, d[i]存储了第i+1个数和第i个数的差，sum维持一个原定的异或和。

代码还使用了异或的自反性来降低时间复杂度，详见注释。

参考代码:

import java.io.*;
import java.util.ArrayList;
import java.util.*;

// https://www.dotcpp.com/oj/problem1459.html
// NIM博弈 -> 阶梯博弈
public class Main {
    static StreamTokenizer cin;
    static PrintWriter out;
    static ArrayList<Integer> list = new ArrayList<>();
    static int[] d;  // 差分数组
    public static void main(String[] args) throws IOException{
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        while(cin.nextToken() != StreamTokenizer.TT_EOF){
            list.add((int)cin.nval);
        }
        d = new int[list.size()-1];
        for(int i = 0; i < list.size()-1; i++)
            d[i] = list.get(i+1) - list.get(i) - 1;  // 差分
        int sum = 0;
        for(int i = 0; i < list.size()-1; i+=2)  // 两两一组, 若为奇数则将最高层看作不可移动的节点
            sum ^= d[i];
        if(sum == 0){
            out.println(-1);
            out.flush();
            System.exit(0);
        }
        for(int i = 0 ;i < list.size()-1; i++){  // 过滤顶层节点
            for(int j = 1; list.get(i+1) > list.get(i)+j; j++){  // 某棋子可向上移动的距离
                int res = sum;
                if(i % 2 == 0){  // 右节点
                    res ^= d[i];
                    res ^= (d[i]-j);
                }else{  // 左节点
                    res ^= d[i-1];
                    res ^= (d[i-1]+j);
                }
                if(res == 0){
                    out.println(list.get(i) + " "+ (list.get(i)+j));
                    out.flush();
                    System.exit(0);
                }
            }
        }

    }
}