小清新构造题
题意
交互题.
有一个长度为\(n\)的数列\(\{a_i\}\), 满足\(a_i \in [0,n-1], n \in [4,2^{16}], n = 2^k\)
你可以进行最多\(n+1\)次询问, 询问分三种:
AND i j 返回\(a_i \& a_j\)的值
OR i j 返回\(a_i | a_j\)的值
XOR i j 返回\(a_i \oplus a_j\)的值
均需满足\(1 \leq i,j \leq n\)且\(i \ne j\)
当确定答案后, 你需要输出!然后在同一行内输出这个数组.
题解
首先一个显而易见的结论: 询问\(a_1\)与\(a_2...a_n\)的异或(共\(n-1\)次询问), 再在两次询问内求出\(a_1\)的值就能还原整个数组. 问题转化为如何求出\(a_1\),
因为数列长度为\(n\)值域为\([0,n-1]\), 由鸽巢原理可得:
数列中至少有两个数字相同
分为两种情况:
\(a_1\)与其他至少一个数字相同.
表现为至少一个异或询问\(a_1 \oplus a_i\)的答案为\(0\). 一次AND 1 i询问即可求出\(a_1\)的值.
\(a_i\)与\(a_j\)相同(\(i,j \ne 1\)).
此时至少两个异或询问的答案相等(\(a_1 \oplus a_i = a_1 \oplus a_j\)), 即\(a_i = a_j\). 通过一次AND i j可求出\(a_i\)的值, 再由\(a_1 \oplus a_i \oplus a_i = a_1\)求出\(a_1\)
数列中全部数字均不相同.
由于\(n = 2^k\)且\(n \ge 4\), \(k\)位二进制的每一种情况均会出现, 故必存在\(a_1 \oplus a_i = 1\). 显然\(a_1\)与\(a_i\)只有最后一位不同. 这时一次AND 1 i可获得\(a_1\)除了最后一位外的信息. 同理存在\(a_1 \oplus a_j = 2\), AND 1 j可获得\(a_1\)最后一位的信息. 两者综合起来即可求出\(a_1\)
以上无论何种情况, 询问次数都不超过\(n+1\)
时间复杂度\(O(n\log n)\) (因为有一次不必要的排序来去重)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int Xor[maxn],ans[maxn];
struct Node{
int w,idx;
Node(int w = 0,int idx = 0):w(w),idx(idx){}
bool operator < (const Node & x) const{
return w < x.w;
}
}node[maxn];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 2;i <= n;i++){
cout << "XOR 1 " << i << endl;
int x;
cin >> x;
Xor[i] = x;
node[i] = Node(x,i);
}
sort(node+2,node+n+1);
int idx = 0;
for(int i = 3;i <= n;i++)if(node[i].w == node[i-1].w)idx = i;
if(!node[2].w){
cout << "AND 1 " << node[2].idx << endl;
int x;
cin >> x;
ans[1] = x;
}
else if(idx){
int l = node[idx].idx,r = node[idx-1].idx;
cout << "AND " << l << " " << r << endl;
int x;
cin >> x;
ans[1] = Xor[l]^x;
}
else{
int bit_0 = 0,bit_1 = 0;
for(int i = 2;i <= n;i++){
if(Xor[i] == 1){
cout << "AND 1 " << i << endl;
int x;
cin >> x;
bit_0 = x;
}
else if(Xor[i] == 2){
cout << "AND 1 " << i << endl;
int x;
cin >> x;
bit_1 = x;
}
}
if(bit_0 & 1)bit_0--;
if(bit_1 & 1)bit_0++;
ans[1] = bit_0;
}
for(int i = 2;i <= n;i++)ans[i] = Xor[i]^ans[1];
cout << "! ";
for(int i = 1;i <= n;i++)cout << ans[i] << " ";
cout << endl;
return 0;
}
|