CF1582D Vupsen, Pupsen and 0 个人题解

Cht_master · 2021-10-29 19:18:32 · 题解

• 题意简述：给定数列 a，构造数列 b 满足 \sum a(i)\cdot b(i)=0，\sum|b(i)|\le10^9，b(i)\ne0。多组数据，1\le t\le 100，2\le n\le 10^5，\sum n\le2\cdot 10^5，-10^4\le a(i)\le10^4。

• 题目简析：

  • 直觉是让两个数互相抵消，即用 b(i)=-a(i+1),b(i+1)=a(i) 来抵消。由于 -10^4\le a(i)\le10^4，所以对应的 b(i) 也满足 -10^4\le b(i)\le10^4。

  • 长度为偶数可以直接按照上面的方法构造。现在考虑长度为奇数。可以想到用某 3 个数来抵消，令这 3 个数是 a,b,c。那我们需要找到满足下列方程的一组解：

    a\cdot x+b\cdot y=-c\cdot z

    发现当 a+b\ne0 时取 x=y=-c,z=a+b 即可，若 a+b=0 交换 b,c 即可。话说这构造挺巧妙的，因为我怎么会告诉你我最开始用扩欧做结果一直 WA 呢。

• //核心是让两个数互相抵消.
  //但若数组长度是奇数,就让某三个数a,b,c互相抵消,解不定方程a*x+b*y=-c*z即可.
  //讨论当a(1)+a(2)!=0:则令x=-a(3),y=-a(3),z=a(1)+a(2)即可.
  #include<bits/stdc++.h>
  using namespace std;
  const int mxN(2e5);
  int n,a[mxN+5];
  int main(){
  int T,s;scanf("%d",&T);
  while(T--){
      s=1,scanf("%d",&n);for(int i(1);i<=n;++i)scanf("%lld",&a[i]);
      if(n&1){
          s=4;
          if(a[1]+a[2]!=0)printf("%d %d %d ",-a[3],-a[3],a[1]+a[2]);
          else if(a[2]+a[3]!=0)printf("%d %d %d ",a[2]+a[3],-a[1],-a[1]);
          else printf("%d %d %d ",-a[2],a[1]+a[3],-a[2]);
      }
      for(int i(s);i<=n;i+=2)printf("%d %d ",-a[i+1],a[i]);
      putchar('\n');
  }
  return 0;
  }