题解 CF1167B 【Lost Numbers】
rui_er
2020-08-10 23:53:46
我们有一个由 $4,8,15,16,23,42$ 组成的排列，只能询问四次两个位置上的数的乘积。
下面是一些可能会考虑到的**错误的**策略（也是我做题时的思路），在这里放出体现我们的思考过程：
**策略 1**：每次询问两个相同的下标 $i$ 和它本身。
这种策略是最容易想到的，但是这样的话只能询问出 $4$ 个位置的值，剩下两个位置就没办法了。考虑其它策略。
**策略 2**：询问 $1$ 与 $1$ 的乘积，得到第一个数，此后三次询问 $(1,2)(2,3)(3,4)$。
和策略 1 有着同样的问题。
---
**正确策略**
通过上面的思考，我们得到了一个结论：**只有 $4$ 个位置是显然不行的**，考虑添加第五个位置。
我们可以询问 $(1,2)(2,3)(3,4)(4,5)$，这样就能方便的获得和五个位置相关的信息。
**具体解法**
在按照上面的策略询问完前五个数后得到了四个答案（代码中记做 $mutiple$），我们枚举所有 $6!=720$ 种可能的排列情况，对于每个排列，循环一遍判断是否符合询问得到的答案即可。
但是这样还不够，我们还要知道**满足四个答案的排列是唯一的**。
**唯一性证明**
自己口胡的，可能不太严谨，但是自认为比较好理解，可以手玩几个理解一下。
因为上面数列任意两个数的乘积都不同，我们想到，满足 $a_i\times a_j=k$ 的只有两种可能，即 $i$ 与 $j$ 交换。而上面就相当于固定了前五个数，因为数列中的六个数给定，可以通过排除来获得第六个数的信息。
唯一性得证，策略正确。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
int a[7] = {-1, 4, 8, 15, 16, 23, 42}, multiple[5];
int main() {
for(int i=1;i<=4;i++) {
printf("? %d %d\n", i, i+1);
fflush(stdout);
scanf("%d", &multiple[i]);
}
do {
bool _ = true;
for(int i=1;i<=4;i++) {
if(a[i] * a[i+1] != multiple[i]) {
_ = false;
break;
}
}
if(_) {
printf("! ");
for(int i=1;i<=6;i++) printf("%d ", a[i]);
puts("");
break;
}
}while(next_permutation(a+1, a+7));
return 0;
}
```