hdu 4672 Present Day, Present Time 博弈论

时间:2024-09-25 11:36:33

看了解题报告才知道怎么做!!

题意:有 N 堆石子和 M 个石子回收站,每回合操作的人可以选择一堆石子,从中拿出一些 放到石子回收站里(可以放进多个回收站,每个回收站可以使用无数次),但每个石子回收站每次 只能接收特定数量的石子。不能操作的输。如果有人操作完之后,有任意一堆石子无法完全回收, 那么他直接输。

一个显然的结论是,每个游戏的 SG 值就是用 M 个回收站,完全回收这堆石子可行的最大 操作次数。由于最大的 Bi 比较小,立方暴力背包即可(比较显然的是,maxBi2 以上的周期是 minBi)。

而最大也就是10000,所以可以直接暴力求解sg值,找到最大操作次数。

ps:看到有人竟然仅仅用了50+B的代码就A了,真乃牛人啊,膜拜……

代码如下:

 #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#define I(x) scanf("%d",&x)
using namespace std;
int sg[],a[];
char x[],y[];
int main(){
int n,m,i,j,MIN,b,t,ans;
while(scanf("%d%d%s%s",&n,&m,x,y)!=EOF){
memset(sg,-,sizeof(sg));
sg[]=;MIN=1e9;
bool flag=;
for(i=;i<n;i++) I(a[i]);
for(i=;i<m;i++){
I(b);
MIN=min(MIN,b);
for(j=;j+b<=;j++)
if(sg[j]>=)
sg[j+b]=max(sg[b+j],sg[j]+);
}
ans=;
for(i=;i<n;i++){
t=a[i];
if(t<=){
if(sg[t]<) flag=;
else ans^=sg[t];
}
else{
t=(t-+MIN)%MIN+-MIN;
if(sg[t]<) flag=;
else ans^=sg[t]+(a[i]-t)/MIN;
}
}
if(!flag&&ans) puts(x);
else puts(y);
}
return ;
}