首页 > 代码库 > Zoj 3591 Nim 【博弈】【搜索】

Zoj 3591 Nim 【博弈】【搜索】

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3591

题目大意:给你T组case,每组case有N,S,W三个数字,根据题目给出的代码可以算出每组石子个数a[i]。

已知了N组石子的个数,现在让你来选出连续的石子堆,使得先手会赢,问有多少种选法。

比如给出的样例:NSW分别是 3 1 1

则算出来的每堆石子的个数a[i]是 1 1 1,则 1 1 1三堆石子的选法有:

选第一堆,选第二堆,选第三堆,选第一堆到第三堆。

我们分别对第i堆取^,得到的值c[i]是:1  0 1 

得到c[i]的值之后,我们可以有这样的想法:比如c[1]和c[3]取^之后是0,说明你选择第二堆和第三堆是不能先手赢的。c[1]和c[2]取^之后是1,说明单选第二堆是先手赢的。为了表示出来第一堆,我们把c[0]赋值为0。

其实也就是在数组c[i]中找有没有相同的。上组给出的1 0 1 加上 c[0]=0, 其实是0 1 0 1 ,有两个0,两个1,说明选了两个0或者两个1都是不满足条件的选择,而总的选择是:C(N,2),也就是总的选择减去不能满足条件的选择。

不能满足条件的选择是C(num,2)的和。

#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
#define LL long long

int main ()
{
    map<LL, LL > v;
    LL T;
    LL a[100005];
    LL c[100005];
    scanf("%lld",&T);
    while(T--)
    {
        LL ans = 0;
        v.clear();
        LL N,S,W;
        scanf("%lld%lld%lld",&N,&S,&W);
        LL g = S;
        for (LL i=0; i<N; i++){
            a[i] = g;
            if(a[i] == 0)  a[i] = g = W;
            if(g%2 == 0)   g = (g/2);
            else           g = (g/2) ^ W;
        }
//        prLLf("石头的数量: ");
//        for(LL i=0;i<N;i++)
//            prLLf("%d ",a[i]);
//        prLLf("\n");

        c[0]=a[0];
        for(LL i=1;i<N;i++)
            c[i]=c[i-1]^a[i];

//        prLLf("取模之后的数量:");
//        for(LL i=0;i<N;i++)
//            prLLf("%d ",c[i]);
//        prLLf("\n");

        v[0]++;
        for(LL i=0;i<N;i++)
            v[c[i]]++;
        for(map<LL,LL>::iterator shit=v.begin();shit!=v.end();shit++){
            if(shit->second > 1) {
                LL num = shit->second;
                ans += num*(num-1)/2;
            }
        }
        LL sum = N+N*(N-1)/2;
        cout<<sum-ans<<endl;
    }
}


    

Zoj 3591 Nim 【博弈】【搜索】