2025年【Gym-101908 B】Marbles【SG函数】

大家好，我是讯享网，很高兴认识大家。

题意：

一个棋盘，棋盘上有 $n$ 个棋子，每个棋子有一个坐标 $(a, b)$ 。两个人轮流玩这个游戏，每一次可以任意选择一个棋子，向左移动 $x$ 格，向下移动 $x$ 格，向左下移动 $x$ 格， $x$ 任意但不能移出棋盘边界。谁先将一个棋子移动到 $(0, 0)$ 谁获胜，每一个棋子独立。 $(1\leq n\leq 1000,1\leq a,b\leq 100)$

思路：

这个题与之前做过的 $S G$ 函数的问题有一些不同，主要区别在于之前的 $S G$ 函数问题求的是哪一方不能再行动则为输，现在则是谁先移动到 $(0, 0)$ 则为输。

因此必须进行转换方可求解。比赛时没有考虑到转换的问题，一直纠结的是必败态与必胜态的问题，最终错失 AC 机会。

所以我们需要对这个题进行转换，其实可以发现每个人在移动棋子的时候，最后一定会移动到 $(1, 2)$ 或 $(2, 1)$ 。因为 $(1, 2)$ 和 $(2, 1)$ 是最接近 $(0, 0)$ 的必败态，即无论怎么移， $(1, 2)$ 或 $(2, 1)$ 只要再移动一步，另一方就能取胜。

因此其实这道题， $(1, 2)$ 和 $(2, 1)$ 才是这个游戏的终结点。每个人将棋子移动到这两个点处便不能再进行移动，第一个不能行动的人则输。由此我们就实现了问题的转化。

讯享网

还有一些细节就是， $S G$ 函数求解枚举转移方向时，不能将棋子移动到必胜态，否则对方就会直接取胜。还有就是判断一下初始点中有无 $(x, x)$ 这样的点即可完成此题。

总结：

本题非常巧妙地考察了 $S G$ 函数的应用，重点在于多个子游戏中，达到必败的关键是最后一个不能移动的人。

但此题求取的却是第一个完成的人，因此一定会存在一个点，使得所有的状态达到这个点，一旦移动则另一方胜利。而这个点就是原来 $S G$ 函数问题中的末状态点。

所以想要在比赛中 $A$ 掉此题，关键的思维点在于类比，将现有问题类比成原有模型，便能高效求解。而不是进行各种没有根据的猜测，妄图创造一种新算法去进行求解。关键在类比！

代码：

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define rep(i,a,b) for(int i = a; i <= b; i++) #define LOG1(x1,x2) cout << x1 << ": " << x2 << endl; #define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl; #define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl; typedef long long ll; typedef double db; const int N = 100+10; const db EPS = 1e-9; using namespace std; int sg[N][N],n; int solve(int x,int y) { 
    if(sg[x][y] != -1) return sg[x][y]; int vis[150]; memset(vis,0,sizeof vis); int tp = 0, ct = 0; rep(i,1,x){ 
    if(x-i != y && x-i != 0 && y != 0){ 
    tp = solve(x-i,y); vis[tp] = 1; } } rep(i,1,y){ 
    if(x != y-i && x != 0 && y-i != 0){ 
    tp = solve(x,y-i); vis[tp] = 1; } } rep(i,1,min(x,y)){ 
    if(x-i != y-i && x-i != 0 && y-i != 0){ 
    tp = solve(x-i,y-i); vis[tp] = 1; } } rep(i,0,150) if(vis[i] == 0) return sg[x][y] = i; } int main() { 
    memset(sg,-1,sizeof sg); int jud = 0; scanf("%d",&n); int ans = 0; rep(i,1,n){ 
    int xx,yy; scanf("%d%d",&xx,&yy); ans ^= solve(xx,yy); if(xx == yy) jud = 1; } if(jud) printf("Y\n"); else if(ans != 0) printf("Y\n"); else printf("N\n"); return 0; }

讯享网

2025年【Gym-101908 B】Marbles【SG函数】

题意：

思路：

总结：

代码：

相关推荐