#2491. [CSP-S 2024] 擂台游戏
[CSP-S 2024] 擂台游戏
题目描述
小 S 想要举办一场擂台游戏,如果共有 名选手参加,那么游戏分为 轮进行:
- 第一轮编号为 的选手进行一次对局,编号为 的选手进行一次对局,以此类推,编号为 的选手进行一次对局。
- 第二轮在只保留第一轮的胜者的前提下,相邻的两位依次进行一场对局。
- 以此类推,第 轮在只保留第 轮的 位胜者的前提下,前两位、后两位分别进行对局,也就是所谓的半决赛。
- 第 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后,小 S 将比赛的规则设置为了擂台赛。具体而言,每位选手都有一个能力值 ,能力值为 之内的整数。对于每场比赛,会先抽签决定一个数 ,我们将第 轮的第 场比赛抽到的数记为 。抽到 则表示表示编号小的选手为擂主,抽到 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 。也就是说,游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系,与另一位的能力值无关。
现在,小 S 先后陆续收到了 位选手的报名信息,他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 。小 S 关心的是,补充尽量少的选手使总人数为 的整次幂,且所有选手进行一次完整的擂台游戏后,所有可能成为总冠军的选手的编号之和是多少。
形式化地,设 是最小的非负整数使得 ,那么应当补充 名选手,且补充的选手的能力值可以任取 之内的整数。如果补充的选手有可能取胜,也应当计入答案中。
当然小 S 觉得这个问题还是太简单了,所以他给了你 个询问 。小 S 希望你帮忙对于每个 求出,在只收到前 位选手的报名信息时,这个问题的答案是多少。
输入格式
本题的测试点包含有多组测试数据。 但不同测试数据只是通过修改 得到,其他内容均保持不变,请参考以下格式。其中 代表异或运算符, 代表 除以 的余数。
输入的第一行包含两个正整数 ,表示报名的选手数量和询问的数量。
输入的第二行包含 个非负整数 ,这列数将用来计算真正的能力值。
输入的第三行包含 个正整数 ,表示询问。
设 是使得 的最小的非负整数,接下来的 行当中,第 行包含 个数(无空格),其中第 个数表示第 轮的第 场比赛抽签得到的 。
注意,由于询问只是将人数凑齐到 ,这里的 ,因此你未必会用到全部的输入值。
接下来一行包含一个正整数 ,表示有 组测试数据。
接下来共 行,每行描述一组数据,包含 个非负整数 ,该组数据的能力值 ,其中 。
输出格式
共输出 行,对于每组数据,设 为第 ()组询问的答案,你只需要输出一行包含一个整数,表示 的结果。
样例 #1
样例输入 #1
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
样例输出 #1
5
19
7
1
提示
【样例 1 解释】
共有 组数据,这里只解释第一组。 名选手的真实能力值为 。 组询问分别是对长度为 的前缀进行的。
- 对于长度为 的前缀,由于只有 号一个人,因此答案为 。
- 对于长度为 的前缀,由于 个人已经是 的幂次,因此不需要进行扩充。根据抽签 可知 号为擂主,由于 ,因此 号获胜,答案为 。
- 对于长度为 的前缀,首先 号、 号比赛是 号获胜(因为 ,故 号为擂主,),然后虽然 号能力值还不知道,但 号、 号比赛一定是 号获胜(因为 ,故 号为擂主,),而决赛 号、 号谁获胜都有可能(因为 ,故 号为擂主,如果 则 号获胜, 则 号获胜)。综上所述,答案为 。
- 对于长度为 的前缀,我们根据上一条的分析得知,由于 ,所以决赛获胜的是 号。
- 对于长度为 的前缀,可以证明,可能获胜的选手包括 号、 号、 号,答案为 。
因此,该组测试数据的答案为 。
【样例 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。
【数据范围】
对于所有测试数据,保证:,,,。
测试点 | 特殊性质 A | 特殊性质 B | ||
---|---|---|---|---|
否 | 否 | |||
是 | ||||
否 | 是 | |||
否 | ||||
是 | ||||
否 | 是 | |||
否 | ||||
特殊性质 A:保证询问的 均为 的幂次。
特殊性质 B:保证所有的 。
Statistics
Related
In following contests: