首页 > 代码库 > 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 【博弈】【搜索】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。