Cutting Game POJ - 2311
给定一个有 \(n\times m\) 方格的纸片,两个人玩剪纸片游戏,每次可以沿着横向或者纵向笔直地剪一刀,谁先剪出 \(1\times 1\) 的小纸片谁就赢了.给出 \(n,m\) ,判断第一个剪的人能否获胜. (\(n,m \geq 2\) )
\(\operatorname{Solution}\)
第一次用 \(SG\) 函数做题.看了很多佬的博客都没太看懂,找到了一个写法跟我很相似的文章
如果不太了解 \(SG\) 函数可以静下心来看一下这篇文章
首先一定要保证减完后的纸条长和宽都要 \(\geq2\) .否则对手可以直接剪出了来 \(1\times 1\) 的.那么剪一下,一定有长或者宽的长度会 \(-1\) ,因此剪之前如果长和宽是 \(2\times 2,2\times 3,3\times 2\) 都是无解的( \(3\times 2\) 减完后一定会有为 \(1\) 的边,这点很容易漏).应该直接把他们的 \(SG\) 函数设为 \(0\) ,而不应该把长或宽为 \(1\) 的情况设为 \(1\) . \(SG\) 函数的定义是不能往下走的设为 \(0\) ,因此一定要保证你设的终态是 $SG = 0 $ 的状态 而不能是其他的!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
//#define endl '\n'
#define pb push_back
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10;
int vis[210][210];
int res[210][210];
int debug = 0;
int sg(int x,int y)
{
if(vis[x][y])return res[x][y];
int t = 0 ;if(debug)
cout<<x<<" "<<y<<"::"<<endl;
vis[x][y] = 1 ;
int h[210]={0};
for(int i= 2;i<=x-i;i++)
{
h[(sg(i,y))^(sg(x-i,y))] = 1;
}
for(int j = 2;j<=y-j;j++)
{
h[(sg(x,j))^(sg(x,y-j))] = 1;
}
for(t = 0 ;h[t];t++);
res[x][y] = t;
if(debug)
cout<<x<<" "<<y<<" "<<t<<endl;
return t;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
vis[2][2] = vis[3][2] = vis[2][3] = 1;
res[2][2] = res[3][2] = res[2][3] = 0;
int x,y;
while(cin>>x>>y)
{
if(sg(x,y))
{
cout<<"WIN"<<endl;
}
else cout<<"LOSE"<<endl;
}
return 0;
}
1669：S-Nim
两个人玩游戏，规则是有 \(n\) 堆石子，分别有 \(a_1,a_2,\cdots ,a_n\) 颗石头，每次从一堆石子中取一些石子，但是可取的石子数是规定了的，必须是 \({s_1,s_2,\cdots,s_k}\) 中的一个，谁无法操作就输。
\(\operatorname{Solution}\)
本题的教训是大数组或者 \(vector\) 一定不要作为递归的局部变量,否则释放会消耗大量时间.这题刚做的时候用的 \(dfs\) 然后把记录子状态 \(SG\) 值的数组开大了(开到了 \(1e5\) ),估计释放所用的时间是 \(O(n)\) 的,一直 \(TLE\) ,看标程明明是差不多的做法.最后把数组改小后直接 \(19ms\) . \(SG\) 的范围应该是 \(0\sim n\) .与石子数量无关,与子态的个数有关,而本题中子态的个数与 \(k\) 紧密相连,因此只需要开 \(k\) 的范围就够了.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<vector>
#define endl '\n'
#define pb push_back
using namespace std;
typedef pair<int, int> PII;
const int N = 2e4 + 10;
int k;
int f[N];
int m;
int n;
int sg[N];
vector<int> a(110);
int mex(vector<int> &h)
{
int i;
for (i = 0; h[i]; i++);
return i;
}
int dfs(int x)
{
if(x<0)return 0;
if(sg[x]!=-1)return sg[x];
sg[x] = 0;
int ok = 0;
vector<int>h(101,0);
for(int j = 1;j<=k&&f[j]<=x;j++)
{
h[dfs(x-f[j])] = 1;
}
sg[x] = mex(h);
return sg[x];
}
void solve()
{
for (int i = 1; i <= k; i++)
{
cin >> f[i];
}
sort(f+1,f+k+1);
cin >> m;
memset(sg,-1,sizeof sg);
while (m--)
{
cin >> n;
int res = 0 ;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
res^=dfs(a[i]);
}
if(res)
{
cout<<"W";
}
else cout<<"L";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while (cin >> k&&k)
{
solve();
}
return 0;
}