logo AlgoBeat OnlineJudge
登录 注册

#215048. [北大集训 2025] 复读机

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

考虑两位玩家进行如下的一个信任游戏(请注意,这个游戏可能与你所了解的某游戏有所不同):

  • 有一台这样的机器:当一位玩家放进去一枚硬币,另一位玩家会得到三枚硬币。
  • 游戏共进行 轮,两位玩家轮流行动,每次行动中,行动的玩家可以选择一下两种操作其一:
    • 「合作」:放入一枚硬币;
    • 「欺骗」:不放硬币。
  • 若选择「合作」,则行动的玩家失去一枚硬币,另一位玩家获得三枚硬币;若选择「欺骗」,则无事发生。
  • 每次行动后,另一位玩家会获知当前行动玩家的选择。

现在你将和「复读机」进行这个信任游戏,你先行动。「复读机」的策略可以用若干个长度不超过 的 01 串构成的可重集合 表示。他的具体策略为:先从集合中等概率随机选取一个 01 串 ,设其长度为 ,则他在第 () 轮(也就是他的第 次行动)时策略为:

  • 对于 ,若 ,则选择「合作」;若 ,选择「欺骗」。
  • 对于 ,选择与你的上一次选择相同,也就是第 轮的选择。

现在你的对手「复读机」的策略池 还未确定,他会进行 次操作:每次操作包含一个长度不超过 的 01 串 和数量 ,表示向 中加入 。特别地,如果 ,则表示从 中删除 ,其中 中至少有 ,且删除后 中至少还有 1 个 01 串。

你需要在每次操作后,计算出你在最优策略下,期望最多收益为多少硬币,每次操作后的询问相互独立。请注意,你已知集合 ,但你并不能得知他选择的 01 串 ,而你的每次行动都可以基于之前轮双方的选择进行决策。你只需要输出期望收益乘 的值,可以证明是一个整数。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数

输入的第 () 包含一个长度不超过 的 01 串 和一个整数

输出格式

输出到标准输出。

输出 行,每行一个整数表示答案。

样例

样例输入 1

8 3
111 1
1 1
0 1
011 4
1 -1
01 3
011 -3
0 3

样例输出 1

0
3
10
18
15
28
22
41

数据范围与提示

【子任务】

对于所有测试数据,均有:

  • 对于所有 ,均有 ,且
  • 对于所有 ,若 ,则 中至少有 ,且删除后 中至少还有 1 个 01 串。
子任务编号 分值 特殊性质
1 20 A
2 15
3
4 B
5 35

特殊性质 A:对于所有 ,均有 ,且

特殊性质 B:对于所有 ,均有

【评分方式】

对于每个子任务:

  1. 正确回答所有测试数据的第 次操作后的答案,可获得该子任务 的分数;
  2. 正确回答所有测试数据的答案,可获得该子任务 的分数。

注意:即使选手仅回答了第 次操作后的答案,也需要按照输出格式输出 个整数,分别对应每次操作后的答案。