bzoj 1188 [HNOI2007]分裂游戏 SG函数 SG定理

时间:2022-04-23 18:39:52

[HNOI2007]分裂游戏

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1394  Solved: 847
[Submit][Status][Discuss]

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

HINT

Source

题解:这道题目,将每颗石子单独作为一个游戏去玩,这样枚举下一次的j,k

最后再xor起来即可。

方法的话就是判断取了这一个后下一个状态是不是必败了即可。

 #pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring> #define N 27
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int a[N],sg[N];
void pre()
{
bool mark[];
sg[]=;
for(int i=;i<=;i++)
{
memset(mark,,sizeof(mark));
for(int j=;j<i;j++)
for(int k=;k<=j;k++)
mark[sg[j]^sg[k]]=;
for(int j=;;j++)
if(!mark[j]){sg[i]=j;break;}
}
}
int main()
{
int t,n;
pre();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
int ans=,tot=;
for(int i=;i<=n;i++)
if(a[i]&)ans^=sg[n-i+];
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
for(int k=j;k<=n;k++)
if((ans^sg[n-i+]^sg[n-j+]^sg[n-k+])==)
{
tot++;
if(tot==)printf("%d %d %d\n",i-,j-,k-);
}
if(!tot)printf("-1 -1 -1\n");
printf("%d\n",tot);
}
}

bzoj 1188 [HNOI2007]分裂游戏 SG函数 SG定理的更多相关文章

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

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

  2. bzoj 1188 &lbrack;HNOI2007&rsqb;分裂游戏(SG函数,博弈)

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

  3. BZOJ 1188&colon; &lbrack;HNOI2007&rsqb;分裂游戏&lpar;multi-nim&rpar;

    Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1386  Solved: 840[Submit][Status][Discuss] Descripti ...

  4. BZOJ 1188 &lbrack;HNOI2007&rsqb;分裂游戏

    AC通道:http://www.lydsy.com/JudgeOnline/problem.php?id=1188 学习SG函数的过程中,我先看了一篇叫做 <2008-贾志豪-组合数学略述... ...

  5. bzoj 1188 &colon; &lbrack;HNOI2007&rsqb;分裂游戏 sg函数

    题目链接 给n个位置, 每个位置有一个小球. 现在两个人进行操作, 每次操作可以选择一个位置i, 拿走一个小球.然后在位置j, k(i<j<=k)处放置一个小球. 问你先进行什么操作会先手 ...

  6. 【BZOJ】1188 &lbrack;HNOI2007&rsqb;分裂游戏

    [算法]博弈论 [题解] 我们的目的是把游戏拆分成互不影响的子游戏,考虑游戏内的转移. 如果把每堆视为子游戏,游戏之间会相互影响,不成立. 将每堆的一个石子视为子游戏,其产生的石子都在同一个子游戏中. ...

  7. BZOJ P1188 HNOI2007 分裂游戏——solution

    题目描述: (<--这个) 组合游戏,——把每个石头看做一个游戏, Multi_game——消去i上的石子后,,k上的游戏又多了一个: 于是就套用multi_game的模型即可 求解SG函数时, ...

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

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

  9. BZOJ 1188 &sol; Luogu P3185 &lbrack;HNOI2007&rsqb;分裂游戏 &lpar;SG函数&rpar;

    题意 有n个格子,标号为0 ~ n-1,每个格子上有若干石子,每次操作可以选一个0 ~ n-2的格子上的一颗石子,分裂为两颗,然后任意放在后面的两个格子内,这两个格子可以相同.求使先手必胜的第一步的方 ...

随机推荐

  1. Titanium&period;App&period;Properties 对象

    Titanium.App.Properties是用来管理键值对数据的一个很方便的对象.在保存数据的时候,在Ti.App.Properties.setString相对应的Key的值中设置你要保存的值即可 ...

  2. swfit-计时器

    import UIKit class FourVC: UIViewController { var label:UILabel = UILabel() var index : Int = var ti ...

  3. Python学习三---序列、列表、元组

    一.序列 1.1.序列概念 pythn中最基本的数据结构是序列(sequence). 序列中每个元素被分配一个序号-元素索引,第一个索引是0,第二个是1,以此类推.类似JAVA中数组和集合中的下标. ...

  4. ParNew收集器

    ParNew收集器其实就是Serial收集器的多线程版本,除了使用多条线程进行垃圾收集之外,其余行为包括Serial收集器可用的所有控制参数,其中Par是Paralle简写l 并行(Parallel) ...

  5. 静态代码检查工具 cppcheck 的使用(可分别集成到VS和QT Creator里)

    CppCheck是一个C/C++代码缺陷静态检查工具.不同于C/C++编译器及其它分析工具,CppCheck只检查编译器检查不出来的bug,不检查语法错误.所谓静态代码检查就是使用一个工具检查我们写的 ...

  6. 翻译:MariaDB ALTER TABLE语句

    */ .hljs { display: block; overflow-x: auto; padding: 0.5em; color: #333; background: #f8f8f8; } .hl ...

  7. maven pom&period;xml 里scope的作用

    <dependency>中<scope>,它主要管理依赖的部署.目前<scope>可以使用5个值:     * compile,缺省值,适用于所有阶段,会随着项目一 ...

  8. MYSQL 总结——2

    1.mysql限制显示条目数:Limit,  Offset 图片网址:https://sqlbolt.com/lesson/filtering_sorting_query_results 实例: SE ...

  9. (数据分析)第02章 Python语法基础,IPython和Jupyter Notebooks&period;md

    第2章 Python语法基础,IPython和Jupyter Notebooks 当我在2011年和2012年写作本书的第一版时,可用的学习Python数据分析的资源很少.这部分上是一个鸡和蛋的问题: ...

  10. Best Sightseeing Pair LT1014

    Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and t ...