模拟赛题讲解[27]

来自 s_r_f 2023-08-03 noi.ac #3195

题目描述

小 A 正在玩一种取石子游戏：开始时有一堆石子，数量是 $n$ 个。小 A 和他的对手轮流行动。小 A 先手。

每轮行动中，如果当前石子数量为 $n$，那么当前行动的人可以选择取出 $[1,\lfloor \frac{n+1}{2} \rfloor]$ 之间数量的石子。

取走最后一个石子的人获胜。

小 A 和他的对手一共玩了 $T$ 局游戏，假定他们都足够聪明（始终执行最优策略），判断小 A 能否获胜。

输入格式：

第一行，一个整数 $T$，表示游戏局数。

接下来 $T$ 行，每行一个正整数 $n$

输出格式：

输出 $T$ 行。

每一行输出字符串 “win” 或 “lose” (不包含引号)，表示小 A 的胜负情况。

输入样例1：

输出样例1：

win
lose
win
win

样例解释：

$n=1:$ 小 A 直接取走唯一的石子。

$n=2:$ 小 A 没有选择，只能取走 $1$ 个石子，然后对手取走剩下那个，小 A 输掉游戏。

$n=3:$ 小 A 取走 $1$ 个石子，此时小 A 的对手面对一个必败局面。

$n = 4:$ 小 A 取走 $2$ 个石子，此时小 A 的对手面对一个必败局面。

数据范围：

$1\le T \leq 10^5,~1\le n \leq 10^{16}$

题解：

这题常规做法是打个表找规律，发现当且仅当 $x=2^k - 2$ 时必输。

证明也很简单，因为下一个 $0$ 恰好取不到上一个 $0$ 的位置。

时间复杂度 $\mathcal{O}(Q\log M)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int Data[105] = {-1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992};
void solve()
{
    int n; cin >> n;
    if(*lower_bound(Data + 1, Data + 1 + 54, n + 2) == n + 2) cout << "lose\n"; else cout << "win\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}