bzoj 1874 取石子游戏 题解 & SG函数初探
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了bzoj 1874 取石子游戏 题解 & SG函数初探,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2522字,纯文字阅读大概需要4分钟。
内容图文
![bzoj 1874 取石子游戏 题解 & SG函数初探](/upload/InfoBanner/zyjiaocheng/1110/aab6bfd2deb145c6a1f70222ae008a7b.jpg)
【原题】
1874: [BeiJing2009 WinterCamp]取石子游戏
Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 334 Solved: 122
[Submit][Status]
Description
Input
Output
Sample Input
7
6
9
3
2
1
2
Sample Output
1 1
Hint
例子中共同拥有四堆石子,石子个数分别为7、6、9、3,每人每次能够从不论什么一堆石子中取出1个或者2个石子,小H有必胜策略,其实仅仅要从第一堆石子中取一个石子就可以。
数据规模和约定
数据编号 N范围 Ai范围 数据编号 N范围 Ai范围
1 N=2 Ai≤10 6 N≤10 Ai≤10
2 N=2 Ai≤1000 7 N≤10 Ai≤100
3 N=3 Ai≤100 8 N≤10 Ai≤1000
4 N≤10 Ai≤4 9 N≤10 Ai≤1000
5 N≤10 Ai≤7 10 N≤10 Ai≤1000
对于所有数据,M≤10,Bi≤10
HINT
Source
【分析】事实上我是心血来潮想大概学一下博弈论有关的题目。
博文推荐:http://www.cnblogs.com/frog112111/p/3199780.html
首先是最简单的Nim游戏:有N堆石子,每次从一堆中取出不为空的石子,不能取者为负。推断先手是否必胜。有一个小小的结论:后手必胜当且仅当全部石子的异或和为0。
再麻烦一点。规定每次取的石子个数,比方每次仅仅能取1,3,4。我们先考虑仅仅有一堆石子。
(下面摘自那个博客)
首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。比如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于一个给定的有向无环图,定义关于图的每一个顶点的Sprague-Grundy函数g例如以下:g(x)=mex{ g(y) | y是x的后继 },这里的g(x)即sg[x]
sg[0]=0,f[]={1,3,4},
x=1时,能够取走1-f{1}个石子,剩余{0}个,mex{sg[0]}={0},故sg[1]=1;
x=2时,能够取走2-f{1}个石子,剩余{1}个,mex{sg[1]}={1},故sg[2]=0;
x=3时,能够取走3-f{1,3}个石子,剩余{2,0}个,mex{sg[2],sg[0]}={0,0},故sg[3]=1;
x=4时,能够取走4-f{1,3,4}个石子,剩余{3,1,0}个,mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;
x=5时,能够取走5-f{1,3,4}个石子,剩余{4,2,1}个,mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3;
以此类推.....
x 0 1 2 3 4 5 6 7 8....
sg[x] 0 1 0 1 2 3 2 0 1....
在这里,那个异或和的结论还是正确的。假设sg[N]=0,那么就存在后手必胜的策略。
可是假设有多堆石子,应该怎么办?直接把所有的SG所有异或起来,也是推断是否是0。
知道了这些结论,那道题也就成了傻题。前面是裸的SG,后面再枚举一下就可以。
【代码】
#include<cstdio> #define N 1005 using namespace std; int sg[N],f[N],hash[N],a[N],sum,temp,i,j,n,m; void get_SG(int up) { sg[0]=0; for (int i=1;i<=up;i++) { for (int j=1;f[j]<=i&&j<=m;j++) hash[sg[i-f[j]]]=i; for (int j=0;j<=up;j++) if (hash[j]!=i) {sg[i]=j;break;} } } int main() { scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for (i=1;i<=m;i++) scanf("%d",&f[i]); get_SG(1000); for (i=1;i<=n;i++) sum^=sg[a[i]]; if (!sum) {printf("NO");return 0;} for (i=1;i<=n;i++) { temp=sum^sg[a[i]]; for (j=1;f[j]<=a[i]&&j<=m;j++) if (!(temp^sg[a[i]-f[j]])) { printf("YES\n%d %d",i,f[j]); return 0; } } }
原文:http://www.cnblogs.com/hrhguanli/p/4060267.html
内容总结
以上是互联网集市为您收集整理的bzoj 1874 取石子游戏 题解 & SG函数初探全部内容,希望文章能够帮你解决bzoj 1874 取石子游戏 题解 & SG函数初探所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。