转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
HDU 1729
http://acm.hdu.edu.cn/showproblem.php?pid=1729
给出一些盒子,盒子有容量限制,有初始容量,每次给某一个盒子中添加石头。
添加的数量必须小于等于盒子中已有数量的平方。
感觉上有一点像巴什博弈,当然肯定比那个复杂
对于上限为S,当前容量如果为C,如果C+C*C<S&&(C+1)+(C+1)*(C+1)>=S,那么对于(S,C)显然是一个必败态
因为你不管一次取多少,不可能直接获胜,而对方都能直接获胜。
那么就继续递归求C状态。
如果最大的必败T>当前的C,那么就求出C后继中最小,也就是S-C
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10005
#define LL long long
#define inf 1<<29
#define eps 1e-7
using namespace std;
int get_sg(int s,int c){
int q=sqrt((double)s);
while(q+q*q>=s)
q--;
if(c>q) return s-c;
else return get_sg(q,c);
}
int main(){
int n,cas=0;
while(scanf("%d",&n)!=EOF&&n){
int s,c;
printf("Case %d:\n",++cas);
int ans=0;
while(n--){
scanf("%d%d",&s,&c);
ans^=get_sg(s,c);
}
if(ans)
puts("Yes");
else
puts("No");
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
90%的杭电母函数解题报告,有题目加解题思路,和ac掉的代码
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦