数论 01_博弈论

Nim游戏

https://www.acwing.com/problem/content/893/

分析：

谁进行最后一次，谁就赢。那么先手面对异或和为0就是必败局面（因为后手已经进行到了必胜局面，将最后的石子给那完了）

所以，异或和为0，先手必输，否则，先手必胜。

代码：

#include <iostream>

using namespace std;

int ans, n, x;
int main()
{
    cin >> n;
    while (n -- )
    {
        cin >> x;
        ans ^= x;
    }
    if (ans) cout << "Yes" << "
";
    else cout << "No" << "
";
    return 0;
}

 台阶-Nim游戏

链接：https://www.acwing.com/problem/content/894/

分析：

我们可以在任意台阶上，拿任意颗石子放到它的下一个台阶，但拿到地面上的石子就不能再拿了。谁无法操作谁输（谁最后一个拿，谁赢）。

结论为：若奇数台阶上的石子异或和为0，则先手必败，否则，先手必胜。

证明：如果异或和不为0， 先手第一次拿石子后，将局面变为异或和为0，再那之后，先手总是将必败局面留给了后手（异或和为0，为必败局面，因为当你面对异或和为0，到了结局，队手将石子全放到了地面上）。

　　如果先手已经给后手造成了必败局面，那么后手如果拿偶数上的石子放到奇数层，我们将这些石子再拿到下一个偶数层。如果后手拿了奇数上的石子，有Nim游戏（上一题），使奇数层异或和为x，我们可以找到一个a[i]从中拿出（a[i] - x）个石子。

使局面再次变为必败局面留给后手。

思考：

为什么不能采用偶数层异或和呢？

现在，假设我们处于必胜局面，我们通过拿出若干个石子，试的局面变成了必败局面，也就是偶数层异或和为0，这时，后手将第一层（这是奇数层）的石子，全部拿到地面上，！！！注意，这时，局面还是必败局面，先手却面临了必败局面，因为后手将第一层放到地面上，对我们的偶数层异或和没有影响，还是异或和为0，但先手却面临着必败局面，而且还不能改变局面，因为第一层已经没有了石子了，这个时候，先手只能破坏异或和为0的局面，

代码：

#include <iostream>

using namespace std;

// const int N = 

int main()
{
    int ans = 0;
    int n; cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int x; scanf("%d", &x);
        if (i & 1) ans ^= x;
    }
    if (ans) cout << "Yes" << "
";
    else cout << "No" << "
";
    
    return 0;
}

 集合-Nim游戏

链接：https://www.acwing.com/problem/content/895/

 分析：

用到了SG函数

如果SG(x)等与0，一定是一个必败局面，

 SG(x)为0，先手必败，SG(x)不为0，先手必胜

可以以这个图为例 。

如果n副图的异或和为0的话，则是一个先手必败局面，否则就是一个先手必胜局面，这已经不需要再分析了。

终止状态定义为0，其他所有sg的值定义成当前状态不能到达的状态的最小自然数是多少。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 10010;

int n, k;
int a[N], f[M];

int sg(int x)
{
    if (f[x] != -1) return f[x];
    
    unordered_set<int> st;
    for (int i = 1; i <= k; i ++ )
    {
        int sum = a[i];
        if (x >= sum) st.insert(sg(x - sum));
    }
    
    for (int i = 0; ; i ++ )
        if (!st.count(i)) return f[x] = i;
}
int main()
{
    cin >> k;
    for (int i = 1; i <= k; i ++ )
    {
        cin >> a[i];
    }
    
    int ans = 0;
    cin >> n;
    memset(f, -1, sizeof f);
    for (int i = 0; i < n; i ++ )
    {
        int x; cin >> x;
        ans ^= sg(x);
    }
    
    if (ans) cout << "Yes" << "
";
    else cout << "No" << "
";
    
    return 0;
}

拆分-Nim游戏

链接： https://www.acwing.com/problem/content/896/

分析：

这题目题意不清。。。

题目说是，可以从一个大的堆里面拿出若干个，可以放入两个更小的石堆里面，而且还能多放点，比如从大堆里拿了5个，可以向一堆放5个，可以给另一堆也放5个，放4个，... ，放0个。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int f[N];

int sg(int x)
{
    if (f[x] != -1) return f[x];
    
    unordered_set<int> st;
    for (int i = 0; i < x; i ++ )
        for (int j = 0; j <= i; j ++ )
            st.insert(sg(i) ^ sg(j));
    
    for (int i = 0; ; i ++ ) 
        if (!st.count(i)) //count(x)返回x的个数
            return f[x] = i;
}
int main()
{
    cin >> n;

    memset(f, -1, sizeof f);    
    int ans = 0;
    while (n -- )
    {
        int x; cin >> x;
        ans ^= sg(x);
    }
    
    if (ans) cout << "Yes" << "
";
    else cout << "No" << "
";
    
    return 0;
}

移棋子游戏

链接：https://www.acwing.com/problem/content/1321/

分析：

则就是sg函数的模板题了。

只需要将每个棋子的sg函数求出来异或一下就OK了。

代码：

#include <iostream>
#include <unordered_set>
#include <cstring>

using namespace std;

const int N = 2010, M = 6010;

int n, m, k;
int h[N], e[M], ne[M], tot;
int f[M];

void add(int a, int b)
{
    e[++ tot] = b, ne[tot] = h[a], h[a] = tot; 
}

int sg(int x)
{
    if (f[x] != -1) return f[x];
    
    unordered_set<int> st;
    for (int i = h[x]; ~i; i = ne[i])
    {
        int y = e[i];
        st.insert(sg(y));
    }
    
    for (int i = 0; ; i ++ )
        if (!st.count(i)) return f[x] = i;
}

int main()
{
    cin >> n >> m >> k;
    
    memset(h, -1, sizeof h);
    memset(f, -1, sizeof f);
    for (int i = 0; i < m; i ++ )
    {
        int x, y; cin >> x >> y;
        add(x, y);
    }
    
    int ans = 0;
    for (int i = 0; i < k; i ++ )
    {
        int x; cin >> x;
        ans ^= sg(x);
    }
    
    if (ans) cout << "win" << "
";
    else cout << "lose" << "
";
    
    return 0;
}

取石子【难】

链接：https://www.acwing.com/problem/content/1323/

分析：

完全不知道该怎么想，正解是，让a表示只有一颗石子的堆数，让b表示每堆石子数大于1个的  石子数+堆数-1.

然后，必胜局面是b为奇数。

按照yxc说法，奇数状态必存在一种方式，到达偶数状态，而偶数状态只能转向奇数状态，最后，先手面对一堆一个石子，就赢了。

分为五种情况：用f[a][b]表示关系

f[a-1][b],从a中取出一个石子(a大于0）

f[a][b-1]，从b中取出一个石子（b大于0）

f[a][b-1],和并b中两堆(b大于1）

f[a-2][b+3]，合并a中两个（a大于1）

f[a-1][b+1]，合并a中的一个和b中的一堆

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 55, M = 50050;

int f[N][M];

int dp(int a, int b)
{
    int &x = f[a][b];
    if (x != -1) return x;
    if (!a) return x = b % 2;//a等于0，只要看b是否为奇数就好了
    if (b == 1) return dp(a + 1, 0);
    //b只有一堆，这一堆里只有一个，所以，它可以算入一个a了
    
    if (a && !dp(a - 1, b)) return x = 1;
    if (b && !dp(a, b - 1)) return x = 1;
    if (a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return x = 1;
    if (a && b && !dp(a - 1, b + 1)) return x = 1;
    
    return x = 0;
}
int main()
{
    memset(f, -1, sizeof f);
    
    int T; cin >> T;
    while (T -- )
    {
        int n; cin >> n;
        int a = 0, b = 0;
        for (int i = 0; i < n; i ++ )
        {
            int x; cin >> x;
            if (x == 1) a ++;
            else b += b ? x + 1 : x;//第一次，一堆，x个，其他，加一个堆数，加x的个数
        }
        
        if (dp(a, b)) cout << "YES" << "
";
        else cout << "NO" << "
";
    }
    
    return 0;
}

取石子游戏【超难】

链接：https://www.acwing.com/problem/content/1324/

捡石头：

链接：https://ac.nowcoder.com/acm/problem/14388

分析：

谁是最后一个，谁就赢。

 如果n % (m + 1) == 0，那么先手必败，因为不管先手拿多少石头，后手都可以凑出来m + 1。这样，一直到最后。

如果n % (m + 1) != 0，那么后手必败，因为第一次先手先拿，然后后手再拿，然后先手就可以凑出来m+1，然后持续到最后。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <cctype>
#include <numeric>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")

using namespace std;

#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);

int n, m;

void work()
{
  cin >> n >> m;

  if (n <= m) puts("first");
  else 
  {
    if (n % (m + 1) == 0) puts("second");
    else puts("first");
  }  
}

int main()
{
  //ios;
  int T = 1;
  // cin >> T;
  while (T -- )
  {
    work();
  }

  return 0;
}

小牛vs小客：

https://ac.nowcoder.com/acm/problem/15065

分析：

当n小于等于2的时候，很显然，XiaoNiu一定会赢，但是当n大于2的时候，不管先手怎么办，后手都可以将剩下的石子分为偶数部分，所以后手必赢

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <cctype>
#include <numeric>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")

using namespace std;

#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);


void work()
{
  int n;
  while (cin >> n)
  {
    if (n <= 2) cout << "XiaoNiu" << "
";
    else cout << "XiaoKe" << "
";
  }
}

int main()
{
  //ios;
  int T = 1;
  // cin >> T;
  while (T -- )
  {
    work();
  }

  return 0;
}

栗酱的异或和

分析：

NIM游戏，这里，第k堆是先要选的，也是必选的，是先手要选的。同时，谁先不能取谁就输了，也就是谁最后一个取，谁就赢了。

如果不考虑第一次要选k的话，异或和为0，先手必败（所有物品都被取光是一个必败局面，因为队友取走了最后一件物品，已经胜利了）。

那么这个时候，加上先选第k个物品的限制。

我们可以假设第一次取第k堆时，没有取，留到最后先手再取。

这样，我们将除了第k堆以外的石子异或起来，假设结果为x的话，这是就是先手所面临的局面，要将第k堆里取出若干个，将这x个石子全部消掉，消掉的话，就意味着，最后一次是先手拿完的（x=0的话，先手也要拿，因为先手必须要拿第k堆至少一个石子，不能不拿，这个时候，可以将第k堆全部拿了就可以了）。但是，如果x大于第k堆的数量，就没办法拿了，当x等于第k堆的数量的时候，

这样，我们将除了第k堆以外的石子异或起来，假设结果为x的话，我们的目的就是让异或的结果不为0，所以，如果第k堆的石子数大于x的话，那么，我们去掉a[k] - x个石子就可以了，先手拿掉(a[k]-x)个石子，让所有石子的异或和为0，将必败局面丢给了后手。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits.h>
#include <sstream>
#include <cctype>
#include <numeric>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inlin")

using namespace std;

#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010, INF = 0x3f3f3f3f, mod = 1e9 + 7, base = 131;
const double eps = 1e-6, PI = acos(-1);

int n, k;
int a[N];

void work()
{
  cin >> n >> k;
  int ans = 0;
  for (int i = 1; i <= n; i ++ )
  {
    cin >> a[i];
    if (i == k) continue;
    ans ^= a[i];
  }
  // cout << ans << endl;
  // cout << (ans ^ a[k]) << "
";
  if (ans < a[k]) cout << "Yes" << "
";
  else cout << "No" << "
";
}

int main()
{
  //ios;
  int T = 1;
  cin >> T;
  while (T -- )
  {
    work();
  }

  return 0;
}