Description
本题是交互题。
有一个固定的数组 A，同时通过数组 A 构造出数组 P，具体来讲，Pi 是 A 中除 Ai 外的所有元素的按位或。
你需要在最多 13 次询问中得到最后的 P 数组。
2≤n≤1000。
Solution
首先有一个 2logn 的是注意到对于任意两个不同的数 i,j，则必有至少一位满足 i 和 j 不同，所以只要维护 vali,0/1 表示第 i 位为 0/1 的数的或，那么每次只要把与 i 不同的位的 val 值或起来即可。
考虑怎么优化到 logn。
容易发现要想优化掉那个 2，就必定要构造出一种方案，使得 idi 存在一位为 1，idj 存在一位为 0。
所以只要给每个 i 分配 popcount 相同的 id 即可满足条件。
经过计算，这些 id 最小位数是 13，因为 (613)>1000。
总询问次数：13。
Code
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
| #include <bits/stdc++.h>
#define int int64_t
const int kMaxN = 1e3 + 5;
int n;
int id[kMaxN], val[13];
int ask(std::vector<int> vec) {
if (!vec.size()) return 0;
std::cout << "? " << vec.size() << ' ';
for (auto x : vec) std::cout << x << ' ';
std::cout << std::endl;
int x;
std::cin >> x;
return x;
}
void dickdreamer() {
std::cin >> n;
int cnt = 0;
for (int i = 0; i < (1 << 13); ++i) {
if (__builtin_popcount(i) == 6) {
id[++cnt] = i;
if (cnt == n) break;
}
}
for (int i = 0; i < 13; ++i) {
std::vector<int> vec;
for (int j = 1; j <= n; ++j)
if (~id[j] >> i & 1)
vec.emplace_back(j);
val[i] = ask(vec);
}
std::cout << "! ";
for (int i = 1; i <= n; ++i) {
int res = 0;
for (int j = 0; j < 13; ++j)
if (id[i] >> j & 1)
res |= val[j];
std::cout << res << ' ';
}
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
while (T--) dickdreamer();
return 0;
}
|