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

https://ac.nowcoder.com/acm/contest/33195/I

题意
给定两个数列 a[] 和 b[]，问：

• 是否 $a[]$ 中存在两个位置 $i,j(i\ne j)$，$b[]$ 中存在两个位置 $k,l(k\ne l)$，满足： $\left|a_i-a_j\right|=\left|b_k-b_l\right|$ ？

如果存在，分别输出四个位置，否则输出 -1。

$2\le n,m\le 10^6,0\le a_i,b_i\le 10^7$

思路
不考虑先后位置，也就是使 $a_i-a_j=b_k-b_l$，即 $a_i+b_l=a_j+b_k$。

观察到 ai 和 bi 的范围，得知 ai + bl 的范围为 [0, 2e7]。

如果 a[] 中元素各不相同，并且 b[] 中元素各不相同，那么由鸽巢原理，如果遍历 2e7+1 个两数之和 ai + bl，那么一定有两个是相同的，这两个相同的便是满足的。

所以我们把两个数组分别去重，然后两重循环，最多遍历 2e7+1 次就能找到相同值，将其位置输出即可。

但是需要提前考虑去重之前就满足的情况：如果 a 数组中有两个数相同，并且 b 数组中有两个数相同，也是满足的。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define endl '\n'

const int N = 1000010, mod = 1e9+7;
int T, n, m;
int a[N], b[N];
int cnta[N*10], cntb[N*10];
int ta[N], tb[N];
int mp[N*20][4];
int mpa[N*10], mpb[N*10];

signed main(){
	scanf("%d%d", &n, &m);
	
	int flag1 = -1, flag2 = -1;
	for(int i=1;i<=n;i++){
		scanf("%d", &a[i]);
		cnta[a[i]] ++;
		if(cnta[a[i]] >= 2) flag1 = a[i];
		mpa[a[i]] = i;
	}
	
	for(int i=1;i<=m;i++){
		scanf("%d", &b[i]);
		cntb[b[i]] ++;
		if(cntb[b[i]] >= 2) flag2 = b[i];
		mpb[b[i]] = i;
	}
	
	if(flag1 != -1 && flag2 != -1)
	{
		int cnt = 0;
		for(int i=1;i<=n;i++){
			if(a[i] == flag1 && cnt < 2) cout << i << ' ', cnt ++;
		}
		cnt = 0;
		for(int i=1;i<=m;i++){
			if(b[i] == flag2 && cnt < 2) cout << i << ' ', cnt ++;
		}
		return 0;
	}
	
	sort(a+1, a+n+1);
	sort(b+1, b+m+1);
	
	int idx1 = 0, idx2 = 0;
	for(int i=1;i<=n;i++)
	{
		if(i == 1 || a[i] != a[i-1]) ta[++idx1] = a[i];
	}
	for(int i=1;i<=m;i++)
	{
		if(i == 1 || b[i] != b[i-1]) tb[++idx2] = b[i];
	}
	
	for(int i=0;i<=2e7;i++) mp[i][0] = -1;
	
	int flag = -1;
	for(int i=1;i<=idx1;i++)
	{
		for(int j=1;j<=idx2;j++)
		{
			int sum = ta[i] + tb[j];
			if(mp[sum][0] != -1){
				flag = sum;
				mp[sum][2] = ta[i], mp[sum][3] = tb[j];
				break;
			}
			mp[sum][0] = ta[i], mp[sum][1] = tb[j];
		}
		if(flag != -1) break;
	}
	
	if(flag != -1)
		cout << mpa[mp[flag][0]] << " " << mpa[mp[flag][2]] << " " << mpb[mp[flag][1]] << " " << mpb[mp[flag][3]];
	else cout << -1;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

---

终于把牛客多校补完了，要及时回顾复习啊！