5199. Extra Large Knapsack

单点时限: 1.0 sec

内存限制: 1024 MB

有一次 Compute 打比赛的时候拿到了一个超大背包,而这个背包不止大这么简单,它可以把装的物品的体积暂时改变,这就使得他可以装更多的东西。

具体地,如果背包里面装了 $k$ 件物品,而这 $k$ 件物品的体积分别为 $w_1,w_2,\ldots,w_k$,则这 $k$ 件物品的总体积 $W$ 就变成了 $\displaystyle W=\bigoplus_{i = 1}^{k} w_i = w_1\oplus w_2 \oplus \ldots \oplus w_k$。其中 $\oplus$ 表示按位异或运算。

——第 19 届上海大学程序设计联赛春季赛 F 题

第 21 届上海大学程序设计联赛春季赛中,Compute 不出意外地又夺冠了,他又得到了一个和第 19 届上海大学程序设计联赛春季赛同样的超大背包。因此他有了两个超大背包。

在比赛结束后,他带着这两个背包来到了上海大学教育超市采购物品。他希望购买 $n$ 件物品,同时他还希望把这些物品分成两组(每组至少一件物品),分别放到这两个背包中,且放入背包后物品的总体积 $W$ 相等(背包中物品的总体积计算方式和第 19 届上海大学程序设计联赛春季赛的背包是相同的)。

现在,你需要帮他计算出一种可行的分组方案,或者告诉他这是不可能做到的。

输入格式

有多组测试数据,第一行包含一个整数 $T$ ($T \leq 1000$) 表示测试数据的组数。对于每组测试数据:

第一行包含一个整数 $n$ ($1 \leq n \leq 10$) 表示 Compute 想购买的物品的个数。

第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$ ($0 \leq w_i < 65536$) ,中间以空格分隔,分别表示每件物品的体积。

输出格式

对于每组测试数据,如果 Compute 可以如题目描述把物品分成两组,首先输出一行”Yes” (不包含引号,不区分大小写),第二行输出一个长度为 $n$ 的 01 串 $s_1s_2 \ldots s_n$,表示物品的分组方式,其中 $s_i = 0$ 表示第 $i$ 个物品放入第一个背包,$s_i = 1$ 表示第 $i$ 个物品放入第二个背包,如果有多种合法的答案,您可以输出任意一种;如果 Compute 无法如题目描述把物品分成两组,输出一行 “No”。

样例

Input
3
7
1 2 3 4 5 6 7
10
2 6 7 9 8 1 8 2 8 6
5
26 79 81 82 86
Output
Yes
0110011
No
Yes
00110

提示

对于第一组样例,$1 \oplus 4 \oplus 5 = 2 \oplus 3 \oplus 6 \oplus 7 = 0$;

对于第三组样例,$26 \oplus 79 \oplus 86 = 81 \oplus 82 = 3$。

269 人解决,296 人已尝试。

296 份提交通过,共有 740 份提交。

1.9 EMB 奖励。

创建: 5 月,3 周前.

修改: 5 月,3 周前.

最后提交: 3 周,4 天前.

来源: N/A

题目标签