HDU 1729（石子）-白红宇

HDU 1729（石子）

阅读量：2125 次

发布时间：2019-04-30

本文共 993 字，大约阅读时间需要 3 分钟。

题意

一共有n个箱子，每个箱子容量为S，当前的石子为C。每次想一个箱子放石子，放的数量不能超过当前石子数的平方，谁先放完谁赢。

AC

SG函数

当C == S 时，sg(S, C) = 0

当C > T 时，假设T为当前最大的必败点，则T满足 T + T * T < S, (T + 1) + (T + 1) * (T + 1) >= S
sg(S, C) = mex(sg(S, C + 1), sg(S, C + 2) …… sg(S, S - 1), sg(S, S)) = S - C
证明：sg(S, S) = 0, sg(S, S - 1) = mex(sg(S, S)) = 1 ………

当C <= T，此时sg(S, C) = sg(T, C)，递归求sg

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #define N 100005#define P pair
           
            #define mk(a, b) make_pair(a, b)#define mem(a, b) memset(a, b, sizeof(a))int inf = 0x3f3f3f3f;#define ll long longusing namespace std;int get_sg(int s, int c) { // 求最大必败点 int q = sqrt(s); while (q + q * q >= s) q--; if (c > q) return s - c; else return get_sg(q, c);}int main(){ int Case = 1; int n; while (cin >> n, n) { int ans = 0; while (n--) { int s, c; cin >> s >> c; ans ^= get_sg(s, c); } cout << "Case " << Case++ << ":" << endl; if (ans) cout << "Yes\n"; else cout << "No\n"; } return 0;}