C++ 算法竞赛、07 周赛篇 | AcWing 第120场周赛
AcWing 第120场周赛
5146 最大GCD
不难发现,最大公约数的条件是 \(GCD(\lfloor \frac{n}{2} \rfloor ,\lfloor \frac{n}{2} \rfloor * 2)\)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
cout << GCD(n >> 1 << 1, n >> 1) << endl;
}
return 0;
}
5174⭐数量
不含 4 和 7 以外 \(\Rightarrow\) 只含 4 和 7,每位只有两种情况,最多到 1e9,即 \(2^9\) 个情况,爆搜枚举即可
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
int ans;
void dfs(LL x) {
if (x > n) return;
if (x) ans++;
dfs(x * 10 + 4);
dfs(x * 10 + 7);
}
int main() {
cin >> n;
dfs(0);
cout << ans << endl;
return 0;
}
5148⭐字符串匹配
顺序随便调。统计两个字符串每个大小写字母出现多少次,然后每个字母独立看
- A 的完美匹配数量就是 两计数数组 A 字母数量最小值
- 两计数数组中删除 A 的完美匹配数量
- 此时,两计数数组中,A+a 字母数量最小值就是 不完美匹配数量
#include <bits/stdc++.h>
using namespace std;
int const N = 256;
int c1[N], c2[N];
int main() {
string s, t;
cin >> s >> t;
for (int i = 0; i < s.size(); i++) c1[s[i]]++;
for (int i = 0; i < t.size(); i++) c2[t[i]]++;
int bestCount = 0, secondCount = 0;
for (int i = 'A'; i <= 'Z'; i++) {
int lower = i + 32;
int min_A = min(c1[i], c2[i]);
int min_a = min(c1[lower], c2[lower]);
bestCount += min_A;
bestCount += min_a;
c1[i] -= min_A;
c1[lower] -= min_a;
c2[i] -= min_A;
c2[lower] -= min_a;
secondCount += min(c1[i] + c1[lower], c2[i] + c2[lower]);
}
cout << bestCount << " " << secondCount;
return 0;
}
也可以分开写
#include <bits/stdc++.h>
using namespace std;
int const N = 256;
int c1[N], c2[N];
int main() {
string s, t;
cin >> s >> t;
for (int i = 0; i < s.size(); i++) c1[s[i]]++;
for (int i = 0; i < t.size(); i++) c2[t[i]]++;
int bestCount = 0, secondCount = 0;
for (int i = 0; i < N; i++) {
int t = min(c1[i], c2[i]);
bestCount += t;
c1[i] -= t, c2[i] -= t;
}
for (int i = 'a'; i <= 'z'; i++) {
secondCount += min(c1[i] + c1[i - 32], c2[i] + c2[i - 32]);
}
cout << bestCount << " " << secondCount;
return 0;
}