思路:
Staircase Nim博弈。两两分组之后转化为Nim博弈。挪动一组中左边的和尚相当于减少石子。挪动一组中右边的和尚相当于增加石子,这样做是没有用的,因为之后对手可以再移动左边的和尚使局面恢复原来的状况。
虽然在必败态增加石子没有用,但是在必胜态增加石子却有可能导致胜利。
实现:
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 105; 4 int a[MAXN], b[MAXN], cnt; 5 bool check() 6 { 7 int ans = 0; 8 for (int i = 0; i < cnt - 1; i += 2) ans ^= b[i]; 9 return ans == 0; 10 } 11 int main() 12 { 13 string s; 14 getline(cin, s); 15 stringstream ss(s); 16 while (ss >> a[cnt]) cnt++; 17 for (int i = 0; i < cnt - 1; i++) b[i] = a[i + 1] - a[i] - 1; 18 if (check()) { cout << -1 << endl; return 0; } 19 for (int i = 0; i < cnt - 1; i++) 20 { 21 for (int j = 1; j < a[i + 1] - a[i]; j++) 22 { 23 if (i & 1) b[i - 1] += j; 24 else b[i] -= j; 25 if (check()) { cout << a[i] << " " << a[i] + j << endl; return 0; } 26 if (i & 1) b[i - 1] -= j; 27 else b[i] += j; 28 } 29 } 30 return 0; 31 }