MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

题解 CF727C 【Guess the Array】

posted on 2018-07-26 20:18:11 | under 题解 |

长度为$n$的数组,询问$n$次来求出数组中每一个数的值

我们可以先询问三次

  1. $a[1]+a[2]$

  2. $a[1]+a[3]$

  3. $a[2]+a[3]$

然后根据这三次询问的结果,我们可以求出$a[1]$、$a[2]$、$a[3]$的值,然后我们就可以通过询问$a[3]+a[4]$、$a[4]+a[5]$、$a[5]+a[6]$……来求出$a[4]$、$a[5]$、$a[6]$……

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int read(){
    int k=0; char c=getchar();
    for(;c<'0'||c>'9';) c=getchar();
    for(;c>='0'&&c<='9';c=getchar())
      k=(k<<3)+(k<<1)+c-48;
    return k;
}
int a[5010];
int main(){
    int n=read();
    cout<<"? "<<1<<" "<<2<<endl; fflush(stdout);
    int x1=read();
    cout<<"? "<<2<<" "<<3<<endl; fflush(stdout);
    int x2=read();
    cout<<"? "<<1<<" "<<3<<endl; fflush(stdout);
    int x3=read();
    a[1]=(x1+x2+x3)/2-x2;
    a[2]=(x1+x2+x3)/2-x3;
    a[3]=(x1+x2+x3)/2-x1;
    for(int i=3;i<=n-1;i++){
        cout<<"? "<<i<<" "<<i+1<<endl;
        fflush(stdout); int x=read();
        a[i+1]=x-a[i];
    }
    printf("! ");
    for(int i=1;i<=n;i++)
      printf("%d ",a[i]);
    return 0;
}