hdu 1850 Being a Good Boy in Spring Festival (nim游戏问必胜方案数,sg函数)

Posted by 111qqz on Wednesday, July 20, 2016

TOC

hdu1850题目链接
题意:n堆石子。。每堆可以取任意多个。。。先取完的赢。。问先手能否赢。。能赢的话第一步有几种取法。。
思路:sg函数。。对于方案数,可以用nim游戏的结论。

未命名
。设异或和为sum..那么统计满足 a[i]^sum<a[i]的个数就是第一步能走的方案数。

以及。。sg函数。。如果走的步数是任意的。。也就是没有限制。。。那么sg[i] = i…此时也就退化成了一般的nim游戏。。。

/* ***********************************************
Author :111qqz
Created Time :2016年07月20日 星期三 19时47分48秒
File Name :code/hdu/1850.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=105;
const int M=1E6+7;

int n;
int sg[M];
int a[N];
void sg_init()
{
    //这个可以记成结论23333
    for ( int i = 1 ; i < M ; i ++) sg[i] = i ;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    sg_init();
    while (~scanf("%d",&n))
    {
        if (n==0) break;
        int sum = 0 ;
        for ( int i = 1 ; i <= n ; i++)
        {
        int x;
        scanf("%d",&x);
        a[i] = x;
        sum^=sg[x];
        }
        if (sum==0)
        {
        puts("0");
        continue;
        }
        int ans = 0 ;
        for ( int i = 1 ; i <= n ; i++)
        if ((a[i]^sum)<a[i]) ans++;
        printf("%d\n",ans);
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付