当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6823:Function

Special Judge 特殊评判
题目描述
Given a sequence of length $n$ $a[1..n]$, $S(a)$ is a set generated by $a$:

1. $S(a)=\{a_i|i\in [1,n]\}$, initially.

2. If $x,y \in S(a)$ and $x \oplus y \notin S$, add $x \oplus y$ to $S$.

Note that here $\oplus$ denotes the bitwise exclusive or, i.e. , $xor$.

If you knew little about that, please refer to https://en.wikipedia.org/wiki/Exclusive.

Construct a mapping $f:S(a) \rightarrow S(a)$ that satisfies all the following conditions:

1. If $x \in S(a)$ satisfying $f(x)=0$, then $\exists y \in S(a)$, satisfying $f(y)=x$.

2. If $x,y \in S(a)$ satisfying $f(x)=y$, then $f(y)=0$.

3. $\forall x,y \in S(a), \ f(x\oplus y)=f(x) \oplus f(y)$.



This problem contains two modes, specified by a parameter $op$.



The first mode:

The parameter $op=construct$, it means that you are a contestant and you need to construct a solution, which will be checked by $special \ judge$ on the evaluation machine.

Firstly, print $NoSolution$ if there doesn't exist a mapping function $f$ on $S(a)$ satisfying the above conditions and go on next test case(but you should also read some following extra data and do not print anything, see input), otherwise print $HaveSolution$ representing that you have a solution.

To check whether your solution is correct, then you are given an integer $m$ denoting the number of queries you should answer. For $i$-th query, read a nonnegative integer $x_i$, print $f(x_i)$ if $x_i \in S(a)$ or $-1$ if $x_i \notin S(a)$.

If there exists a solution $g$ satisfying $g(x_i)=f(x_i),i\in [1,m]$, your solution will be assumed to be correct, otherwise it is wrong.



The second mode:

The parameter $op=check$, it means that you are the evaluation machine and you need to check a solution.

Firstly, read a string $st$, $st=HaveSolution$ or $st=NoSolution$ denoting whether the evaluation machine assumes that there is a solution. If the conclusion is wrong, print $No$ and go on next test case(\textbf{but maybe you should also read some following extra data and do not print anything, see input}). Otherwise, if $st=HaveSolution$, you should check whether the construction $f$ is correct.

You are given an integer $m$ and $m$ pieces of information. For one of them, you should read a nonnegative integer $x_i$, and $f(x_i)$ is either a nonnegative integer or $-1$ according to whether the evaluation machine assumes that $x_i \in S(a)$. $-1$ means that it assumes that $x_i \notin S(a)$. And you should also check that $-1$ is correct or not. Namely, you have to note that if the given $x_i \notin S(a)$, but $f(x_i) \ne -1$, it is a wrong construction.


Note that the solution given by the evaluation machine may be not generated randomly.

If there exists a solution $g$ satisfying $g(x_i)=f(x_i),i\in [1,m]$, you should print $Yes$ denoting that the solution is correct, otherwise it is wrong and you should print $No$. That is to say, the criterion is the same for the two modes.


See the example for details.


输入解释
The first line contains one integer $T$, $T \in [1,550]$.

For each test case:

The first line contains one integer $n$, $n \in [1,10^6]$.

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, $a_i \in [0,2^{60})$.

Then you should read a string $op$.

If $op=contruct$, next line contains one integer $m$. The $i$-th of the next $m$ lines contains one integer $x_i$, $x_i \in [0,2^{60})$.

If $op=check$, then next line contains a string $st$, $st=HaveSolution$ or $st=NoSolution$.

If $st=HaveSolution$, the next line contains one integer $m$. Each of the next $m$ lines contains $2$ integers $x_i$ and $f(x_i)$, $x_i \in [0,2^{60}),f(x_i) \in [-1,2^{60})$.

The total of $n$ does not exceed $2 \times 10^6$.
The total of $m$ does not exceed $2 \times 10^5$.
输出解释
For each test case:

If $op=construct$, print $HaveSolution$ if you have a solution and for each $x_i$, output a line containing $f(x_i)$, or print $NoSolution$ with no extra output if you assumes that there doesn't exist a solution.

If $op=check$, output a line containing $Yes$ if it is correct, otherwise print $No$.
输入样例
4
4
1 1 2 3
check
HaveSolution
4
1 0
2 1
3 1
4 -1
1
1
construct
1
1
3
1 2 3
check
HaveSolution
2
1 0
4 1
3
1 2 3
construct
2
1
4
输出样例
Yes
NoSolution
No
HaveSolution
3
-1
来自杭电HDUOJ的附加信息
Recommend IceyWang

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6823

最后修改于 2020-10-25T23:34:42+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/3000MS(Java/Others) 524288/524288K(Java/Others)