首页 > 其他 > 详细

数学知识-博弈论

时间:2021-02-18 23:27:26      阅读:26      评论:0      收藏:0      [点我收藏+]

Nim游戏

题目

技术分享图片

 

 

算法思路

技术分享图片

 

 

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

/*
先手必胜状态:先手操作完,可以走到某一个必败状态
先手必败状态:先手操作完,走不到任何一个必败状态
先手必败状态:a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态:a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
*/

int main(){
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res == 0) puts("No");
    else puts("Yes");
}

台阶-Nim游戏

题目

技术分享图片

 

 算法思路

技术分享图片

 

 

#include <iostream>

using namespace std;

int main()
{
    int res = 0;
    int n;
    cin >> n;

    for(int i = 1 ; i <= n ; i++)
    {
        int x;
        cin >> x;
        if(i % 2) res ^= x;
    }

    if(res) puts("Yes");
    else puts("No");
    return 0;
}

集合-Nim游戏

题目

技术分享图片

 

 算法思路

技术分享图片

 

 技术分享图片

 

 

#include<bits/stdc++.h>
using namespace std;
int s[10010],f[10010];

int n,k;

int sg(int x)
{
    //记忆化搜索,如果f[x]已经被计算过,则直接返回
    if(f[x]!=-1)
        return f[x];
    //用一个哈希表来存每一个局面能到的所有情况,便于求mex
    set<int>S;
    for(int i=0;i<k;i++)
    {
        int sum=s[i];
        //如果可以减去s[i],则添加到S中
        if(x>=sum)
            S.insert(sg(x-sum));
    }
    //求mex(),即找到最小并不在原集合中的数
    for(int i=0;;i++)
    {
        if(!S.count(i))
            return f[x]=i;
    }
}

int main()
{
    int i,j;
    memset(f,-1,sizeof(f));
    cin>>k;
    for(i=0;i<k;i++)
        cin>>s[i];
    cin>>n;
    int res=0;
    for(i=0;i<n;i++)
    {
        int x;
        cin>>x;
        res^=sg(x);
    }
    if(res!=0)
        puts("Yes");
    else
        puts("No");
    return 0;
}

拆分-Nim游戏

题目

技术分享图片

算法思路

技术分享图片

 

 

#include<bits/stdc++.h>
using namespace std;

int s[110],f[110];
int n;

int sg(int x)
{
    if(f[x]!=-1)
        return f[x];
    set<int>S;
    for(int i=0;i<x;i++)
    {
        //规定j不大于i,避免重复
        for(int j=0;j<=i;j++)
        {
            //相当于一个局面拆分成了两个局面,由SG函数理论,多个独立局面的SG值
            //等于这些局面SG值的异或和
            S.insert(sg(i)^sg(j));
        }
    }
    for(int i=0;;i++)
    {
        if(!S.count(i))
            return f[x]=i;
    }

}

int main()
{
    int i,j;
    memset(f,-1,sizeof f);
    cin>>n;
    int res=0;
    for(i=0;i<n;i++)
    {
        int x;
        cin>>x;
        res^=sg(x);
    }
    if(res!=0)
        puts("Yes");
    else
        puts("No");
    return 0;
}

 

数学知识-博弈论

原文:https://www.cnblogs.com/xiaofengzai/p/14413853.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!