武理校赛J题搬书比赛（反nim博弈）

编程入门行业动态更新时间:2024-10-18 13:23:38

武理校赛J题搬书比赛（反nim博弈）

武理校赛J题

搬书比赛（反nim博弈）

牛客链接

题意：

ljw 先手；

最后没有书搬的人获胜；

一次可以向下搬任意本书，一次搬两层，第二层可直接搬到第一层；

每回合不能不搬；

思路：

注意到一次只能向下搬两层，且二楼和三楼都能直接搬到一楼，因此可以将 1 楼看作阶梯博弈中的地面（第 0 层），将 2，3 楼合并为阶梯博弈中的 1 楼，以此类推。

再将阶梯博弈转化为奇数台阶的反nim博弈

反nim博弈结论：

各堆石子数目异或和不为0，且至少有一堆石子数大于1，则先手必胜；

各堆石子数目异或和等于0，且所有石子堆数均为1，则先手必胜；

细节：

注意第 1 层实际上是阶梯博弈的第 0 层，所以奇数台阶的判断为

if (i % 4 == 2 || i % 4 == 3) -> 奇数台阶

完整代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef double dd;
typedef pair<int, int> pii;
typedef pair<dd, dd> pdd;
const int MAXN = 200010;
const int inf = 1e9 + 7;
const int MAXM = 1500010;int a[MAXN];int main()
{int n;scanf("%d", &n);for (int i = 1;i <= n;i++) scanf("%d", &a[i]);int ans = 0;for (int i = 2;i <= n;i++){if (i % 4 == 2 || i % 4 == 3)ans ^= a[i];}if (ans == 0){for (int i = 2;i <= n;i++){if (i % 4 == 2 || i % 4 == 3)if (a[i] > 1){printf("wfy");return 0;}}printf("ljw");}else{for (int i = 2;i <= n;i++){if (i % 4 == 2 || i % 4 == 3)if (a[i] > 1){printf("ljw");return 0;}}printf("wfy");}
}