公司网站怎么优化,中国制造网的网络营销方式,上海建定建设工程信息网,用html5的视频网站题意#xff1a;两个人玩游戏#xff0c;通过轮流填数字#xff08;0~9#xff09;#xff0c;若最终左右两边的和相等#xff0c;后手赢#xff0c;否则先手赢。起始有部分数字和空格。
官方题解#xff1a; 题解翻译#xff1a;
让我们把余额表示为左半部分数字和…题意两个人玩游戏通过轮流填数字0~9若最终左右两边的和相等后手赢否则先手赢。起始有部分数字和空格。
官方题解 题解翻译
让我们把余额表示为左半部分数字和右半部分数字和的差。也让我成为最小可能的余额如果我们用00的左半部替换所有的问号和99的右半部分中的所有问号都可以计算让RR成为最大可能的平衡。
当且仅当lr20lr20时第二个玩家获胜。我们就票子上剩下的问号做归纳证明吧。
如果所有的字符都是数字那么第二个玩家只有在票子满意的情况下才能获胜也就是当LR20LR20时。
好吧现在假设问号是偶数现在轮到第一个玩家了。每转一圈R-LR-L的值减小99并且可以将LL设置为从当前LL到L9L9的任意数字。如果lr0lr0那么第一个玩家可以使ll尽可能大并将其设置为l9l9。第二个玩家在回合中能做的最好的事情是将r r设置为r-9r-9保持l l不变lrlr的值将与前两回合相同。LR0LR0的情况也可作类似分析。在lr0lr0的情况下第二个玩家有一个对称的策略。
我的理解类似于巴什博弈考虑后手赢的情况其余情况则为先手赢。
此题要注意两个问题一要填的空格二:起始两边的和的大小
若只考虑后手赢的情况有两个阶段。一两边都有空格时先手为了让自己赢在和大的一边放9后手也只能在和小的这一边放9则两边和差sum空格差k都不变
二只有一边有空格且另一边的和较大因为不知先手放啥特殊放0或9故每一回合k/2保持放九个故只有k/2*9sum时后手才会赢。
Monocarp and Bicarp live in Berland, where every bus ticket consists of nn digits (nn is an even number). During the evening walk Monocarp and Bicarp found a ticket where some of the digits have been erased. The number of digits that have been erased is even.
Monocarp and Bicarp have decided to play a game with this ticket. Monocarp hates happy tickets, while Bicarp collects them. A ticket is considered happy if the sum of the first n2n2 digits of this ticket is equal to the sum of the last n2n2 digits.
Monocarp and Bicarp take turns (and Monocarp performs the first of them). During each turn, the current player must replace any erased digit with any digit from 00to 99. The game ends when there are no erased digits in the ticket.
If the ticket is happy after all erased digits are replaced with decimal digits, then Bicarp wins. Otherwise, Monocarp wins. You have to determine who will win if both players play optimally.
Input
The first line contains one even integer nn (2≤n≤2⋅105)(2≤n≤2⋅105) — the number of digits in the ticket.
The second line contains a string of nn digits and ? characters — the ticket which Monocarp and Bicarp have found. If the ii-th character is ?, then the ii-th digit is erased. Note that there may be leading zeroes. The number of ? characters is even.
Output
If Monocarp wins, print Monocarp (without quotes). Otherwise print Bicarp (without quotes).
Examples
Input
4
0523Output
BicarpInput
2
??Output
BicarpInput
8
?054??0?Output
BicarpInput
6
???00?Output
MonocarpNote
Since there is no question mark in the ticket in the first example, the winner is determined before the game even starts, and it is Bicarp.
In the second example, Bicarp also wins. After Monocarp chooses an erased digit and replaces it with a new one, Bicap can choose another position with an erased digit and replace it with the same digit, so the ticket is happy.
ac代码
#includestdio.h
#includeiostream
#includestring.h
#includealgorithm
using namespace std;
const int M2e510;
char s[M];
int main()
{int n;while(~scanf(%d,n)){int x0,y0,z0,a0,b0,c0;scanf(%s,s1);for(int i1; in/2; i)if(s[i]?)x;elseas[i]-0;for(int in/21; in; i)if(s[i]?)y;elsebs[i]-0;cb-a;zx-y;if(z%2)printf(Monocarp\n);else{z1;//因为不知先手放啥特殊放0或1故每次保持放九个类似巴什博弈if(z*9c)printf(Bicarp\n);elseprintf(Monocarp\n);}}return 0;
}
