题解 CF727C 【Guess the Array】

· · 题解

长度为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;
}