HDU6869 | 2020杭电多校(第九场)1003 Smile and Stone

传送门

题意

江湖人称 “扩展威佐夫博弈”,反正我是第一次听说,也没有找到公式,所以在比赛的时候就没过,恨!

首先来看一下普通的威佐夫博弈(Wythoff’s game),游戏规则是:有两堆各若干个物品,两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品,规定每次至少取一个,至多不限,最后取光者胜利。

在本题上这就是 k = 0的情况,那么k != 0的时候怎么推柿子呢?

再来回顾一下,威佐夫博弈必败态的公式是怎么来的,这其实来自贝蒂定理(Betty Theorem),具体是啥呢,看看这个吧。

欢迎回来~,好了现在你已经知道了,公式其实来自

1a+1a+1=1
\frac{1}{a}+\frac{1}{a+1}=1

a1​+a+11​=1
解出这个方程就会得出

a=1+52
a=\frac{1+\sqrt5}{2}

a=21+5​​
那么对于威佐夫博弈必败态的公式即为

an=n1+52bn=an+n
a_{n}=n*\lfloor\frac{1+\sqrt5}{2} \rfloor \quad b_{n}=a_{n} + n

an​=n∗⌊21+5​​⌋bn​=an​+n

上面是大佬们推导的公式,现在该我来优雅的找规律了;

我们都知道威佐夫博弈是本题

k=0k=0

k=0的特殊情况,我们将

k=0k=0

k=0代入上述公式,于是我们就得到了

1a+1a+k+1=1
\frac{1}{a}+\frac{1}{a+k+1}=1

a1​+a+k+11​=1
这时候相当于解这个方程(我们先将

kk

k加一,显得比较优雅),然后再化简一下

a2+(k2)ak=0
a^2+(k-2)*a-k=0

a2+(k−2)∗a−k=0
我们来解这个方程,很容易就知道

A=1,B=k2,C=ka=B24ACB2A
A=1,B=k-2,C=-k\\
a=\frac{\sqrt{B^2-4*A*C}-B}{2*A}\\

A=1,B=k−2,C=−ka=2∗AB2−4∗A∗C​−B​
好的,我们类似得到必败态的公式为

an=nB24ACB2Abn=an+kn(kk)
a_{n}=n*\lfloor\frac{\sqrt{B^2-4*A*C}-B}{2*A}\rfloor\quad b_{n}=a_n+k*n\\(注意这里的k是题目中的k加一之后的值)

an​=n∗⌊2∗AB2−4∗A∗C​−B​⌋bn​=an​+k∗n(注意这里的k是题目中的k加一之后的值)
嗯优雅的找规律结束,打表验证一下是否符合;

打表对比结束,OK,Very 符合,接下来对于输入的a,b取较大值去二分它是在第几项,根据公式算出a,b较小值是否符合公式即可;

AC code(46ms 傲娇~)

/*******************************
* Coder : He Shuo. *
* Type : Original Work *
*******************************/
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<deque>
#include<stdlib.h>
#include<set>
#include<bitset>
#include<map>
#include<ctime>
#include<unordered_map>
using namespace std;
typedef long long ll;

namespace Fast_IO //orz laofu
{
const int MAXL((1 << 18) + 1);int iof, iotp;
char ioif[MAXL], *ioiS, *ioiT, ioof[MAXL],*iooS=ioof,*iooT=ioof+MAXL-1,ioc,iost[55];
inline char Getchar(){if(ioiS == ioiT){ioiS = ioif;ioiT = ioiS + fread(ioif,1,MAXL,stdin);return (ioiS == ioiT ? EOF : *ioiS++);}else return (*ioiS++);}
inline int read()
{
int x = 0;for(iof = 1,ioc = Getchar();(ioc < '0' || ioc > '9') && ioc != EOF;)iof = ioc == '-' ? -1 : 1,ioc = Getchar();
if(ioc == EOF)exit(0);
for(x = 0;ioc <= '9' && ioc >= '0';ioc = Getchar())x = (x << 3) + (x << 1) + (ioc ^ 48);
return x * iof;
}
inline long long read_ll()
{
long long x = 0;
for(iof = 1,ioc = Getchar();(ioc < '0' || ioc > '9') && ioc != EOF;)iof = ioc == '-' ? -1 : 1,ioc = Getchar();
if(ioc == EOF)exit(0);
for(x = 0;ioc <= '9' && ioc >= '0';ioc = Getchar())x = (x << 3) + (x << 1) + (ioc ^ 48);
return x * iof;
}
}
using namespace Fast_IO;

ll a,b,k;
ll check()///二分寻找较大值在第几项;
{
k = k + 1;///先加一,优雅~
ll A = 1,B = k - 2,C = -k;
ll res = B * B - 4 * A * C;///判别式;

ll l = 0,r = 1e8 + 10;
while(l <= r)
{
ll mid = (l + r) / 2;
ll ans = (mid * ((sqrt(res) - B) / 2) + k * mid);
if(b < ans)r = mid - 1;
else if(b > ans)l = mid + 1;
else return mid;
}
return -1;
}

int main()
{
int q;q = read();
while(q --)
{
a = read_ll();
b = read_ll();
k = read_ll();
if(a > b)swap(a,b);///用较大去跑二分;
ll n = check();///返回是第几项;
if(n == -1)printf("1\n");///不在数列中必赢;
else
{
if(b - a == n * k)printf("0\n");///符合公式必输;
else printf("1\n");///不符合必赢;
}
}
}

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

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

HDU6869 | 2020杭电多校(第九场)1003 Smile and Stone

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

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

评论抢沙发

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

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

支付宝扫一扫打赏

微信扫一扫打赏