1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
//HDU 1730 Northcott Game //FAILED /* #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int main(){ int n = 0,m = 0; while (cin >> n >> m) { int cnt = 0; for (int i = 1; i <= n; i++) { int a = 0,b = 0; cin >> a >> b; if (abs(a-b)!=1) { cnt++; } } if (cnt%2) { cout << "I WIN!" << endl; }else{ cout << "BAD LUCK!" << endl; } } return 0; }*/ //AC /* #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int main(){ int n = 0,m = 0; while (cin >> n >> m) { int nim = 0; for (int i = 1; i <= n; i++) { int a = 0,b = 0; cin >> a >> b; nim ^= abs(a-b)-1; } if (!nim) { cout << "BAD LUCK!" << endl; }else{ cout << "I WIN!" << endl; ] } } return 0; } |
我把做错了的也发出来,一种典型的做错了的思路就是:先查Tom和Jerry的初始位置有空隙的行的个数,如果是奇数就是一种情况偶数另外一种情况,这个是不正确的。
正确的思路:我们可以把问题转化为没行空隙的大小就是每堆石子的个数,双方每轮任选一堆,取少则为1多则任意大枚石子,先取完获胜,这就是典型的Nim博弈。所以把每一行空隙大小(abs(a-b)-1)挨个xor,然后看看是不是0就行了。