CF 256C Furlo and Rublo and Game
暴力的求SG函数会超时,正解是先处理出10^6以内的SG值,对于更大的,开根号之后计算出。
小数据观察可以发现sg函数值成段出现,而且增长速度很快,因此可以计算出来每一段的范围,只需打表即可。
Nim游戏:
Nim和:L.Bouton给出了一个定理,状态(X1, X2, ..., Xn)为必败态当且仅当X1 xor X2 xor .... xor Xn = 0,xor是二进制的按位异或操作。
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; ll x, a[] = {3, 15, 81, 6723, 50625, 2562991875LL}; int sg[] = {0, 1, 2, 0, 3, 1, 2}, n, ans = 0; int main() { cin >> n; while (n--) { cin >> x; ans ^= sg[lower_bound(a, a+6, x)-a]; } cout << (ans ? "Furlo" : "Rublo") << endl; return 0; }
补充:软件开发 , C++ ,