題目?

傳送門?P8606 [藍橋杯 2013 國 B] 高僧斗法 - 洛谷

思路

這個題就比較考驗博弈的基本題型和轉換能力了；

這個題是nim博弈=>階梯博弈

再將小和尚的移動轉化為階梯上石子的移動：兩個小和尚之間可以移動的距離，看做階梯上的石子，小和尚右移==相鄰階梯上石子的轉移

將所有距離轉化為階梯，看奇數位置的nim和是否為0，為0--無解，不為零--找一個合法的解：讓找最小的A且數據較小，即從小到大枚舉小和尚向右移動的位置

代碼

LL n;
vector<LL> a;vector<LL> b;bool check()//計算階梯博弈的 nim和
{	LL res = 0;for (int i = 0;i < n - 1;i += 2){res ^= b[i];}return res;
}void solve()
{LL x;while(cin >> x)//小和尚的距離{a.push_back(x);}n = a.size();for (int i = 0;i < n - 1;i ++)//轉化為階梯上的石子{b.push_back(a[i + 1] - a[i] - 1);}if (!check()) {cout << -1 << endl;}else{for (int i = 0;i < n - 1;i ++)//從小到大枚舉小和尚for (int j = 1;j <= a[i + 1] - a[i] - 1;j ++)//右移的距離{//模擬小和尚右移后對之間距離(臺階石子)的影響b[i] -= j;if (i) b[i - 1] += j;//如果是第一個,左邊沒有臺階，不用加if (!check())//先手操作完后，檢查是否滿足必勝要求{cout << a[i] << " " << a[i] + j << endl;return;}//還原b[i] += j;if (i) b[i - 1] -= j;}}
}