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

时间:2022-09-05 18:55:18

题目大意

  有\(n\)堆石子,两个人可以轮流取石子。每次可以选择一堆石子,做出下列的其中一点操作:

  1.移去整堆石子

  2.设石子堆中有\(x\)个石子,取出\(y\)堆石子,其中\(1\leq y<x\)且\((x,y)=1\)

  取出最后一颗石子的人胜利。问先手胜还是后手胜。

  \(n\leq 100\),每堆石子个数\(a_i\leq {10}^6\)

题解

  基础知识:SG函数。

  令\(x\)为某堆石子的个数。

  \(SG(i)=mex(SG(j)~~~~((i,j)=1)\)

  先用暴力求一遍SG值,然后会发现:

  当\(x\)为质数时,\(SG(x)=\)\(x\)是第几个质数\(+1\)。因为前面的质数都可以选,所以就是这个。

  当\(x\)不是质数时,设\(y\)为\(x\)的最小质因子,则\(SG(x)=SG(y)\)。因为\(y\)之前的都可以选,\(y\)不能选,所以就是\(SG(y)\)。

  然后直接线性筛计算答案。

  时间复杂度:\(O(a+n)\)

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void sort(int &a,int &b)
{
if(a>b)
swap(a,b);
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[100];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
sprintf(str,"%s.out",s);
freopen(str,"w",stdout);
#endif
}
int rd()
{
int s=0,c;
while((c=getchar())<'0'||c>'9');
do
{
s=s*10+c-'0';
}
while((c=getchar())>='0'&&c<='9');
return s;
}
int upmin(int &a,int b)
{
if(b<a)
{
a=b;
return 1;
}
return 0;
}
int upmax(int &a,int b)
{
if(b>a)
{
a=b;
return 1;
}
return 0;
}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int sg[1000010];
int pri[100010];
int cnt;
int main()
{
sg[0]=0;
sg[1]=1;
int i,j;
for(i=2;i<=1000000;i++)
{
if(!sg[i])
{
pri[++cnt]=i;
sg[i]=cnt+1;
}
for(j=1;j<=cnt&&i*pri[j]<=1000000;j++)
{
sg[i*pri[j]]=sg[pri[j]];
if(i%pri[j]==0)
break;
}
}
int t;
scanf("%d",&t);
while(t--)
{
int n,x,s=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
s^=sg[x];
}
if(s)
printf("Alice\n");
else
printf("Bob\n");
}
return 0;
}

【GZOI2015】石子游戏 博弈论 SG函数的更多相关文章

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

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

  2. 【BZOJ1874】取石子游戏(SG函数)

    题意:小H和小Z正在玩一个取石子游戏. 取石子游戏的规则是这样的,每个人每次可以从一堆石子中取出若干个石子, 每次取石子的个数有限制,谁不能取石子时就会输掉游戏. 小H先进行操作, 他想问你他是否有必 ...

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

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

  4. &lbrack;BeiJing2009 WinterCamp&rsqb;取石子游戏 Nim SG 函数

    Code: #include<cstdio> #include<algorithm> #include<cstring> using namespace std; ...

  5. HDU 1864 Brave Game 【组合游戏,SG函数】

    简单取石子游戏,SG函数的简单应用. 有时间将Nim和.SG函数总结一下……暂且搁置. #include <cstdio> #include <cstring> #define ...

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

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

  7. Nim 游戏、SG 函数、游戏的和

    Nim游戏 Nim游戏定义 Nim游戏是组合游戏(Combinatorial Games)的一种,准确来说,属于“Impartial Combinatorial Games”(以下简称ICG).满足以 ...

  8. POJ&period;1067 取石子游戏 &lpar;博弈论 威佐夫博弈&rpar;

    POJ.1067 取石子游戏 (博弈论 威佐夫博弈) 题意分析 简单的威佐夫博弈 博弈论快速入门 代码总览 #include <cstdio> #include <cmath> ...

  9. HDU&period;2516 取石子游戏 &lpar;博弈论 斐波那契博弈&rpar;

    HDU.2516 取石子游戏 (博弈论 斐波那契博弈) 题意分析 简单的斐波那契博弈 博弈论快速入门 代码总览 #include <bits/stdc++.h> #define nmax ...

随机推荐

  1. 安装了ruby后怎么安装sass

    在命令行中输入 ruby -v 查看版本号 先移除默认的https://rubygems.org源,命令为gem sources --remove https://rubygems.org/,按回车 ...

  2. idea 显示行号

    File->Settings->Editor->General->Appearence->Show Line Number 选中之后"Apply",然 ...

  3. Codeforces 723e &lbrack;图论&rsqb;&lbrack;欧拉回路&rsqb;

    /* 不要低头,不要放弃,不要气馁,不要慌张. 题意: 给你一个有n个点,m条边的无向图,给每条边规定一个方向,使得这个图变成有向图,并且使得尽可能多的点入度与出度相同. 输出有多少个这样的点并且输出 ...

  4. heapsort

    Introduction to Algorithms Third Edition The (binary) heap data structure is an array object that we ...

  5. 【网络收集】如何修改vs tfs的登录名和密码 &period;

    连接TFS时,如果本机保存了用户的网络密码,不会出现用户名和密码的输入框,若要更换TFS的用户名和密码,需按以下步骤操作:控制面板--->用户账号--->管理网络密码,此时会列出所有保存了 ...

  6. indexOf&lpar;&rpar;不区分大小写用法

    str.toLowerCase().indexOf(str.toLowerCase())>=0; 对字符串进行统一小写转换. indexOf()查找到返回索引值大于=0; 未找到,返回-1; i ...

  7. Stackdump&colon; 一个可以离线看*的工具

    博客搬到了fresky.github.io - Dawei XU,请各位看官挪步.最新的一篇是:Stackdump: 一个可以离线看*的工具.

  8. HTML特殊布局--------双飞翼布局

    今天看到以前写的一篇布局的例子分享给大家,双飞翼布局. 什么是双飞翼布局?? 1.三列布局,中间宽度自适应,两边固定宽度; 2.中间栏在浏览器中优先展示渲染: 双飞翼布局的原理: 中间的盒子定100% ...

  9. 初识Haskell 五:自定义数据类型和类型类

    对Discrete Mathematics Using a Computer的第一章Introduction to Haskell进行总结.环境Windows 自定义数据类型 data type de ...

  10. 《2018面向对象程序设计(Java)课程学习进度条》

    周次 (阅读/编写)代码行数 发布博客量/博客评论数量 课堂/课余学习时间(小时) 最满意的编程任务 第一周 50/40 1/0 6/4 九九乘法表 第二周 100/80 1/0 6/8 实验5,6, ...