AcWing 第120場周賽

競賽 - AcWing

5146 最大GCD

5146. 最大GCD - AcWing題庫

不難發(fā)現(xiàn)，最大公約數(shù)的條件是 \(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?數(shù)量

5147. 數(shù)量 - AcWing題庫

不含 4 和 7 以外 \(\Rightarrow\) 只含 4 和 7，每位只有兩種情況，最多到 1e9，即 \(2^9\) 個(gè)情況，爆搜枚舉即可

#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?字符串匹配

AcWing 5148. 字符串匹配 - AcWing

順序隨便調(diào)。統(tǒng)計(jì)兩個(gè)字符串每個(gè)大小寫字母出現(xiàn)多少次，然后每個(gè)字母獨(dú)立看

1. A 的完美匹配數(shù)量就是 兩計(jì)數(shù)數(shù)組 A 字母數(shù)量最小值
2. 兩計(jì)數(shù)數(shù)組中刪除 A 的完美匹配數(shù)量
3. 此時(shí)，兩計(jì)數(shù)數(shù)組中，A+a 字母數(shù)量最小值就是 不完美匹配數(shù)量

#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;
}

也可以分開寫文章來源地址http://www.zghlxwxcb.cn/news/detail-709620.html

#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;
}

到了這里，關(guān)于C++ 算法競賽、07 周賽篇 | AcWing 第120場周賽的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！