A3064 | 隐藏元素
来源官方 / 2024
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
时间限制：1000ms
内存限制：128MB
给定一个长度为 $N$ 的只包含 $0$ 和 $1$ 的数组 $A$；
其中 $A_1 = 1$，其他元素 $A_2, A_3, \cdots, A_N$ 的值是不确定的。
你需要根据 $M$ 条信息来确定数组中其他 $N - 1$ 个元素的值。
每条信息给出三个整数 $i, j, k$ 表示 $A_i \oplus A_j = k$。其中 $\oplus$ 表示按位异或运算。
题目保证 $M$ 条信息没有冲突。
$\large{数据范围}$
- $1 \le N, M \le 10^5$
- $1 \le i, j \le 10^5 (i \ne j)$
输入格式
对于每个测试文件格式如下：
$\tt{i_1\ j_1\ k_1}$
$\tt{i_2\ j_2\ k_2}$
$\tt{\vdots}$
$\tt{i_M\ j_M\ k_M}$
$\tt{N\ M}$
$\tt{i_1\ j_1\ k_1}$
$\tt{i_2\ j_2\ k_2}$
$\tt{\vdots}$
$\tt{i_M\ j_M\ k_M}$
输出格式
对于每个测试文件输出格式如下：
若 $M$ 条信息依然无法确定 $A_i(2 \le i \le N)$ 的值，则令 $A_i = -1$。
$\tt{A_1\ A_2\ A_3\ \cdots\ A_N}$
若 $M$ 条信息依然无法确定 $A_i(2 \le i \le N)$ 的值，则令 $A_i = -1$。
输入输出样例
输入 #1
5 4 1 2 1 2 3 1 3 4 1 4 5 1
输出 #1
1 0 1 0 1
输入 #2
5 4 1 2 1 2 3 1 1 3 0 4 5 1
输出 #2
1 0 1 -1 -1
输入 #3
10 13 4 3 0 1 7 0 9 5 0 3 4 0 5 9 0 4 5 0 3 6 0 2 7 1 3 9 0 2 4 1 5 7 0 6 2 1 10 7 0
输出 #3
1 0 1 1 1 1 1 -1 1 1
样例 $1$：
数组 $A$ 为 $[1, 0, 1, 0, 1]$，其中 $A_1 \oplus A_2 = 1$，$A_2 \oplus A_3 = 1$，$A_3 \oplus A_4 = 1$，$A_4 \oplus A_5 = 1$。
样例 $2$：
数组 $A$ 为 $[1, 0, 1, -1, -1]$，其中 $A_1 \oplus A_2 = 1$，$A_2 \oplus A_3 = 1$，$A_1 \oplus A_3 = 0$，$A_4 \oplus A_5 = 1$。$A_4$ 和 $A_5$ 的值无法确定。
数组 $A$ 为 $[1, 0, 1, 0, 1]$，其中 $A_1 \oplus A_2 = 1$，$A_2 \oplus A_3 = 1$，$A_3 \oplus A_4 = 1$，$A_4 \oplus A_5 = 1$。
样例 $2$：
数组 $A$ 为 $[1, 0, 1, -1, -1]$，其中 $A_1 \oplus A_2 = 1$，$A_2 \oplus A_3 = 1$，$A_1 \oplus A_3 = 0$，$A_4 \oplus A_5 = 1$。$A_4$ 和 $A_5$ 的值无法确定。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？