11389: [CSP-S2024] T4 - 擂台游戏
[Creator : ]
Time Limit : 2.000 sec Memory Limit : 512 MiB
Description
小 S 想要举办一场擂台游戏,如果共有 $2^k$ 名选手参加,那么游戏分为 $k$ 轮进行:
- 第一轮编号为 $1, 2$ 的选手进行一次对局,编号为 $3, 4$ 的选手进行一次对局,以此类推,编号为 $2^k - 1, 2^k$ 的选手进行一次对局。
- 第二轮在只保留第一轮的胜者的前提下,相邻的两位依次进行一场对局。
- 以此类推,第 $k - 1$ 轮在只保留第 $k - 2$ 轮的 $4$ 位胜者的前提下,前两位、后两位分别进行对局,也就是所谓的半决赛。
- 第 $k$ 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后,小 S 将比赛的规则设置为了擂台赛。具体而言,每位选手都有一个能力值 $a_1, a_2, \dots , a_{2^k}$,能力值为 $[0,2^{31}-1]$ 之内的整数。对于每场比赛,会先抽签决定一个数 $0/1$,我们将第 $R$ 轮的第 $G$ 场比赛抽到的数记为 $d_{R,G}$。抽到 $0$ 则表示表示编号小的选手为擂主,抽到 $1$ 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 $a\geq R$。也就是说,游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系,与另一位的能力值无关。
现在,小 S 先后陆续收到了 $n$ 位选手的报名信息,他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 $1, 2, \dots, n$。小 S 关心的是,补充**尽量少**的选手使总人数为 $2$ 的整次幂,且所有选手进行一次完整的擂台游戏后,所有可能成为总冠军的选手的编号之和是多少。
形式化地,设 $k$ 是最小的非负整数使得 $2^k\geq n$,那么应当补充 $(2^k-n)$ 名选手,且补充的选手的能力值可以任取 $[0,2^{31}-1]$ 之内的整数。如果补充的选手有可能取胜,也应当计入答案中。
当然小 S 觉得这个问题还是太简单了,所以他给了你 $m$ 个询问 $c_1,c_2,\dots,c_m$。小 S 希望你帮忙对于每个 $c_i$ 求出,在只收到前 $c_i$ 位选手的报名信息时,这个问题的答案是多少。
- 第一轮编号为 $1, 2$ 的选手进行一次对局,编号为 $3, 4$ 的选手进行一次对局,以此类推,编号为 $2^k - 1, 2^k$ 的选手进行一次对局。
- 第二轮在只保留第一轮的胜者的前提下,相邻的两位依次进行一场对局。
- 以此类推,第 $k - 1$ 轮在只保留第 $k - 2$ 轮的 $4$ 位胜者的前提下,前两位、后两位分别进行对局,也就是所谓的半决赛。
- 第 $k$ 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后,小 S 将比赛的规则设置为了擂台赛。具体而言,每位选手都有一个能力值 $a_1, a_2, \dots , a_{2^k}$,能力值为 $[0,2^{31}-1]$ 之内的整数。对于每场比赛,会先抽签决定一个数 $0/1$,我们将第 $R$ 轮的第 $G$ 场比赛抽到的数记为 $d_{R,G}$。抽到 $0$ 则表示表示编号小的选手为擂主,抽到 $1$ 则表示编号大的选手为擂主。擂主获胜当且仅当他的能力值 $a\geq R$。也就是说,游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系,与另一位的能力值无关。
现在,小 S 先后陆续收到了 $n$ 位选手的报名信息,他们分别告知了小 S 自己的能力值。小 S 会按照报名的先后顺序对选手进行编号为 $1, 2, \dots, n$。小 S 关心的是,补充**尽量少**的选手使总人数为 $2$ 的整次幂,且所有选手进行一次完整的擂台游戏后,所有可能成为总冠军的选手的编号之和是多少。
形式化地,设 $k$ 是最小的非负整数使得 $2^k\geq n$,那么应当补充 $(2^k-n)$ 名选手,且补充的选手的能力值可以任取 $[0,2^{31}-1]$ 之内的整数。如果补充的选手有可能取胜,也应当计入答案中。
当然小 S 觉得这个问题还是太简单了,所以他给了你 $m$ 个询问 $c_1,c_2,\dots,c_m$。小 S 希望你帮忙对于每个 $c_i$ 求出,在只收到前 $c_i$ 位选手的报名信息时,这个问题的答案是多少。
Input
本题的测试点包含有多组测试数据。但不同测试数据只是通过修改 $a_1, a_2, \dots , a_n$ 得到,其他内容均保持不变,请参考以下格式。其中 $\oplus$ 代表异或运算符,$a \bmod b$ 代表 $a$ 除以 $b$ 的余数。
输入的第一行包含两个正整数 $n, m$,表示报名的选手数量和询问的数量。
输入的第二行包含 $n$ 个非负整数 $a'_1,a'_2,\dots,a'_n$,这列数将用来计算真正的能力值。
输入的第三行包含 $m$ 个正整数 $c_1, c_2, \dots , c_m$,表示询问。
设 $K$ 是使得 $2^K \geq n$ 的最小的非负整数,接下来的 $K$ 行当中,第 $R$ 行包含 $2^{K-R}$ 个数(无空格),其中第 $G$ 个数表示第 $R$ 轮的第 $G$ 场比赛抽签得到的 $d_{R,G}=0/1$。
注意,由于询问只是将人数凑齐到 $2^k\geq c_i$,这里的 $k\leq K$,因此你未必会用到全部的输入值。
接下来一行包含一个正整数 $T$,表示有 $T$ 组测试数据。
接下来共 $T$ 行,每行描述一组数据,包含 $4$ 个非负整数 $X_0,X_1,X_2,X_3$,该组数据的能力值 $a_i=a'_i \oplus X_{i\bmod 4}$,其中 $1\leq i\leq n$。
输入的第一行包含两个正整数 $n, m$,表示报名的选手数量和询问的数量。
输入的第二行包含 $n$ 个非负整数 $a'_1,a'_2,\dots,a'_n$,这列数将用来计算真正的能力值。
输入的第三行包含 $m$ 个正整数 $c_1, c_2, \dots , c_m$,表示询问。
设 $K$ 是使得 $2^K \geq n$ 的最小的非负整数,接下来的 $K$ 行当中,第 $R$ 行包含 $2^{K-R}$ 个数(无空格),其中第 $G$ 个数表示第 $R$ 轮的第 $G$ 场比赛抽签得到的 $d_{R,G}=0/1$。
注意,由于询问只是将人数凑齐到 $2^k\geq c_i$,这里的 $k\leq K$,因此你未必会用到全部的输入值。
接下来一行包含一个正整数 $T$,表示有 $T$ 组测试数据。
接下来共 $T$ 行,每行描述一组数据,包含 $4$ 个非负整数 $X_0,X_1,X_2,X_3$,该组数据的能力值 $a_i=a'_i \oplus X_{i\bmod 4}$,其中 $1\leq i\leq n$。
Output
共输出 $T$ 行,对于每组数据,设 $A_i$ 为第 $i$($1 \leq i \leq m$)组询问的答案,你只需要输出一行包含一个整数,表示 $(1\times A_1) \oplus (2\times A_2) \oplus \dots \oplus (m\times A_m)$ 的结果。
Constraints
对于所有测试数据,保证:$2 \leq n, m \leq 10^5$,$0 \leq a_i, X_j < 2^{31}$,$1 \leq c_i \leq n$,$1 \leq T \leq 256$。
特殊性质 A:保证询问的 $c_i$ 均为 $2$ 的幂次。
特殊性质 B:保证所有的 $d_{R,G} = 0$。
特殊性质 A:保证询问的 $c_i$ 均为 $2$ 的幂次。
特殊性质 B:保证所有的 $d_{R,G} = 0$。
Sample 1 Input
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
Sample 1 Output
5
19
7
1
共有 $T = 4$ 组数据,这里只解释第一组。$5$ 名选手的真实能力值为 $[1, 0, 0, 2, 1]$。$5$ 组询问分别是对长度为 $5, 4, 1, 2, 3$ 的前缀进行的。
1. 对于长度为 $1$ 的前缀,由于只有 $1$ 号一个人,因此答案为 $1$。
2. 对于长度为 $2$ 的前缀,由于 $2$ 个人已经是 $2$ 的幂次,因此不需要进行扩充。根据抽签 $d_{1,1} = 1$ 可知 $2$ 号为擂主,由于 $a_2 < 1$,因此 $1$ 号获胜,答案为 $1$。
3. 对于长度为 $3$ 的前缀,首先 $1$ 号、$2$ 号比赛是 $1$ 号获胜(因为 $d_{1,1} = 1$,故 $2$ 号为擂主,$a_2 < 1$),然后虽然 $4$ 号能力值还不知道,但 $3$ 号、$4$ 号比赛一定是 $4$ 号获胜(因为 $d_{1,2} = 0$,故 $3$ 号为擂主,$a_3 < 1$),而决赛 $1$ 号、$4$ 号谁获胜都有可能(因为 $d_{2,1} = 1$,故 $4$ 号为擂主,如果 $a_4 < 2$ 则 $1$ 号获胜,$a_4 \geq 2$ 则 $4$ 号获胜)。综上所述,答案为 $1 + 4 = 5$。
4. 对于长度为 $4$ 的前缀,我们根据上一条的分析得知,由于 $a_4 \geq 2$ ,所以决赛获胜的是 $4$ 号。
5. 对于长度为 $5$ 的前缀,可以证明,可能获胜的选手包括 $4$ 号、$7$ 号、$8$ 号,答案为 $19$。
因此,该组测试数据的答案为 $(1 \times 19) \oplus (2 \times 4) \oplus (3 \times 1) \oplus (4 \times 1) \oplus (5 \times 5) = 5$。
1. 对于长度为 $1$ 的前缀,由于只有 $1$ 号一个人,因此答案为 $1$。
2. 对于长度为 $2$ 的前缀,由于 $2$ 个人已经是 $2$ 的幂次,因此不需要进行扩充。根据抽签 $d_{1,1} = 1$ 可知 $2$ 号为擂主,由于 $a_2 < 1$,因此 $1$ 号获胜,答案为 $1$。
3. 对于长度为 $3$ 的前缀,首先 $1$ 号、$2$ 号比赛是 $1$ 号获胜(因为 $d_{1,1} = 1$,故 $2$ 号为擂主,$a_2 < 1$),然后虽然 $4$ 号能力值还不知道,但 $3$ 号、$4$ 号比赛一定是 $4$ 号获胜(因为 $d_{1,2} = 0$,故 $3$ 号为擂主,$a_3 < 1$),而决赛 $1$ 号、$4$ 号谁获胜都有可能(因为 $d_{2,1} = 1$,故 $4$ 号为擂主,如果 $a_4 < 2$ 则 $1$ 号获胜,$a_4 \geq 2$ 则 $4$ 号获胜)。综上所述,答案为 $1 + 4 = 5$。
4. 对于长度为 $4$ 的前缀,我们根据上一条的分析得知,由于 $a_4 \geq 2$ ,所以决赛获胜的是 $4$ 号。
5. 对于长度为 $5$ 的前缀,可以证明,可能获胜的选手包括 $4$ 号、$7$ 号、$8$ 号,答案为 $19$。
因此,该组测试数据的答案为 $(1 \times 19) \oplus (2 \times 4) \oplus (3 \times 1) \oplus (4 \times 1) \oplus (5 \times 5) = 5$。