http://codeforces.com/contest/1500

A. Going Home

 

题意：给定一个数列 aa，求四个不同的位置 x,y,z,wx, y, z, w 满足 ax+ay=az+awa_x + a_y = a_z + a_w。(1≤ai≤2.5⋅106)(1 \leq a_i \leq 2.5 \cdot 10^6)

暴力枚举+复杂度计算

如果是普通题目，复杂度至少是 O(n2)O(n^2)，肯定不行。

但是发现这个数列元素很小，两个元素的和最多只有 5×1065\times 10^6。

直接暴力枚举 ai,aja_i,a_j，如果之前出现过 (x,y)(x,y) 满足 ax+ay=ai+aja_x+a_y=a_i+a_j，则得到答案。

注意到 ai+aj≤5×106a_i+a_j\le 5\times 10^6，则由鸽笼原理得到在最多 5×1065\times 10^6 次枚举后一定能得到两组相同的和。

当然，上面是在 (i,j),(x,y)(i,j),(x,y) 恰好是四个不同的位置的理想情况下，但是讨论下就能发现只要记录每个和的上一次出现位置 (x,y)(x,y)，则只要答案存在，就一定能找到。且复杂度也只是多了常数级别。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 5e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
int a[N];
int x[N], y[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			int s = a[i] + a[j];
			if (x[s] && y[s] && y[s] != j && y[s] != i) {
				printf("YES\n%d %d %d %d\n", x[s], y[s], i, j);
				return 0;
			}
		}
		for (int j = i + 1; j <= n; j++) {
			x[a[i] + a[j]] = i, y[a[i] + a[j]] = j;
		}
	}
	puts("NO");
	return 0;
}

 

B. Two chandeliers

 

题意：给定长为 nn 的数列 aa，长为 mm 的数列 bb，每个数字在每个数列中最多出现一次。第 ii 天分别从这两个循环数列中拿第 ii 个数，问最少在第几天遇到第 kk 次拿到两个不同的数字。1≤n,m≤500 000,1≤k≤1012,1≤ai,bi≤2⋅max⁡(n,m)1 \le n, m \le 500\,000,1 \le k \le 10^{12},1 \le a_i,b_i \le 2 \cdot \max(n, m)

二分+扩展中国剩余定理

很关键的一点在于每个数在一个数列中最多出现一次。

最少在第几天遇到第 kk 次拿到两个不同的数字，显然要二分答案。

则现在需要求在前 xx 天有几次拿到两个不同的数。可以逆向思考变成求有几次拿到两个相同的数。

假设颜色 cc 在 aa 中的位置为 pa[c]pa[c]，在 bb 中的位置为 pb[c]pb[c]，在第 t,(t<lcm(n,m))t,(t<lcm(n,m)) 天同时选中 pa[c],pb[c]pa[c],pb[c]。则有

{t=pa[c](mod  n)t=pb[c](mod  m)\begin{cases} t= pa[c](\mod n)\\ t=pb[c](\mod m) \\ \end{cases}

由于 n,mn,m 不一定互质，所以excrt求。

之后对于给定的 xx 天，先求出 lcm 的整数倍的答案，再加上多出来的。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, m;
ll k;
int a[N], b[N];
ll pa[N], pb[N], p[N];
ll g, sg, lc;
ll x, y;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	return b == 0 ? a : gcd(b, a % b);
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
	if (b == 0) { x = 1, y = 0; return a; }
	ll r = exgcd(b, a % b, x, y), tmp;
	tmp = x; x = y; y = tmp - (a / b) * y;
	return r;
}
ll inv(ll a, ll b) {
	ll r = exgcd(a, b, x, y);
	while (x < 0) x += b;
	return x;
}
ll M[10], C[10];
ll excrt(ll* M, ll* C, int n) {
	for (int i = 2; i <= n; i++) {
		ll M1 = M[i - 1], M2 = M[i], C2 = C[i], C1 = C[i - 1], T = gcd(M1, M2);
		if ((C2 - C1) % T != 0) return -1;
		M[i] = (M1 * M2) / T;
		C[i] = (inv(M1 / T, M2 / T) * (C2 - C1) / T) % (M2 / T) * M1 + C1;
		C[i] = (C[i] % M[i] + M[i]) % M[i];
	}
	return C[n];
}
ll cal(ll k) {
	ll ans = k / lc * sg;
	k %= lc;
	ans += k;
	for (int i = 1; i < N; i++) {
		if (p[i] != -1 && p[i] < k)ans--;
	}
	return ans;
}
int main() {
	scanf("%d%d%lld", &n, &m, &k);
	memset(pa, -1, sizeof(pa));
	memset(pb, -1, sizeof(pb));
	for (int i = 0; i < n; i++)scanf("%d", &a[i]), pa[a[i]] = i;
	for (int i = 0; i < m; i++)scanf("%d", &b[i]), pb[b[i]] = i;
	g = gcd(n, m);
	lc = 1ll*n * m / g;
	sg = lc;
	for (int i = 1; i < N; i++) {
		if (pa[i] == -1 || pb[i] == -1) {
			p[i] = -1;
			continue;
		}
		M[1] = n; M[2] = m;
		C[1] = pa[i]; C[2] = pb[i];
		p[i] = excrt(M, C, 2);
		if (p[i] != -1)sg--;
	}
	ll L = 1, R = inf;
	while (L < R) {
		ll mid = (L + R) / 2;
		if (cal(mid) >= k)R = mid;
		else L = mid + 1;
	}
	printf("%lld\n", L);
	return 0;
}