Stone Game

HDU - 1729

题意:
给定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");
}
}

最新文章

  1. 找到第k个最小元----快速选择
  2. Mac升级到Yosemite后默认的php版本不支持imagetfftext函数问题解决
  3. MSSQL FOR MXL PATH 运用(转载)
  4. java中DatagramSocket连续发送多个数据报包时产生丢包现象解决方案
  5. 神经网络(luogu 1038 答案错误,出题人语体教)
  6. ZZC语言代码风格
  7. 如何使用编辑模板在ASPxGridView中进行新增修改(除去常规的gridviw模板编辑外)
  8. Linux shell用法和技巧(转)
  9. 17个Web前端开发工程师必看的国外网站
  10. RazorEngine在非MVC下的使用,以及使用自定义模板
  11. springboot 配置文件 .properties和.yml的写法区别
  12. HDU4738【杭州网赛、判桥】
  13. Linux MySQL自己环境搭建的笔记
  14. 市场主流5款HTML5开发框架详解
  15. CodeForces-747C
  16. Variable binding depth exceeds max-specpdl-size
  17. Kudu之Tablet的发现过程
  18. 动手动脑(lesson 3)
  19. Python 面向对象详解
  20. C#与C++区别

热门文章

  1. png8 png24 png32
  2. xxx was built without full bitcode&quot; 编译错误解决
  3. 【二叉树的递归】04找出二叉树中路径和等于给定值的所有路径【Path Sum II】
  4. Arc066_E Addition and Subtraction Hard
  5. bzoj 1242 弦图判定 MCS
  6. TYVJ 1094 矩形分割
  7. 洛谷【P1873】砍树
  8. bzoj 4066 &amp; bzoj 2683 简单题 —— K-D树(含重构)
  9. 删除老的Azure Blob Snapshot
  10. POJ3468(线段树区间维护)