首页 > 其他 > 详细

SG博弈简单题

时间:2015-08-10 14:51:28      阅读:266      评论:0      收藏:0      [点我收藏+]



ZOJ - 2083 - Win the Game

题目传送:Win the Game

最近正在慢慢体会博弈里面的SG函数的意义

此题是最简单的SG博弈问题,只需打个表就OK了

AC代码:

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;

int sg[55];
int vis[55];

void get_sg() {
    sg[0] = 0;
    sg[1] = 0;
    for(int i = 2; i < 55; i ++) {
        memset(vis, 0, sizeof(vis));
        vis[sg[i - 2]] = 1;
        for(int j = 1; j + 2 <= i; j ++) {
            vis[sg[j] ^ sg[i - j - 2]] = 1;
        }
        for(int j = 0;; j ++) {
            if(!vis[j]) {
                sg[i] = j;
                break;
            }
        }
    }
}

int n;

int main() {
    get_sg();
    //for(int i = 0; i < 55; i ++) cout << sg[i] << " ";
    while(scanf("%d", &n) != EOF) {
        int SG = 0, t;
        for(int i = 0; i < n; i ++) {
            scanf("%d", &t);
            SG ^= sg[t];
        }
        if(SG == 0) {
            printf("No\n");
        }
        else printf("Yes\n");
    }
    return 0;
}



版权声明:本文为博主原创文章,未经博主允许不得转载。

SG博弈简单题

原文:http://blog.csdn.net/u014355480/article/details/47397913

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