Luogu CF727C Guess the Array

CF727C Guess the Array

注：本文含交互题 endl 与 fflush 不同种类的配合使用效果的测试（见 “四”）

一. 审题：

1. 前提条件：

一个数 $n$ 代表数组中数的个数。

2. 询问 & 输入：

询问：

输出两个数 $x$ ， $y$ 。代表询问 $a_x$ 和 $a_y$ 的和。

格式：? x y
输入：

读入一个数代表这两个数的和。

3. 输出：

数组中所有数的值。格式：! a[1] a[2] a[3] ... a[n]

二. 思路

1. 思考解法

我们可以不一口气把 $n$ 次都询问完（当然最后肯定是都要询问完的），既然 $n$ 个数询问 $n$ 次一定有解，那么我们可以先询问 $a_1+a_2$ ， $a_2+a_3$ 以及 $a_3+a_1$ 。这样就能先计算出 $a_1$ ， $a_2$ 以及 $a_3$ 。

只要有了一个数的具体值，我们每询问一次就可以算出一个数的具体值，这样一气呵成，避免了一口气询问完后堆积过多条件无从下手的情况。

2. 具体实现

前三个数：

解法有很多，如

$\ \ \ \ \begin{cases}x+y=a\\y+z=b\\z+x=c\end{cases}$

$\Longrightarrow 2x+2y+2z=a+b+c$

$\Longrightarrow x+y+z=\dfrac{a+b+c}{2}$

$\Longrightarrow x=\dfrac{a+b+c}{2}-b$

$y$ ， $z$ 同理。
剩下的数：

接下来询问 $a_1+a_4$ ， $a_1+a_5$ . . . $a_1+a_n$ 。

三. 代码

#include<bits/stdc++.h>
using namespace std;
const int MAXn = 5000;

int n;
int add12,add13,add23;	//addxy:第x个和第y个数的和
int add[MAXn + 10];	//add[x]:第1个和第x个数的和
int first;	//第一个数的值
int main() {
    scanf("%d", &n);
    cout << "? 1 2" << endl;	scanf("%d", &add12);
    cout << "? 2 3" << endl;    scanf("%d", &add23);
    cout << "? 1 3" << endl;	scanf("%d", &add13);//这里用了endl就不需要fflush(stdout)了
    first = (add13 - add23 + add12) >> 1;//读入前三个数间两两值得和，并计算第一个数
    for (int i = 4 ; i <= n; ++i) {
        cout << "? 1 " << i << endl;
        scanf("%d", &add[i]);
    }//读入第1个数和第4-n个数间两两的值
    cout << "! " << first;					fflush(stdout);
    cout << ' ' << add12 - first;			fflush(stdout);
    cout << ' ' << add23 - add12 + first;	fflush(stdout);
    for(int i = 4; i <= n; ++i) {
        cout << ' ' << add[i] - first;
    }
}