「UVA12293」 Box Game

曾经终败给现在 2023-08-17 17:24 124阅读 0赞

### 题目链接 ###

[戳我][Link 1]

### \\(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"); } }

转载于:https://www.cnblogs.com/hbxblog/p/11426843.html

[Link 1]: https://www.luogu.org/problem/UVA12293

发表评论取消回复

表情：

评论列表（有 0 条评论，124人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVa 10891（记忆化搜索，递推）Game of Sum

例题 28 Sum 游戏（ Game of Sum, UVa 10891 ）有一个长度为 n 的整数序列，两个游戏者 A 和 B 轮流取数， A 先取。每次玩家

古城微笑少年丶/ 2024年02月17日 23:21/ 0 赞/ 80 阅读

相关盒子Box UVA1587

1. \include<cstdio> 2. \include<set> 3. \include<string.h> 4. using namespace std; 5

刺骨的言语ヽ痛彻心扉/ 2024年02月17日 18:44/ 0 赞/ 85 阅读

相关「UVA12293」 Box Game

题目链接 [戳我][Link 1] \\(Solution\\) 这道题第一眼看样例，猜了个结论偶数\\(Alice\\)赢，否则\\(Bob\\)赢，打了一发，

曾经终败给现在/ 2023年08月17日 17:24/ 0 赞/ 125 阅读

相关 UVA1045 The Great Wall Game

题目链接：[UVA1045 The Great Wall Game][] 题目大意：在一个n\n的棋盘上有n个棋子，要求通过移动棋子使棋子的排布满足以下情况之一：呈横行排列

约定不等于承诺〃/ 2023年08月17日 15:35/ 0 赞/ 128 阅读

相关 UVA 10843 Anne's game (Cayley定理)

题意：求n个点，可以连接出多少种不同的生成树 Cayley定理在组合数学上的应用以下从百度百科摘一段：过n个有标志顶点的树的数目等于n^(n-2)。定理的

Dear 丶/ 2022年08月27日 14:47/ 0 赞/ 141 阅读

相关 UVA10843——Anne\'s game

Lily: “Chantarelle was part of my exotic phase.” Buffy: “It’s nice. It’s a mushroom.”

男娘i/ 2022年08月09日 13:46/ 0 赞/ 18 阅读

相关 uva 1610——Party Games

题目链接：[http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=51171][http_acm.h

逃离我推掉我的手/ 2022年08月09日 13:45/ 0 赞/ 185 阅读

相关 UVA 1204 Fun Game 状态压缩圆圈的处理

题意：一群小孩(至少两个)围成一圈做游戏。每一轮从某个小孩开始往他左边或者右边传手帕。一个小孩拿到手帕后在手帕上写上自己的性别，男孩写B,女孩写G，然后按照相同的方向传递给下

怼烎@/ 2021年12月15日 06:13/ 0 赞/ 248 阅读

相关 UVa1587--Box--盒子（自认为代码很好理解）

> 题意就是判断6个面能否组成一个长方体做这道题的时候，想着，老子一定要用自己的方法，如果AC了，我一定要发题解！真的太不容易了。一个晚上的时间终于把这道题给AC了。

悠悠/ 2021年12月14日 07:03/ 0 赞/ 217 阅读

相关 Uva 10891 Game of Sum （经典博弈区间DP）

题意：给定一个长度为n的整数序列，A和B轮流取数，A先取，一次只能从左端或者右端取任意数量个数，所有数取完后求A的得分减去B的得分，A,B都采取最优策略。分析：这题用

太过爱你忘了你带给我的痛/ 2021年12月14日 02:37/ 0 赞/ 206 阅读