題目鏈接

題意

一共有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 <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <map> #include <string.h> #include <cmath> #include <algorithm> #define N 100005 #define P pair<int,int> #define mk(a, b) make_pair(a, b) #define mem(a, b) memset(a, b, sizeof(a)) int inf = 0x3f3f3f3f; #define ll long long using 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; }

總結

以上是生活随笔為你收集整理的HDU 1729（石子）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。