比賽連結: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\)。
否則無法構造。
代碼
#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\) 天,最少需要買幾集。
暴力。
#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\) 的滑動視窗即可。
#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\) 是否在這個範圍内即可。
#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))\) 是否存在即可。
#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;
}