题解 | 武汉工程大学第七届ACM程序设计竞赛同步赛

B

。

#include "bits/stdc++.h"

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    cin >> s >> t;
    cout << (s == t ? "AC" : "WA") << '\n';
    
    return 0;
}

C

。

#include "bits/stdc++.h"

using namespace std;

constexpr int N = 1E6;
int c[N + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    int g = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        c[x]++;
        g = gcd(g, x);

        if (5 * g <= N) {
            cout << min({c[g] / 8, c[g * 2] / 3, c[g * 3] / 2, c[g * 5]});
        } else {
            cout << 0;
        }
        cout << " \n"[i == n - 1];
    }
    
    return 0;
}

D

考虑枚举 ，这里用到了组合数的知识。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

constexpr int N = 2E5, K = 1E6;

constexpr int P = 1000000007;
i64 power(i64 a, int b, int p = P) {
    i64 r = 1;
    for (; b > 0; b >>= 1, a = a * a % p) {
        if (b & 1) {
            r = r * a % p;
        }
    }
    return r;
}

i64 fac[N + 1], ifac[N + 1];

i64 C(int n, int m) {
    if (m < 0 || m > n || n < 0) {
        return 0;
    }
    return fac[n] * ifac[m] % P * ifac[n - m] % P;
}

int c[K + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % P;
    }
    ifac[n] = power(fac[n], P - 2);
    for (int i = n - 1; i >= 0; i--) {
        ifac[i] = ifac[i + 1] * (i + 1) % P;
    }

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        c[a[i]]++;
    }

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    n = a.size();

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + C(c[a[i]], 8)) % P;
        for (int k = 2 * a[i]; k <= K; k += a[i]) {
            ans = (ans + C(c[a[i]], 6 + k / a[i]) * c[k] % P) % P;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

F

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    i64 x, y;
    cin >> n >> x >> y;
    
    vector<i64> a(n);
    unordered_map<i64, vector<int>> pos;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }

    for (int i = 0; i < n; i++) {
        i64 k = x / a[i]; 
        if (k > 0 && !(y % k)) {
            i64 d = y / k;
            if (a[i] + d > 0) {
                i64 aim = a[i] + d;
                if (pos.find(aim) != pos.end()) {
                    auto it = lower_bound(pos[aim].begin(), pos[aim].end(), i + 1);
                    if (it != pos[aim].end()) {
                        cout << i + 1 << ' ' << *it + 1 << '\n';
                        return 0;
                    }
                }
            }
        }
    }
    cout << "NO\n";

    return 0;
}

I

答案为 ，这里使用了快速幂。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

constexpr int P = 998244353;
i64 power(i64 a, int b, int p = P) {
    i64 r = 1;
    for (; b > 0; b >>= 1, a = a * a % p) {
        if (b & 1) {
            r = r * a % p;
        }
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    string s;
    cin >> n >> s;
    cout << (power(2, n) - 1 + P) % P * power(2, P - 2) % P << '\n';
    
    return 0;
}

J

。

#include "bits/stdc++.h"

using namespace std;
using i64 = int64_t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> w(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> val(n), dep(n);
    i64 ans = 0;
    auto dfs = [&](auto dfs, int x, int p, i64 sum) -> void {
        val[dep[x]] = x + 1;
        ans += sum * w[x];
        
        for (int y : adj[x]) {
            if (y != p) {
                dep[y] = dep[x] + 1;
                i64 sum0 = sum + y + 1 - (dep[x] >= k ? val[dep[x] - k] : 0);
                
                dfs(dfs, y, x, sum0);
            } 
        }
    };
    
    dfs(dfs, 0, 0, 1);
    
    cout << ans << '\n';
    
    return 0;
}