当前位置 : 主页 > 编程语言 > java >

博弈专题·sg函数

来源:互联网 收集:自由互联 发布时间:2022-10-26
​​UVA 12293 Box Game​​ ​​UVA 11892 ENimEN​​ ​​LA 3668 A Funny Game​​ ​​LA 5760 Alice and Bob​​ ​​UVA 10561 Treblecross​​ ​​UVA 12163 Addition-Subtraction Game​​ UVA 12293 Box Game 一个盒子


  • ​​UVA 12293 Box Game​​
  • ​​UVA 11892 ENimEN​​
  • ​​LA 3668 A Funny Game​​
  • ​​LA 5760 Alice and Bob​​
  • ​​UVA 10561 Treblecross​​
  • ​​UVA 12163 Addition-Subtraction Game​​


UVA 12293 Box Game

一个盒子n个球,另一个盒子有一个球,每次清空球较少的盒子,然后从较多的那个分一些球到空盒中,操作后2堆至少余1个球
甲乙轮流操作,无法操作者输,问赢家.

计算sg函数,发现只有n=1,3,7,15,…2^n-1时,后手胜

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iomanip>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
int f[MAXN][MAXN];
int dfs(int a,int b)
{
if (f[a][b]>=0) return f[a][b];
// if a>b
bool vis[MAXN]={0};
For(i,a-1) {
if (i<a-i) continue;
vis[dfs(i,a-i)]=1;
}
int p=0;
while (vis[p]) ++p;
return f[a][b]=p;

}
int main()
{
// freopen("uva12293.in","r",stdin);
// freopen(".out","w",stdout);

// memset(f,-1,sizeof(f));
// For(i,100)
// {
// if (!dfs(i,1)) cout<<i<<':'<<dfs(i,1)<<' ';
// }
int n;
char s[]="Alice",s2[]="Bob";
while (cin>>n && n) {

++n;
while (n%2==0) n/=2;
printf("%s\n",n==1?s2:s);
}

return 0;
}

UVA 11892 ENimEN

N堆石子,
操作:取走一堆中至少1个石子,如果上次对手没取整堆,则当前只能继续在这堆石子取.
甲乙轮流操作,无法操作者输,问谁赢

显然局面无环,存在sg函数
如果存在一堆至少为2的,可以通过某种办法取走整堆,使自己在剩余游戏中获得先手 or 后手,其中至少有一个必胜态。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iomanip>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}

int main()
{
// freopen("uva11892.in","r",stdin);
// freopen(".out","w",stdout);

int T;cin>>T;
while(T--) {
int n=read();
bool flag=0;
For(i,n) {
int p=read();
if (p>1) flag=1;
}

if (flag|| (n&1) ) puts("poopi");
else puts("piloop");

}


return 0;
}

LA 3668 A Funny Game

n堆石子,编号0..n−1(n<=23), 第i堆有si个石子
操作:每次选3堆i,j,k,i<j≤k,其中第i堆石子非空,令第i堆石子-1,j,k两堆石子各+1,
甲乙轮流操作,无法操作者输,问谁赢

把组合游戏拆成,(第i个位置上有1个石子,其余与题目描述相同),的∑si个局面,每次在其中一个游戏中走一步。
由SG定理,答案为这些局面sg函数异或和,故答案只和si奇偶性有关
所以可以O(2^n)大暴力

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<vector>
#include<cctype>
#include<ctime>
#include<iomanip>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define MAXN (1000)
int a[MAXN];

int sg[10000000];

int calc(int x) {

if (sg[x]>=0) return sg[x];
vector<int> b;
for(int i=1;i<=x;i<<=1) {
if (i&x) {

for(int j=i>>1;;j>>=1)
{
for(int k=j;;k>>=1) {

b.pb(calc(x^i^j)^calc(x^i^k));

if (!k) break;
}
if (!j) break;
}

}
}

sort(b.begin(),b.end());
int p=0,m=b.size();

Rep(i,m) {
if (b[i]>p) break;
if (b[i]==p) p++;
}
return sg[x]=p;

}
int n,kcase=0;
void work(int p) {
for(int i=1;i<=n;i++) if (a[i]) {
for(int j=i+1;j<=n+1;j++) {
for(int k=j;k<=n+1;k++) {

if ((p^sg[1<<n-i]^(j<=n ? sg[1<<n-j] : 0) ^ (k<=n ? sg[1<<n-k] : 0 ) )== 0){
printf("%d %d %d\n",i-1,j-1,k-1);
return ;
}
}
}
}

}

int main()
{
// freopen("la3668.in","r",stdin);
// freopen(".out","w",stdout);
memset(sg,-1,sizeof(sg));
sg[0]=0;
for(int i=1;i<=1<<23;i<<=1) {
calc(i);
}


while (n=read()) {
++kcase;


For(i,n) {
a[i]=read();
}
n--;

int p=0;
for(int i=n,j=1;i;i--,j<<=1) {
if (a[i]&1) p^=sg[j];
}

if (!p||!n) {
printf("Game %d: -1 -1 -1\n",kcase);
continue;
}
printf("Game %d: ",kcase);

work(p);



}

return 0;
}

LA 5760 Alice and Bob

n个正数,n<=50
每次操作可以将一个数-1(如果这个数为0便删除),或者把两个数合并(用a+b替换a,b)。
甲乙轮流操作,无法操作者输,问谁赢

如果不考虑‘删除1’的情况,操作数固定
如果所有数都≥2 ,操作数固定,因为赢家总有办法让对手无法‘删除1’
那么不妨猜想:
一个状态的输赢情况只和 ①1的个数 ②非1的数的总操作数 有关
那么可以暴搜

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<iomanip>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
#define
int n,a[MAXN];

int sg[MAXN][MAXM];

bool g(int i,int j) {
if (sg[i][j]>=0) return sg[i][j];
if (j==1) return g(i+1,0);
sg[i][j]=0;
if (i>=1&&!g(i-1,j)) sg[i][j]=1;
if (j>=1&&!g(i,j-1)) sg[i][j]=1;
if (j) {
if (i>=2&&!g(i-2,j+3)) sg[i][j]=1;
} else
if (i>=2&&!g(i-2,j+2)) sg[i][j]=1;
if (i>=1&&j&&!g(i-1,j+1)) sg[i][j]=1;

return sg[i][j];
}

int main()
{
// freopen("la5760.in","r",stdin);
// freopen(".out","w",stdout);

memset(sg,-1,sizeof(sg));

int T;cin>>T;
For(kcase,T) {
printf("Case #%d: ",kcase);

int I=0,J=0;

n=read();
For(i,n) {
a[i]=read();
if (a[i]==1) ++I;
else J+=a[i]+1;
}
if (J) --J;

if (g(I,J)) puts("Alice"); else puts("Bob");




}

return 0;
}

UVA 10561 Treblecross

n个格子排成1行,其中一些格子有X,没有连续3个X
操作:将一个没有X的格子改为有X的
甲乙轮流操作,操作后格子有连续3个X就赢,问谁赢

考虑排除特殊情况
原目标等价 : 操作后连续3个格子有2个X算输
于是我能执行的操作变为:在若干‘无X’片段中选一个填X

可以把长度为k的无X片段的sg函数算出来,用SG定理合并

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<vector>
#include<iomanip>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}

#define MAXN (200+10)
int n;
char s[MAXN];

int sg[MAXN];

int calc(int x) {
if (sg[x]>=0) return sg[x];

bool b[MAXN]={0};

for(int i=1;i<=x;i++) {
int l=i-3,r=x-i-2;
b[max(calc(l),0)^max(calc(r),0)]=1;
}
int p=0;
while (b[p]) ++p;
return sg[x]=p;
}

int is_win(){

int p=(s[1]=='X') + (s[2] == 'X' );
bool flag=0;
Fork(i,3,n) {
p+= (s[i]=='X') - (s[i-3] == 'X');
if (p==3) return 0;
if (p==2) flag=1;
}

if (flag) return 1;

vector<int> a;
For(i,n) if (s[i]=='X') a.pb(i);

int m=a.size();
p=0;

if (m==1) {
if (a[0]>3) p^=sg[a[0]-3];
if (n-a[0]-2>0) p^=sg[n-a[0]-2];
return p;
}

if (a[0]>3) p^=sg[a[0]-3];
if (n-a[m-1]-2>0) p^=sg[n-a[m-1]-2];

For(i,m-1) {
int len=a[i]-a[i-1];
if (len-5>0) p^=sg[len-5];
}
return p;

}
char s1[]="WINNING",s2[]="LOSING";
int main()
{
// freopen("uva10561.in","r",stdin) ;
// freopen(".out","w",stdout);

memset(sg,-1,sizeof(sg));
sg[0]=0;
sg[1]=sg[2]=sg[3]=1;

For(i,200) calc(i);

int T;cin>>T;
while(T--) {
s[0]=0;
scanf("%s",s+1);
n=strlen(s+1);

vector<int> ans;
For(i,n) {
if (s[i]=='.') {
s[i]='X';
if (!is_win()) ans.pb(i);
s[i]='.';

}
}

int m=ans.size();
if (m) {
puts(s1);
cout<<ans[0];
For(i,m-1) printf(" %d",ans[i]);
}else puts(s2);
printf("\n");
}

return 0;
}

UVA 12163 Addition-Subtraction Game

题意:有一张DAG,点数为n<=100,每个点出度小于15,无自环,
每个点上有点权ki,
有R局,每局每个点上会有权值vi,甲乙两人轮流操作,
每次选一个vi>0且出度>0的点,将其vi的值-1,然后对于其出边指向的点,选ki个点(允许重复选),把这些点的vi值+1。
无法操作者输

由于没注意到加粗部分贡献wa

其实还是sg函数。

#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
#define
vi Edge[MAXN];
int n,m,R,k[MAXN];
ll sg[MAXN];
ll SG(int x) {
if (sg[x]>-1) return sg[x];
bool vis[1<<16]={0};

int m = Edge[x].size();
if (m==0) return sg[x]=0;
Rep(i,(1<<m)) {
int t=__builtin_popcountll(i);
if (t>k[x] || (t&1)!=(k[x]&1)) continue;
ll tmp=0;
Rep(j,m) {
if ((i&(1<<j))) {
tmp^=SG(Edge[x][j]);
}
}
vis[tmp]=1;
}

sg[x]=0;
while (vis[sg[x]]) ++sg[x];

return sg[x];
}
int main()
{
// freopen("uva12163.in","r",stdin);
// freopen(".out","w",stdout);

int T=read();
For(kcase,T) {
printf("Game\#%d:\n",kcase);
memset(sg,-1,sizeof(sg));
Rep(i,n) Edge[i].clear();
cin>>n>>m;
Rep(i,m) {
int u=read(),v=read();
Edge[u].pb(v);
}
Rep(i,n) k[i]=read();
Rep(i,n) sg[i]=SG(i);
R=read();
For(i,R) {

ll ans=0;
Rep(j,n) {
int p=read();
if (p&1) ans^=SG(j);
}
printf("Round\#%d: ",i);
if (ans==0) puts("LOSING");
else puts("WINNING");
}
puts("");

}


return 0;
}


上一篇:iOS CFBundleShortVersionString
下一篇:没有了
网友评论