比赛链接:Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2)
官方题解:Technocup 2020 — Elimination Round 2 + Codeforces Round 596: analysis
A. Forgetting Things 题意 有两个数 $a$ 和 $b$,给定 $a$ 的首位 $d_a$ 和 $b$ 的首位 $d_b$,问能否构造出 $a$ 和 $b$,满足 $a + 1 = b$
思路 如果 $a = b$,构造 $a1$,$b2$。
如果 $a + 1 = b$,构造 $a9$,$b0$。
如果 $a = 9$,$b = 1$,构造 $9$,$10$。
否则无法构造。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <bits/stdc++.h> using namespace std ;typedef long long ll;int main () { int n, m; cin >> n >> m; if (n == m) { printf ("%d1 %d2\n" , n, m); } else if (n == 9 && m == 1 ) { printf ("9 10\n" ); } else if (n + 1 == m) { printf ("%d9 %d0\n" , n, m); } else { printf ("-1\n" ); } return 0 ; }
B1. TV Subscriptions (Easy Version) 题意 某电视节目有 $k$ 集,告诉你 $n$ 天每天播放哪一集,现在要看连续 $d$ 天,最少需要买几集。
思路 暴力。
代码 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 #include <bits/stdc++.h> using namespace std ; int a[110 ]; int main () { ios::sync_with_stdio(false ); cin .tie(0 ); int T; cin >> T; while (T--) { int n, k, d; cin >> n >> k >> d; for (int i = 0 ; i < n; ++i) { cin >> a[i]; } int ans = 0x3f3f3f3f ; map <int , int > mp; for (int i = 0 ; i < n - d + 1 ; ++i) { mp.clear(); for (int j = 0 ; j < d; ++j) { mp[a[i + j]]++; } int tmp = mp.size(); ans = min(ans, tmp); } int tmp = mp.size(); ans = min(ans, tmp); cout << ans << endl ; } return 0 ; }
B2. TV Subscriptions (Hard Version) 题意 与上一题相同,数据范围变大。
思路 维护一个长度为 $d$ 的滑动窗口即可。
代码 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 #include <bits/stdc++.h> using namespace std ;const int maxn = 2e5 + 10 ; int a[maxn];int mp[maxn * 5 ]; int main () { ios::sync_with_stdio(false ); cin .tie(0 ); int T; cin >> T; while (T--) { memset (mp, 0 , sizeof (mp)); int n, k, d; cin >> n >> k >> d; for (int i = 0 ; i < n; ++i) { cin >> a[i]; } int ans = 0x3f3f3f3f ; int tmp = 0 ; for (int i = 0 ; i < n; ++i) { if (i < d) { if (mp[a[i]] == 0 ) ++tmp; mp[a[i]]++; } else { ans = min(ans, tmp); mp[a[i - d]]--; if (mp[a[i - d]] == 0 ) --tmp; if (mp[a[i]] == 0 ) ++tmp; mp[a[i]]++; } } ans = min(ans, tmp); cout << ans << endl ; } return 0 ; }
C. p-binary 题意 给定两个整数 $n$ 和 $p$,将 $n$ 分解成若干个 $2^x + p$ 的和,求最少需要几项。如 $n=24,p=-1$,则 $24 = (2^4 - 1) + (2^2 - 1) + (2^2 - 1) + (2^2 - 1)$,所以答案为 $4$。
思路 枚举项数 $i$,$2^{31}>1e9$,所以不超过 $31$ 项。然后将 $n$ 减去 $p*i$,$n - p\times i$ 最多有 $n - p\times i$ 项 (每项都为 $2^0$),最少项数为二进制分解后二进制中为 $1$ 的个数,判断 $i$ 是否在这个范围内即可。
代码 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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;int main () { int n, p; int ans = -1 , tmp = 0 ; scanf ("%d%d" , &n, &p); for (int i = 1 ; i <= 31 ; ++i) { int cnt = 0 ; tmp = n - p * i; while (tmp > 0 ) { if (tmp & 1 ) { cnt++; } tmp >>= 1 ; } if (cnt <= i && i <= n - p * i){ ans = i; break ; } } printf ("%d\n" , ans); return 0 ; }
D. Power Products 题意 给定 $n$ 个正整数 $a_1, a_2, …, a_n$,和一个整数 $k\ge 2$,问有多少对 $a_i, a_j$ 满足 $a_i\cdot a_j = x^k$,$x$ 是整数。
思路 将每个数质因数分解,将每个因子和模 $k$ 后的数量存入 $map$,然后找所需的剩余因子个数满足的是否存在。
比如 $24 = 2^3 * 3$,设 $k = 2$,则 $map$ 中存 $((2, 3\mod k), (3, 1 \mod k))$,$((2, 1), (3, 1))$。然后在 $map$ 中找 $((2,k - 1), (3, k - 1))$ 是否存在即可。
代码 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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 1e5 + 10 ; ll a[maxn]; int main () { ios::sync_with_stdio(false ); cin .tie(0 ); ll n, k; cin >> n >> k; map <vector <pair<ll, ll> >, ll> mp; ll ans = 0 ; for (int i = 0 ; i < n; ++i) { cin >> a[i]; vector <pair<ll, ll> > vt; for (int j = 2 ; j <= a[i] / j; ++j) { int num = 0 ; if (a[i] % j == 0 ) { while (a[i] % j == 0 ) { ++num; a[i] /= j; } } if (num % k) { vt.push_back({j, num % k}); } } if (a[i] > 1 ) vt.push_back({a[i], 1 % k}); vector <pair<ll, ll> > vt2; for (int j = 0 ; j < vt.size(); ++j) { vt2.push_back({vt[j].first, k - vt[j].second}); } ans += mp[vt2]; mp[vt]++; } cout << ans << endl ; return 0 ; }