[蓝桥杯 2021 省 A] 异或数列

Luogu
IDLGP8743
Time1000ms
Memory512MB
DifficultyP4
博弈论2021位运算蓝桥杯省赛
Alice 和 Bob 正在玩一个异或数列的游戏。初始时,Alice 和 Bob 分别有一个初始值为 $0$ 的整数 $a$ 和 $b$, 有一个给定的长度为 $n$ 的公共数列 $X_{1}, X_{2}, \cdots, X_{n}$ 。 Alice 和 Bob 轮流操作,Alice 先手,每步可以在以下两种选项中选一种: 选项 1: 从数列中选一个 $X_{i}$ 给 Alice 的数异或上, 或者说令 $a$ 变为 $a \oplus X_{i}$ 。(其中 $\oplus$ 表示按位异或) 选项 2: 从数列中选一个 $X_{i}$ 给 Bob 的数异或上,或者说令 $b$ 变为 $b \oplus X_{i}$ 。 每个数 $X_{i}$ 都只能用一次, 当所有 $X_{i}$ 均被使用后($n$ 轮后)游戏结束。游戏结束时, 拥有的数比较大的一方获胜,如果双方数值相同,即为平手。 现在双方都足够聪明,都采用最优策略,请问谁能获胜? ## Input 每个评测用例包含多组询问。询问之间彼此独立。 输入的第一行包含一个整数 $T$,表示询问数。 接下来 $T$ 行每行包含一组询问。其中第 $i$ 行的第一个整数 $n_{i}$ 表示数列长度,随后 $n_{i}$ 个整数 $X_{1}, X_{2}, \cdots, X_{n_{i}}$ 表示数列中的每个数。 ## Output 输出 $T$ 行,依次对应每组询问的答案。 每行包含一个整数 $1$、$0$ 或 $-1$ 分别表示 Alice 胜、平局或败。 [samples] ## Note 对于所有评测用例, $1 \leq T \leq 2\times 10^5,1 \leq \sum\limits_{i=1}^{T} n_{i} \leq 2\times10^5,0 \leq X_{i}<2^{20}$ 。 蓝桥杯 2021 第一轮省赛 A 组 G 题。
Samples
Input #1
4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580
Output #1
1
0
1
1
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2021 省 A] 异或数列",
    "description": {
      "content": "Alice 和 Bob 正在玩一个异或数列的游戏。初始时,Alice 和 Bob 分别有一个初始值为 $0$ 的整数 $a$ 和 $b$, 有一个给定的长度为 $n$ 的公共数列 $X_{1}, X_{2}, \\cdots, X_{n}$ 。 Alice 和 Bob 轮流操作,Alice 先手,每步可以在以下两种选项中选一种: 选项 1: 从数列中选一个 $X_{i}$ 给 Alice 的数异",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8743"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice 和 Bob 正在玩一个异或数列的游戏。初始时,Alice 和 Bob 分别有一个初始值为 $0$ 的整数 $a$ 和 $b$, 有一个给定的长度为 $n$ 的公共数列 $X_{1}, X_{2}, \\cdots, X_{n}$ 。\n\nAlice 和 Bob 轮流操作,Alice 先手,每步可以在以下两种选项中选一种:\n\n选项 1: 从数列中选一个 $X_{i}$ 给 Alice 的数异...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments