2022牛客多校10 I-Yet Another FFT Problem?（鸽巢原理）

 

题目大意：给定一个n，m，分别代表a数组和b数组的长度，接下来给出a数组和b数组，问是否存在i,j,k,l满足1<=i,j<=n，1<=k,l<=m，i!=j,k!=l使得|aj-ai|=|bl-bk|，如果存在则输出，否则输出-1.

解题思路：由|aj-ai|=|bl-bk|交换左右两边可以去掉绝对值得到aj+bk=bl+ai,又因为0<=ai,bi<=1e7,所以我们可以开长度为2e7的数组作为map映射a，b两个数组中每个值的位置，以及两个数的加和==temp时两个数字ai和bl，在两个数组中分别出现的位置，具体的做法就是遍历a，b两个数组中所有不同的数字，并记录两个数的加和，如果两个数的加和在之前已经出现过，那么答案就是当前两个数的位置和之前出现相同加和时两个数的位置，这里我们需要注意一点就是a，b两个数组必须去重之后才能遍历两个数组找加和，因为如果不去重的话两个数组的长度都是1e6两重循环会超时的，但是由于我们去重了，所以两个数的加和最多有2e7种情况，所以复杂度就不会超了，但是我们还要考虑到一种情况就是在a,b两个数组中可能会有ai=aj,bl=bk，所以在去重之前我们要特判一下这种情况。最后也是说一点注意事项，前面说到要用数组来模拟map的功能，主要是因为map会比数组要慢，我一开始就是用的map结果超时了，但是改成数组之后就过了。

上代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int N=2e7+10;
int n,m,a[N],b[N];
int mpa1[N],mpa2[N],mpb1[N],mpb2[N],mp[N];
vector<int>ca,cb;
int main()
{
	scanf("%d %d",&n,&m);
	int posa1=0,posa2=0,posb1=0,posb2=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(mpa1[a[i]])
		{
			posa1=mpa1[a[i]];
			posa2=i;
		}
		else
		{
			mpa1[a[i]]=i;
			ca.push_back(a[i]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&b[i]);
		if(mpb1[b[i]])
		{
			posb1=mpb1[b[i]];
			posb2=i;
		}
		else
		{
			mpb1[b[i]]=i;
			cb.push_back(b[i]);
		}	
	}
	sort(ca.begin(),ca.end());
	sort(cb.begin(),cb.end());
	ca.erase(unique(ca.begin(),ca.end()),ca.end());
	cb.erase(unique(cb.begin(),cb.end()),cb.end());
	if(posa1&&posb1)
	{
		cout<<posa1<<" "<<posa2<<" "<<posb1<<" "<<posb2<<endl;
		return 0;
	}
	int flag=0;
	for(int i=0;i<ca.size();i++)
		for(int j=0;j<cb.size();j++)
		{
			int temp=ca[i]+cb[j];
			if(mpa2[temp])
			{
				cout<<mpa1[ca[i]]<<" "<<mpa2[temp]<<" "<<mpb1[cb[j]]<<" "<<mpb2[temp];
				flag=1;
				return 0;	
			}
			mpa2[temp]=mpa1[ca[i]];
			mpb2[temp]=mpb1[cb[j]];
		}
		if(flag==0)
		cout<<"-1"<<endl;
		return 0;
 }