博弈论(SG函数):HNOI 2007 分裂游戏

时间:2022-09-07 22:25:40

Description

聪聪和睿睿最近迷上了一款叫做分裂的游戏。 该游戏的规则试: 共有 n 个瓶子, 标号为 0,1,2.....n-1, 第 i 个瓶子中装有 p[i]颗巧克力豆,两个人轮流取豆子,每一轮每人选择 3 个瓶子。标号为 i,j,k, 并要保证 i < j , j < = k 且第 i 个瓶子中至少要有 1 颗巧克力豆,随后这个人从第 i 个瓶子中拿走一颗豆 子并在 j,k 中各放入一粒豆子(j 可能等于 k) 。如果轮到某人而他无法按规则取豆子,那么他将输 掉比赛。胜利者可以拿走所有的巧克力豆! 两人最后决定由聪聪先取豆子,为了能够得到最终的巧克力豆,聪聪自然希望赢得比赛。他思考 了一下,发现在有的情况下,先拿的人一定有办法取胜,但是他不知道对于其他情况是否有必胜 策略,更不知道第一步该如何取。他决定偷偷请教聪明的你,希望你能告诉他,在给定每个瓶子 中的最初豆子数后是否能让自己得到所有巧克力豆,他还希望你告诉他第一步该如何取,并且为 了必胜,第一步有多少种取法? 假定 1 < n < = 21,p[i] < = 10000

Input

输入文件第一行是一个整数t表示测试数据的组数,接下来为t组测试数据(t<=10)。每组测试数据的第一行是瓶子的个数n,接下来的一行有n个由空格隔开的非负整数,表示每个瓶子中的豆子数。

Output

对 于每组测试数据,输出包括两行,第一行为用一个空格两两隔开的三个整数,表示要想赢得游戏,第一步应该选取的3个瓶子的编号i,j,k,如果有多组符合要 求的解,那么输出字典序最小的一组。如果无论如何都无法赢得游戏,那么输出用一个空格两两隔开的三个-1。第二行表示要想确保赢得比赛,第一步有多少种不 同的取法。

Sample Input

2
4
1 0 1 5000
3
0 0 1

Sample Output

0 2 3
1
-1 -1 -1
0
  这道题,了解SG函数就可以发现,对每个巧克力豆求SG函数是可做的,这里先预处理,不过是倒着的。
 #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=;
int sg[N],vis[N*N*N],f[N];
//注意这里mex的值域很大!!!
int T,n,ans,tot; int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int pi,pj,pk;scanf("%d",&T);
for(int i=,p;i<=;i++){
memset(vis,,sizeof(vis));
for(int j=i-;j>=;j--)
for(int k=j;k>=;k--)
vis[sg[j]^sg[k]]=;
for(p=;vis[p];p++);sg[i]=p;
}
while(T--){
scanf("%d",&n);ans=;
for(int i=;i<=n;i++){
scanf("%d",&f[i]);
if(f[i]&)ans^=sg[n-i+];
}
if(ans==)
printf("-1 -1 -1\n0\n");
else{
pi=pj=pk=tot=;
for(int i=n-;i>=;i--)if(f[i])
for(int j=n;j>=i+;j--)
for(int k=n;k>=j;k--)
if((sg[n-i+]^sg[n-j+]^sg[n-k+])==ans)
{tot+=;pi=i-;pj=j-;pk=k-;}
printf("%d %d %d\n%d\n",pi,pj,pk,tot); }
} return ;
}

  思路真的很简单很简单……

博弈论(SG函数):HNOI 2007 分裂游戏的更多相关文章

  1. bzoj1188 &lbrack;HNOI2007&rsqb;分裂游戏 博弈论 sg函数的应用

    1188: [HNOI2007]分裂游戏 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 973  Solved: 599[Submit][Status ...

  2. &lbrack;BZOJ 1188&rsqb; &lbrack;HNOI2007&rsqb; 分裂游戏 【博弈论&vert;SG函数】

    题目链接:BZOJ - 1188 题目分析 我们把每一颗石子看做一个单个的游戏,它的 SG 值取决于它的位置. 对于一颗在 i 位置的石子,根据游戏规则,它的后继状态就是枚举符合条件的 j, k.然后 ...

  3. &lbrack;BZOJ 1874&rsqb; &lbrack;BeiJing2009 WinterCamp&rsqb; 取石子游戏 【博弈论 &vert; SG函数】

    题目链接:BZOJ - 1874 题目分析 这个是一种组合游戏,是许多单个SG游戏的和. 就是指,总的游戏由许多单个SG游戏组合而成,每个SG游戏(也就是每一堆石子)之间互不干扰,每次从所有的单个游戏 ...

  4. &lbrack;2016北京集训试题6&rsqb;魔法游戏-&lbrack;博弈论-sg函数&rsqb;

    Description Solution 首先,每个节点上的权值可以等价于该节点上有(它的权的二进制位数+1)个石子,每次可以拿若干个石子但不能不拿. 然后就发现这和NIM游戏很像,就计算sg函数em ...

  5. 【GZOI2015】石子游戏 博弈论 SG函数

    题目大意 有\(n\)堆石子,两个人可以轮流取石子.每次可以选择一堆石子,做出下列的其中一点操作: 1.移去整堆石子 2.设石子堆中有\(x\)个石子,取出\(y\)堆石子,其中\(1\leq y&l ...

  6. 【基础操作】博弈论 &sol; SG 函数详解

    博弈死我了……(话说哪个小学生会玩博弈论提到的这类弱智游戏,还取石子) 先推荐两个文章链接:浅谈算法——博弈论(从零开始的博弈论) 博弈论相关知识及其应用 This article was updat ...

  7. 2016多校联合训练1 B题Chess &lpar;博弈论 SG函数&rpar;

    题目大意:一个n(n<=1000)行,20列的棋盘上有一些棋子,两个人下棋,每回合可以把任意一个棋子向右移动到这一行的离这个棋子最近的空格上(注意这里不一定是移动最后一个棋子),不能移动到棋盘外 ...

  8. POJ 2425 A Chess Game 博弈论 sg函数

    http://poj.org/problem?id=2425 典型的sg函数,建图搜sg函数预处理之后直接求每次游戏的异或和.仍然是因为看不懂题目卡了好久. 这道题大概有两个坑, 1.是搜索的时候vi ...

  9. POJ2425 A Chess Game&lbrack;博弈论 SG函数&rsqb;

    A Chess Game Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 3917   Accepted: 1596 Desc ...

随机推荐

  1. xgboost原理及应用

    1.背景 关于xgboost的原理网络上的资源很少,大多数还停留在应用层面,本文通过学习陈天奇博士的PPT 地址和xgboost导读和实战 地址,希望对xgboost原理进行深入理解. 2.xgboo ...

  2. 初识html5 File API实现带有进度提示的文件上传

    Html5终于解决了上传文件的同时显示文件上传进度的老问题.现在大部分的网站用Flash去实现这一功能,还有一些网站继续采用Html <form>with enctype=multipar ...

  3. SQLite 数据库调研

    SQLite数据库的特点(转载的): ★技术上的优点和特性 SQLite是一个轻量级.跨平台的关系型数据库.既然号称关系型数据库,支持SQL92标准中常用的玩意儿(比如视图.事务.触发器等)就是理所当 ...

  4. Python之异常篇 &lbrack;待更新&rsqb;

    简介 当你的程序中出现某些 异常的 状况的时候,异常就发生了.例如,当你想要读某个文件的时候,而那个文件不存在.或者在程序运行的时候,你不小心把它删除了.上述这些情况可以使用异常来处理. 假如你的程序 ...

  5. HTML5之地理信息应用 获取自己的位置

    上代码: window.onload = function() { if (navigator.geolocation) { navigator.geolocation.getCurrentPosit ...

  6. C语言实验——一元二次方程Ⅱ

    C语言实验--一元二次方程Ⅱ Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 169  Solved: 131 [Submit][Status][Web ...

  7. MVC验证10-到底用哪种方式实现客户端服务端双重异步验证

    原文:MVC验证10-到底用哪种方式实现客户端服务端双重异步验证 本篇将通过一个案例来体验使用MVC的Ajax.BeginForm或jQuery来实现异步提交,并在客户端和服务端双双获得验证.希望能梳 ...

  8. &lbrack;PCB设计&rsqb; 3、用CAM350修改GERBER文件(删除某些部分)

    1.问题产生 由于在电子元件封装时阻焊开窗未处理好,生成的GERBER文件在生产钢网时容易出现错误.比如:测试点上不需要上锡,如果封装元件时采用焊盘修改而来,结果往往使paste层在该测试点上有覆盖, ...

  9. JWPlayer支持SD&sol;HD

    First, we have to render two versions of our video: an SD (standard definition) and HD (high definit ...

  10. UWP中实现大爆炸效果(一)

    自从老罗搞出大爆炸之后,各家安卓都内置了类似功能.UWP怎么能落下呢,在这里我们就一起撸一个简单的大爆炸实现. 闲话不说,先上效果: 因为代码太多,所以我打算写成一个系列,下面是第一篇的正文: 首先, ...