题目链接:
?pid=1729
题意:
又n个盒子,每个盒子的可以放 S个石头,里面已经有的石头的个数为C;
每次可以放的石头的个数不超过C*C。先手胜的输出Yes,后手胜输出No.
分析:
必败的状态很好找 当C + C * C < S && (C + 1) + (C + 1) * (C + 1) > = S;
然后我们对于每一组(c,s)来寻找他的必败状态。
枚举for(i = 1 ; i + i * i > = s;i++)
然后将 i与 c进行比较,,
如果 c >i, 那么这是一个必胜的状态 sg值为 s – c;
这点不懂得可以看看这个 @126/blog/static/171370086201101711276278/
如果 c == i , 那么必败。
如果 c < i 将i 看成 S 继续递归求解
代码如下:
#include <iostream>#include <cstdio>#include <cstring>using namespace std;int get(int c,int s){int q=0;while(q+q*q<s)q++;q–;if(c>q) return s-c;else return get(c,q);}int main(){int n,cas=1;while(~scanf("%d",&n)&&n){int s,c,ans=0;for(int i=0;i<n;i++){scanf("%d%d",&s,&c);ans^=get(c,s);}printf("Case %d:\n",cas++);if(ans) puts("Yes");else puts("No");}return 0;}
一张单程车票,一颗潇洒的心。