$HDU1848\ Fibonacci\ again\ and\ again$ 博弈论
2024-10-08 05:37:22
正解:博弈论
解题报告:
首先按照套路显然是考虑先预处理出所有数的$SG$函数值然后全局的$SG$就是$SG(n)$^$SG(m)$^$SG(p)$,这儿应该麻油问题$QwQ$?
然后就考虑怎么求$SG$函数?于是就直接$SG(x)=mex\{SG(x-y),y\in Fib,x\ge y\}$就好鸭$QwQ$
$over!$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i) const int N=+;
int f[N],sg[N];
bool gdgs=,vis[N]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void pre()
{
f[]=;f[]=;rp(i,,)f[i]=f[i-]+f[i-];
rp(i,,){for(ri j=;f[j]<=i;++j)vis[sg[i-f[j]]]=;ri tmp=;while(vis[tmp])++tmp;sg[i]=tmp;for(ri j=;f[j]<=i;++j)vis[sg[i-f[j]]]=;}
} int main()
{
// freopen("1848.in","r",stdin);freopen("1848.out","w",stdout);
pre();
while(gdgs){ri m=read(),n=read(),p=read();if(!m && !n && !p)return ;printf(sg[m]^sg[n]^sg[p]?"Fibo\n":"Nacci\n");}
return ;
}
最新文章
- MyBatis Mapper.xml文件中 $和#的区别
- java基础5_数组
- python7 静态方法、类方法、属性方法 ;反射;异常处理
- System.Web.HttpRequestBase转HttpWebRequest
- 51nod 1336 RMQ逆问题
- Flex4/AS3.0自定义VideoPlayer组件皮肤,实现Flash视频播放器
- MySQL命令输入错误 取消命令
- U盘安装Win7 64位
- UVa 10256 - The Great Divide 判断凸包相交
- asp.mvc获取checkbox、radio、select的值
- 解决IE10以下对象不支持“bind”属性或方法
- 脸识别API微软牛津项目
- Codeforces 376C. Socks
- java导入项目有红色叹号
- 新概念英语(1-39)Don&#39;t drop it!
- 花生日记_花生日记APP下载_花生日记邀请码
- Python 字典(Dictionary) has_key()方法
- Android6.0 源码修改之Settings音量调节界面增加通话音量调节
- 《程序设计入门——C语言》翁恺老师 第一周编程练习记录
- 通过ldap验证svn服务
热门文章
- django之请求方法
- golang gin框架 使用swagger生成api文档
- 模板—点分治B(合并子树)(洛谷P4149 [IOI2011]Race)
- Pytorch: 命名实体识别: BertForTokenClassification/pytorch-crf
- hadoop2.6.0 + hbase-1.0.0 伪分布配置
- 【CSS3 + 原生JS】移动的标签
- 命名实体识别视频51cto
- 添加gitignore文件后使其生效
- P1045 和为给定数
- yum安装gcc和gcc-c++