http://codeforces.com/contest/1500
A. Going Home
题意:给定一个数列 a,求四个不同的位置 x,y,z,w 满足 ax+ay=az+aw。(1≤ai≤2.5⋅106)
暴力枚举+复杂度计算
如果是普通题目,复杂度至少是 O(n2),肯定不行。
但是发现这个数列元素很小,两个元素的和最多只有 5×106。
直接暴力枚举 ai,aj,如果之前出现过 (x,y) 满足 ax+ay=ai+aj,则得到答案。
注意到 ai+aj≤5×106,则由鸽笼原理得到在最多 5×106 次枚举后一定能得到两组相同的和。
当然,上面是在 (i,j),(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
题意:给定长为 n 的数列 a,长为 m 的数列 b,每个数字在每个数列中最多出现一次。第 i 天分别从这两个循环数列中拿第 i 个数,问最少在第几天遇到第 k 次拿到两个不同的数字。1≤n,m≤500000,1≤k≤1012,1≤ai,bi≤2⋅max(n,m)
二分+扩展中国剩余定理
很关键的一点在于每个数在一个数列中最多出现一次。
最少在第几天遇到第 k 次拿到两个不同的数字,显然要二分答案。
则现在需要求在前 x 天有几次拿到两个不同的数。可以逆向思考变成求有几次拿到两个相同的数。
假设颜色 c 在 a 中的位置为 pa[c],在 b 中的位置为 pb[c],在第 t,(t<lcm(n,m)) 天同时选中 pa[c],pb[c]。则有
{t=pa[c](modn)t=pb[c](modm)
由于 n,m 不一定互质,所以excrt求。
之后对于给定的 x 天,先求出 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; }
|