hdu 1729 Stone Game
2024-09-06 12:29:45
Stone Game
题意:
给定n个箱子,每个箱子的容量为si,每个箱子里最初有ci个石子,每次放入石子不能超过放入前的石子数的平方,谁无法继续放入石子就算输。
/*
这是个SG函数的基础题?并不是的吧。。
求一个t使t+t*t=si,那么
1.当ci>t时,是必胜态,可以一次性放满箱子,即(si,si)。
2.当ci==t时,即便只放一个,下一个状态t+1+(t+1)*(t+1)一定能放满箱子必胜,所以ci==t这个状态必败。
3.当ci=si-t,同样的方法判断必胜必败,这样就可以通过递归求解sg值。 求sg:要得到sg需要对他的子集做mex{}运算,求出不属于该集合的最小非负整数。
在ci>t时满足
对于ci==si这个点,ci在有向图中没有出度(必败),因此返回si-ci=0,;
在ci==si-1时,它能到达的只有si点,sg[ci]={sg[si]=0},所以sg[ci]=1.
在ci==si-2时,他能到达的点有si-1,si,所以sg[ci]={sg[si-1]=1,sg[si]=0},所以sg[ci]=2.
因此在ci>t时返回si-ci
在ci==t是是必败,可直接返回0,也可以不做判断直接进入下一轮递归。
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#define maxn 51
using namespace std;
int n;
int getSG(int s,int c){
int t=sqrt(s);
while(t*t+t>=s)t--;
if(c>t)return s-c;
if(c==t)return ;
return getSG(t,c);
}
int main(){
int cas=;
while(scanf("%d",&n)){
cas++;
if(n==)return ;
printf("Case %d:\n",cas);
int ans=,s,c;
for(int i=;i<=n;i++){
scanf("%d%d",&s,&c);
ans^=getSG(s,c);
}
if(ans)puts("Yes");
else puts("No");
}
}
最新文章
- 找到第k个最小元----快速选择
- Mac升级到Yosemite后默认的php版本不支持imagetfftext函数问题解决
- MSSQL FOR MXL PATH 运用(转载)
- java中DatagramSocket连续发送多个数据报包时产生丢包现象解决方案
- 神经网络(luogu 1038 答案错误,出题人语体教)
- ZZC语言代码风格
- 如何使用编辑模板在ASPxGridView中进行新增修改(除去常规的gridviw模板编辑外)
- Linux shell用法和技巧(转)
- 17个Web前端开发工程师必看的国外网站
- RazorEngine在非MVC下的使用,以及使用自定义模板
- springboot 配置文件 .properties和.yml的写法区别
- HDU4738【杭州网赛、判桥】
- Linux MySQL自己环境搭建的笔记
- 市场主流5款HTML5开发框架详解
- CodeForces-747C
- Variable binding depth exceeds max-specpdl-size
- Kudu之Tablet的发现过程
- 动手动脑(lesson 3)
- Python 面向对象详解
- C#与C++区别
热门文章
- png8 png24 png32
- xxx was built without full bitcode"; 编译错误解决
- 【二叉树的递归】04找出二叉树中路径和等于给定值的所有路径【Path Sum II】
- Arc066_E Addition and Subtraction Hard
- bzoj 1242 弦图判定 MCS
- TYVJ 1094 矩形分割
- 洛谷【P1873】砍树
- bzoj 4066 &; bzoj 2683 简单题 —— K-D树(含重构)
- 删除老的Azure Blob Snapshot
- POJ3468(线段树区间维护)