牛客多校10 I

Yet Another FFT Problem?

题目链接

题目大意

给定两个长度为\(n\)和\(m\)的数组\(a\)和\(b\)，请找出一组解使得\(abs(a[l1] - a[r1]) = abs(b[l2] - b[r2])\)。

题解

对于两个数组中都有重复的数的情况，我们可以直接\(O(n)\)特判输出

然后我们考虑所有数都不同的情况

条件可以转化为\(a[l1]+b[l2]=a[r1]+b[r1]\)

首先想到\(O(n^2)\)的暴力，看似好像行不通

但是否真的会跑完\(n^2\)呢

由于每个数都是小于等于\(1e7\)的，因此\(a[l1]+b[l2]\)一定小于\(2e7\)

若将每个\(a[l1]+b[l2]\)占据一个位置，根据鸽笼原理，我们发现最多\(2e7\)次就会出现一个重复

因此实际最大复杂度\(2e7\)

这样就能直接暴力判断了

代码

#include<bits/stdc++.h>
#define MN 1000005
#define MM 20000005
int n,a[MN],b,m;
int n1,A[MN];
int nx[MM],ny[MM],u=10000000;
int vis[MM>>1],ggx=0,ggy;
bool ok=0;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        if(vis[a[i]]) {
            ggx=vis[a[i]];ggy=i;
        } else A[++n1]=i;
        vis[a[i]]=i;
    }
    memset(vis,0,sizeof vis);
    for(int i=1;i<=m;i++) {
        scanf("%d",&b);
        if(vis[b]) {
            if(ggx) {
                printf("%d %d %d %d\n",ggx,ggy,vis[b],i);
                ok=1;
                break;
            }
            continue;
        }
        vis[b]=i;
        for(int j=1;j<=n1;j++) {
            int o=b-a[A[j]]+u;
            if(nx[o]) {
                printf("%d %d %d %d\n",A[j],nx[o],ny[o],i);
//              printf("%d %d %d %d\n",o,b,A[j],a[A[j]]);
                ok=1;
                break;
            }
            nx[o]=A[j];
            ny[o]=i;
        }
        if(ok) break;
    }
    if(!ok) puts("-1");
}