题库 信息学奥赛题库 题目列表 擂台游戏(arena)【题目描述】小 S 想要举办...
问答题

擂台游戏(arena)

【题目描述】

小 想要举办一场擂台游戏,如果共有 2名选手参加,那么游戏分为 轮进行:

  • 第一轮编号为 1的选手进行一次对局,编号为 3的选手进行一次对局,以此

    类推,编号为 2− 12的选手进行一次对局。

  • 第二轮在只保留第一轮的胜者的前提下,相邻的两位依次进行一场对局。

  • 以此类推,第 − 轮在只保留第 − 轮的 位胜者的前提下,前两位、后两位分别进行对局,也就是所谓的半决赛。

第 轮即为半决赛两位胜者的决赛。

确定了游戏晋级的规则后,小 将比赛的规则设置为了擂台赛。具体而言,每位选 手都有一个能力值 a, a· · · , a2,能力值为 [0231 − 1] 之内的整数。对于每场比赛,会 先抽签决定一个数 0/1,我们将第 轮的第 场比赛抽到的数记为 dR,G。抽到 则表 示表示编号小的选手为擂主,抽到 则表示编号大的选手为擂主。擂主获胜当且仅当他 的能力值 ≥ R。也就是说,游戏的胜负只取决于的 大小关系,

现在,小 先后陆续收到了 位选手的报名信息,他们分别告知了小 自己的能 力值。小 会按照报名的先后顺序对选手进行编号为 12· · · , n。小 关心的是,补充 的选手使总人数为 的整次幂,且所有选手进行一次完整的擂台游戏后,所有可 能成为总冠军的选手的为多少。

形式化地,设 是最小的非负整数使得 2≥ n,那么应当补充 (2− n名选手,且 补充的选手的能力值可以任取[0,2311]之内的整数。............,也

当然小 觉得这个问题还是太简单了,所以他给了你 个询问 c1, c2· · · , cm。小 希望你帮忙对于每个 c求出,在只收到前 c位选手的报名信息时,这个问题的答案 是多少。

【输入格式】

从文件 arena.in 中读入数据。

.,但不同测试数据只是通过修改a1,a2,··· ,a得 到,其他内容均保持不变,请参考以下格式。其中 ⊕ 代表异或运算符,mod 代表 除以 的余数。

输入的第一行包含两个正整数 n, m,表示报名的选手数量和询问的数量。

输入的第二行包含 个非负整数 a1, a2· · · , an,这列数将用来计算真正的能力值。 

输入的第三行包含 个正整数 c1, c2· · · , cm,表示询问。

K是使得2n的最小的非负整数,接下来的K行当中,第R行包含2KR个数(无空格),其中第 个数表示第 轮的第 场比赛抽签得到的 dR,G = 0/1

注意,由于询问只是将人数凑齐到 2≥ ci,这里的 ≤ K,因此你未必会用到全部 的输入值。

接下来一行包含一个正整数 T,表示有 组测试数据。

接下来共 行,每行描述一组数据,包含 个非负整数 X0, X1, X2, X3,该组数据 的能力值a=aXimod4,其中1in

【输出格式】

输出到文件 arena.out 中。

共输出 行,对于每组数据,设 A为第 i(≤ ≤ m)组询问的答案,你只需要 输出一行包含一个整数,表示 (1 × A1⊕ (2 × A2⊕ · · · ⊕ (× Am的结果。

【样例 输入】

5 5
0 0 0 0 0
5 4 1 2 3
1001
10
1
4
2 1 0 0
1 2 1 0
0 2 3 1
2 2 0 1


【样例 输出】


19 

1


【样例 解释】

共有 = 4 组数据,这里只解释第一组。名选手的真实能力值为 [10021]组询问分别是对长度为 5412的前缀进行的。

1. 对于长度为 的前缀,由于只有 号一个人,因此答案为 1

  1. 对于长度为 的前缀,由于 个人已经是 的幂次,因此不需要进行扩充。根据 抽签d1,= 1可知2号为擂主,由于a1,因此1号获胜,答案为1

  2. 对于长度为 的前缀,首先 号、号比赛是 号获胜(因为 d1,= 1,故 号 为擂主,a1),然后虽然 号能力值还不知道,但 号、号比赛一定是 号 获胜(因为 d1,= 0,故 号为擂主,a1),而决赛 号、号谁获胜都有可 能(因为d2,= 1,故4号为擂主,如果a21号获胜,a≥ 24号获 胜)。综上所述,答案为 1 + 4 = 5

  3. 对于长度为 的前缀,我们根据上一条的分析得知,由于 a≥ ,所以决赛获 胜的是号。

  4. 对于长度为 的前缀,可以证明,可能获胜的选手包括 号、号、号,答案 为 19

因此,该组测试数据的答案为(1×19)(2×4)(3×1)(4×1)(5×5) = 5。 

【样例 2

见选手目录下的 arena/arena2.in 与 arena/arena2.ans。 这组样例满足特殊性质 A

【样例 3
见选手目录下的 arena/arena3.in 与 arena/arena3.ans

这组样例满足特殊性质 B。 

【样例 4

见选手目录下的 arena/arena4.in 与 arena/arena4.ans。 

【样例 5

见选手目录下的 arena/arena5.in 与 arena/arena5.ans。 

【数据范围】

对于所有测试数据,保证:≤ n,m ≤ 105≤ ai,X231≤ c≤ n≤ ≤ 256

特殊性质 A:保证询问的 c均为 的幂次。

特殊性质 B:保证所有的 dR,G = 0

题目信息
完善程序 2024年 复赛
-
正确率
0
评论
72
点击