Codeforces 1215 D. Ticket Game(博弈论)
程序员文章站
2022-03-16 07:58:08
...
题意:
有长度为 的串,内容为 数字或 。 先手,填数。希望前 个数和 后 个数和。 希望相等。问谁能赢。
显然各个位置的数字是没用的,我们只要知道两边的数字和分别是多少
并且状态显然和左右两边的 数量有关
因为最终我们只在意左右是否相等,即差值是否为
所以两边的数字和分别是多少也不必要,我们只要知道两边数字的差即可
对于当前某种两边都有 的情况,先手走了对他最优的决策,使数字差往对他有利的方向发展
后手显然可以在另一边做同样的决策,使得数字差又变回来,即后手可以抵消先手的决策
所以两边的 可以互相抵消,我们只要考虑剩下一边有 的情况
如果此时 数量刚好为 ,直接根据差值即可判断胜负
否则
此时如果 数量除以 ,即先手可以填的位置数量,乘以 即先手全填 得到的值大于另一边,那么最终差值不可能相等,先手全填 即可保证胜利
或者如果 数量除以 ,即后手可以填的位置数量,乘以 即后手全填 得到的值小于另一边,那么最终差值不可能相等,先手全填 即可稳赢
只有当 数量除以 乘以 以后值刚好等于另一边,那么后手稳赢,因为后手只要填 先手填的数值 即可。
AC代码:
const int N = 4e5 + 7;
int n, t;
char s[N];
int tl, tr, cntl, cntr, cnt;
int main()
{
sd(n);
ss(s + 1);
tl = 0, tr = 0, cntl = 0, cntr = 0;
rep(i, 1, n / 2)
{
if (s[i] != '?')
tl += s[i] - '0';
else
cntl++;
}
rep(i, n / 2 + 1, n)
{
if (s[i] != '?')
tr += s[i] - '0';
else
cntr++;
}
if (cntl < cntr)
swap(cntl, cntr), swap(tl, tr);
cnt = cntl - cntr, t = tl - tr;
if (!cnt && !t)
{
puts("Bicarp");
return 0;
}
if (!cnt && t || t >= 0 || cnt / 2 * 9 > -t || cnt / 2 * 9 < -t)
{
puts("Monocarp");
return 0;
}
puts("Bicarp");
return 0;
}
推荐阅读
-
codeforces D. Game With Array
-
Codeforces Round #533 (Div. 2) D. Kilani and the Game(bfs+模拟)
-
Codeforces Round #643 (Div. 2) D. Game With Array
-
Codeforces Round #459 (Div. 2):D. MADMAX(记忆化搜索+博弈论)
-
Codeforces Round #283 (Div. 2) D. Tennis Game_html/css_WEB-ITnose
-
Codeforces Round #283 (Div. 2) D. Tennis Game_html/css_WEB-ITnose
-
Ticket Game CodeForces - 1215D(博弈题,巴什博弈思维)
-
Codeforces 1215 D. Ticket Game(博弈论)
-
Codeforces Round #666 (Div. 2)D. Stoned Game(博弈问题)
-
Codeforces Round #685 (Div. 2)——D. Circle Game