博弈论

NIM游戏

https://www.cnblogs.com/dx123/p/17263056.html

P2197 【模板】Nim 游戏

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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 2147483647;
const ll INF = 1e18;
void solve(){
    int n;
    cin>>n;
    int shu=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        shu^=x;
    }    
    if(shu)cout<<"Yes\n";
    else cout<<"No\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

P1247 取火柴游戏

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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 2147483647;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    int shu=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        shu^=a[i];
    }
    if(!shu)return cout<<"lose\n",0;
    for(int i=1;i<=n;i++)
    {
        if((a[i]^shu)<a[i])
        {
            cout<<a[i]-(a[i]^shu)<<' '<<i<<'\n';
            for(int j=1;j<=n;j++)
            {
                if(j!=i)cout<<a[j]<<' ';
                else cout<<(a[i]^shu)<<' ';
            }
            break;
        }
    }

    return 0;    
}

P1288 取数游戏 II

https://www.luogu.com.cn/problem/P1288

如果向左有偶数个数或者向右有偶数个数，那么A赢，否则B赢，因为假设选择向右取的话，A每次都直接把下一个数取完，这样不管B怎么做，A总能先把0之前的那个数取完，如A先取完第一个，不管B将第二个取了多少，A直接取完第三个，第三个变成了0，所以已经无法回头了。

反之，如果都是奇数的话，无论A对第一个怎么取，对于B来说剩下的都只剩下偶数个边了，B直接按照上面的步骤暴力把下一个数取完就能赢。

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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 2147483647;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0)
        {
            if(i%2==0)return cout<<"YES\n",0;
            break;
        }
    }
    for(int i=n;i>=1;i--)
    {
        if(a[i]==0)
        {
            if((n-i+1)%2==0)return cout<<"YES\n",0;
            break;
        }
    }
    cout<<"NO\n";

    return 0;    
}

P4279 [SHOI2008] 小约翰的游戏

[NOIP2010 普及组] 三国游戏 题目imghttps://www.luogu.com.cn/problem/P1199