HDU1729_Stone Game_新型求sg值

/*
*State:     1729    0MS    268K    726 B    C++
*题目大意：
*        （取石子游戏）有n个箱子，体积为Si，当前箱子里的石子数为Ci。
*        两个人轮流往箱子里放石子，而且每一次放是数量都有限制，不能
*        超过当前箱子内石子数的平方。例如箱子里有3颗石子，那么下一个
*        人就可以放1~9颗石子，直到箱子被装满。当有一方放不下石子时游
*        戏结束，最后放不下石子的人输。
*解题思路：
*        一开始我的想法就是正确的，求sg值，sg值也能用笔模拟出来，但
*        关键的一步是箱子的容量<1000 000,这个数值太大了，一般的sg值
*        模拟不出来，数组会爆掉。求sg的代码都写好了，就是数值大了就爆，
*        看了解题报告，原来找sg数据特点，然后用迭代来求，几行代码搞定，
*        代码写得真优雅，比起我丑陋无比的求sg代码。
*解题感想：
*        这道题目就是新型的求sg值，比较经典。注意sg数列的规律特点。
*/

View Code

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int get_sg(int box, int sto)
 6 {
 7     int sqrtbox = (int)sqrt((double)box) + 1;
 8     while(sqrtbox * sqrtbox + sqrtbox >= box)
 9         sqrtbox--;
10     if(sqrtbox < sto)
11         return box - sto;
12     else
13         get_sg(sqrtbox, sto);
14 }
15 
16 int main(void)
17 {
18 #ifndef ONLINE_JUDGE
19     freopen("in.txt", "r", stdin);
20 #endif
21     int n, cas_c = 1;
22     while(scanf("%d", &n), n)
23     {
24         int yihuo = 0;
25         for(int i = 0; i < n; i++)
26         {
27             get_sg(n, 0);
28             int box, sto;
29             scanf("%d %d", &box, &sto);
30             if(box != 0)
31                 yihuo ^= get_sg(box, sto);
32             else
33                 yihuo ^= 0;
34         }    
35         printf("Case %d:\n", cas_c++);
36         if(!yihuo)
37             printf("No\n");
38         else
39             printf("Yes\n");
40     }
41     return 0;
42 }