CF1500A Going Home

先考虑的做法，两层循环分别枚举a[x]和a[y]，再建立一个结构体数组id[x]={idx,idy};表示和为x的两个下标分别是idx和idy，在循环中你会收到一个和，你只需要判断id[x]是否有值，你可以用一个bool类型的数组sum[x]来存储，具体代码如下(挺好理解的)：

#include<bits/stdc++.h> using namespace std; const int N=5e6+5; int n,a[N]; bool mp[N]; struct node{ int x,y; }; node id[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ int sum=a[i]+a[j]; if(mp[sum]==1){ int idx=id[sum].x; int idy=id[sum].y; if(i!=idx&&i!=idy&&j!=idx&&j!=idy&&idx!=idy){ cout<<"YES\n"<<i<<' '<<j<<' '<<idx<<' '<<idy; return 0; } } mp[sum]=1; id[sum]={i,j}; } } cout<<"NO"; return 0; }

然后我们绞尽脑汁发现无法战胜，于是观察题面(以为读错题了)，观察到a[i]的值域为2.5e6,那么能凑出来的和最多有多少个呢？也就是2.5e6个数分别是1~2.5e6，两两匹配最多出来2*2.5e6也就是5e6个数，也就是我们枚举的的平方个数中有大量的重复，所以我们只需要枚举不重复的5e6个数就行，所以就是正解(什么鬼？)，上边给出的代码就可以通过题目(求赞)。