「UVA12293」 Box Game

题目链接

$Solution$

这道题第一眼看样例，猜了个结论偶数$Alice$赢，否则$Bob$赢，打了一发，交了上去果不其然的$wa$了,第二次猜$2$的幂次方$Alice$赢，否则$Bob$赢,这次没有再交上去了，打了个表发现并不对。于是开始了推结论。

我们现在根据样例已经知道了$3$为先手输,于是能变成$3$的是那些呢?很显然可以发现时$4 $~$ 2*3-1$,所以下一个先手输的为$7$,以此类推。如果你不想找规律了你可以直接见$Code1$,如果想推推公式可以继续看下去，我们观察发现$1,3,7,31$都为$2^k-1$于是我们现在就是要证明这个结论正确

我们发现下一个输的为上一个输的$*2+1$于是带入式子:

\[(2^k-1)*2+1=2^{k+1}+1
\]

依旧满足那个式子，所以结论成立，代码见$Code2$

$Code1$

#include<bits/stdc++.h>

using namespace std;

int n;

map<int,int> f;

int main(){

	for(int i=1;i<=1e9;i=i*2+1)

		f[i]=1;

	while(scanf("%d",&n)!=EOF){

		if(!n) return 0;

		if(f[n]==1) puts("Bob");

		else puts("Alice");

	}

}

$Code2$

#include<bits/stdc++.h>

using namespace std;

int n;

int main(){

	while(scanf("%d",&n)!=EOF){

		if(!n) return 0;

		if(floor(log(n+1)/log(2))==log(n+1)/log(2))

			puts("Bob");

		else puts("Alice");

	}

}

巴特西

「UVA12293」 Box Game

题目链接

\(Solution\)

\(Code1\)

\(Code2\)

最新文章

热门文章