题解 CF727C 【Guess the Array】
rui_er
2019-07-16 19:44:25
这是我第二道交互题。
首先，有n个未知数，n次询问，是一个n元1次方程组。
如何构造方程？
我们知道，对于方程组
$$\begin{cases}
x+y=a&\\
y+z=b&\\
z+x=c\\
\end{cases}$$
一定有唯一解。
所以前三个询问就可以这样询问：
```
? 1 2
? 2 3
? 1 3
```
解方程组方法：
```cpp
sum123 = (sum12 + sum23 + sum13) / 2;
a[1] = sum123 - sum23;
a[2] = sum123 - sum13;
a[3] = sum123 - sum12;
```
之后的第i次询问如下：
```
? 1 i
```
可解出整个数组。
完整代码：
```cpp
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
int a[5001];
int main()
{
int n, sum12, sum13, sum23, sum, sum123;
cin>>n;
cout<<"? 1 2"<<endl;
fflush(stdout);
cin>>sum12;
cout<<"? 1 3"<<endl;
fflush(stdout);
cin>>sum13;
cout<<"? 2 3"<<endl;
fflush(stdout);
cin>>sum23;
sum123 = (sum12 + sum23 + sum13) / 2;
a[1] = sum123 - sum23;
a[2] = sum123 - sum13;
a[3] = sum123 - sum12;
for(int i=4;i<=n;i++)
{
cout<<"? 1 "<<i<<endl;
fflush(stdout);
cin>>sum;
a[i] = sum - a[1];
}
cout<<"! ";
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
cout<<endl;
return 0;
}
```