【杭电多校9:拓展威佐夫博弈(如何优雅地找规律)】HDU6869:Slime and Stones

HDU6869:Slime and Stones

【难度】

5/105/10

5/10
杭电就喜欢出拓展题……

【题意】

有两堆石子,第一堆有

aa

a 个石头,第二堆有

bb

b 个石头。
你有两种操作:
操作一:从某堆拿任意个石子。
操作二:从第一堆拿

xx

x 个,从第二堆拿

yy

y 个,要求

xyk|x-y|\le k

∣x−y∣≤k,其中

kk

k是给定常数。

每个人都是最优策略,让你求是否先手必胜(1)或先手必败(2)。

【数据范围】

1T105样例组数 1\le T\le 10^5

样例组数1≤T≤105

1a,b,k1081\le a,b,k\le 10^8

1≤a,b,k≤108

【样例输入】

4
1 2 0
2 4 0
1 2 1
2 6 1

【样例输出】

0
1
1
0

【思路】

(一)首先是一眼就能看出的规律

abk|a-b|\le k

∣a−b∣≤k,则直接先手必胜。

(i,j)(i,j)

(i,j)为必输状态,且

(a,b)(a,b)

(a,b)能转移到

(i,j)(i,j)

(i,j) ,则

(a,b)(a,b)

(a,b) 必胜,否则必输。

更正式的表达为:

SG[a,b]=mex(a,b)(i,j){SG[i,j]}
\color{red}SG[a,b]=\underset{(a,b)能转移到(i,j)}{mex}\Big\{ SG[i,j]\Big \}

SG[a,b]=(a,b)能转移到(i,j)mex​{SG[i,j]}

我们打一下表查看一下规律

【打表代码】

/*
_ __ __ _ _
| | \ \ / / | | (_)
| |__ _ _ \ V /__ _ _ __ | | ___ _
| '_ \| | | | \ // _` | '_ \| | / _ \ |
| |_) | |_| | | | (_| | | | | |___| __/ |
|_.__/ \__, | \_/\__,_|_| |_\_____/\___|_|
__/ |
|___/
*/
int dp[MAX][MAX][MAX];
int main()
{
for(int k=0;k<=5;++k){
show(k);
for(int i=1;i<=60;++i){
for(int j=1;j<=60;++j){
if(abs((i-j))<=k)cout << "+" << " ",dp[i][j][k] = 1;
else{
bool fd = false;
for(int p=1;!fd && p<=i;++p)
for(int q=1;!fd && q<=j;++q){
if(p==i && q==j)continue;
if(abs((i-p)-(j-q))<=k && dp[p][q][k]==0)fd=true;
}
for(int p=1;!fd && p<i;++p)if(dp[p][j][k]==0)fd=true;
for(int p=1;!fd && p<j;++p)if(dp[i][p][k]==0)fd=true;
if(fd)dp[i][j][k] = 1;
else dp[i][j][k] = 0;
if(fd)cout << "." << " ";
else cout << "X" << " ";
}
}
puts("");
}
puts("");
}
return 0;
}

以下为k=0与k=1时的表格,其中

mat[i][j]=Xmat[i][j]=‘X’

mat[i][j]=‘X’表示该点为必输态,否则为必胜态。
其中对角线状态额外用

+‘+’

‘+’号做了对照标记。
【杭电多校9:拓展威佐夫博弈(如何优雅地找规律)】HDU6869:Slime and Stones
【杭电多校9:拓展威佐夫博弈(如何优雅地找规律)】HDU6869:Slime and Stones
发现,对于不同的

kk

k,必输态都很少,大致呈直线分布。但是之间的间隔很奇怪。

我们枚举上三角矩阵不同的

XX

X之间的间隔(纵坐标间隔)并丢到OEIS中去,可以发现规律

k=0,dis[]={2,5,7,10,13,15,18}k=1,dis[]={3,6,10,13,17,20,23}k=2,dis[]={4,8,12,17,21,25,30,34}k=3,dis[]={5,10,15,20,26,31,36,41,47}
k=0,dis[]=\{2,5,7,10,13,15,18\cdots\}\\
k=1,dis[]=\{3,6,10,13,17,20,23\cdots\}\\
k=2,dis[]=\{4,8,12,17,21,25,30,34\cdots\}\\
k=3,dis[]=\{5,10,15,20,26,31,36,41,47\cdots\}\\

k=0,dis[]={2,5,7,10,13,15,18⋯}k=1,dis[]={3,6,10,13,17,20,23⋯}k=2,dis[]={4,8,12,17,21,25,30,34⋯}k=3,dis[]={5,10,15,20,26,31,36,41,47⋯}

然后OEIS里面的查找结果为:
【注意:需要通分成分母为2,注意根号内数值需要递增】

k=0,B[n]=floor(n×3+52)k=1,B[n]=floor(n×4+82)k=2,B[n]=floor(n×5+132)k=3,B[n]=floor(n×6+202)
\color{green}k=0,B[n]=floor(n\times \frac{3+\sqrt5}{2})\\
k=1,B[n]=floor(n\times \frac{4+\sqrt8}{2})\\
k=2,B[n]=floor(n\times \frac{5+\sqrt{13}}{2})\\
k=3,B[n]=floor(n\times \frac{6+\sqrt{20}}{2})\\
\vdots

k=0,B[n]=floor(n×23+5​​)k=1,B[n]=floor(n×24+8​​)k=2,B[n]=floor(n×25+13​​)k=3,B[n]=floor(n×26+20​​)⋮
可以看到,左侧的数字

3,4,5,63,4,5,6\cdots

3,4,5,6⋯依次递增。右侧数字的规律?再套到OEIS中!
(若找不到可以多找几个k)

【杭电多校9:拓展威佐夫博弈(如何优雅地找规律)】HDU6869:Slime and Stones
我们是从第二项开始的,那么稍微替换一下

nn

n:

b(n)=(n+1)2+1=n2+2n+5
b(n) =\sqrt{(n+1)^2+1}=\sqrt{n^2+2n+5}

b(n)=(n+1)2+1​=n2+2n+5

那么第

nn

n 个必败态的纵坐标我们就知道了,为:

B[n]=nk+3+k2+2k+52
B[n]=\Big\lfloor n\frac{k+3+\sqrt{k^2+2k+5}}{2}\Big\rfloor

B[n]=⌊n2k+3+k2+2k+5​​⌋

然后再结合威佐夫博弈的一些性质(找来的):

【贝亚蒂定理:Beatty’s theorem】
贝亚蒂定理:百度百科

p,pp1
\color{red}奇异局势满足(p,\frac{p}{p-1})的模式,即可反推横坐标\\ \ \\
\color{green}(奇异局势指的是必败态的点对)

奇异局势满足(p,p−1p​)的模式,即可反推横坐标(奇异局势指的是必败态的点对)
【威佐夫博弈:Wythoff’s game】
威佐夫博弈:百度百科

(百度百科这里是

k=0k=0

k=0的特殊情况、、)

k=0(p,p+n)(p,p+n+nk)
\color{red}当k=0时,奇异局势满足(p,p+n)\\
我们马后炮一下得知:奇异局势满足(p,p+n+nk)

当k=0时,奇异局势满足(p,p+n)我们马后炮一下得知:奇异局势满足(p,p+n+nk)
然后得出奇异局势标为:

A[n]=nk+1+k2+2k+52B[n]=nk+3+k2+2k+52
\color{red}A[n]=\Big\lfloor n\frac{-k+1+\sqrt{k^2+2k+5}}{2}\Big\rfloor\\ \ \\
B[n]=\Big\lfloor n\frac{k+3+\sqrt{k^2+2k+5}}{2}\Big\rfloor

A[n]=⌊n2−k+1+k2+2k+5​​⌋B[n]=⌊n2k+3+k2+2k+5​​⌋

然后我们二分查找对应的

nn

n,再查看是否满足这两个点对公式即可。

【注:】

k=0k=0

k=0时,即为普通的威佐夫博弈,在HDU有原题。

【核心代码】

时间复杂度:

O(T×log2Limit)O(T\times \log_2 Limit)

O(T×log2​Limit)
其中上界

LimitLimit

Limit为

10810^8

108
Time(Ms):62

/*
_ __ __ _ _
| | \ \ / / | | (_)
| |__ _ _ \ V /__ _ _ __ | | ___ _
| '_ \| | | | \ // _` | '_ \| | / _ \ |
| |_) | |_| | | | (_| | | | | |___| __/ |
|_.__/ \__, | \_/\__,_|_| |_\_____/\___|_|
__/ |
|___/
*/
int main()
{
int T;
T = read();
while(T--){
int a,b,t;
a = read();
b = read();
t = read();
double k = (double)t;
if(a > b)swap(a,b);
double XA = (1.0-k+sqrt(5.0+2*k+k*k))/2;
double XB = (3.0+k+sqrt(5.0+2*k+k*k))/2;
int l = 0;
int r = 100000000;
while(l < r){
int mid = l + r >> 1;
if(floor((double)mid * XA) > a)r = mid - 1;
else if(floor((double)mid * XA) < a)l = mid + 1;
else {
l = mid;
break;
}
}
if(floor((double)l * XA) == a && floor((double)l * XB) == b)printf("0\n");
else printf("1\n");
}
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【杭电多校9:拓展威佐夫博弈(如何优雅地找规律)】HDU6869:Slime and Stones

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【杭电多校9:拓展威佐夫博弈(如何优雅地找规律)】HDU6869:Slime and Stones
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏