挑战赛#10正经题解（C++）

userId_undefined

复仇者_零

尊贵铂金

2024-10-02 13:24:56

发布于：浙江

6阅读
0回复
0点赞

t1 题解（位运算）：

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    int c = a & b;
    int d = a | b;
    int e = a ^ b;

    int result = c + d + e;
    cout << result << endl;

    return 0;
}

t2 题解（循环控制）：

#include <iostream>
#include <vector>
using namespace std;

int min_steps(int x, int k) {
    int steps = 0;
    int current = 0;

    while (current < x) {
        for (int i = x - current; i > 0; --i) {
            if (i % k != 0) {
                current += i;
                ++steps;
                break;
            }
        }
    }

    return steps;
}

int main() {
    int t;
    cin >> t;
    vector<int> results;

    for (int i = 0; i < t; ++i) {
        int x, k;
        cin >> x >> k;
        results.push_back(min_steps(x, k));
    }

    for (int result : results) {
        cout << result << endl;
    }

    return 0;
}

t3 题解（质数判定）：

#include <iostream>
#include <cmath>
using namespace std;

bool is_prime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

bool is_prime_power(int n) {
    if (n == 1) return true;
    for (int p = 2; p <= sqrt(n); ++p) {
        if (is_prime(p)) {
            int power = p;
            while (power < n) power *= p;
            if (power == n) return true;
        }
    }
    return false;
}

int main() {
    int t;
    cin >> t;

    for (int i = 0; i < t; ++i) {
        int n;
        cin >> n;
        if (n == 1 || is_prime(n) || is_prime_power(n)) {
            cout << "No" << endl;
        } else {
            cout << "Yes" << endl;
        }
    }

    return 0;
}

t4 题解（阶乘与排序）：

#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 998244353
using namespace std;

long long factorial(int n) {
    long long result = 1;
    for (int i = 1; i <= n; ++i) {
        result = (result * i) % MOD;
    }
    return result;
}

long long solve(int n, vector<int>& a) {
    sort(a.begin(), a.end());
    long long result = 1;
    for (int i = 0; i < n; ++i) {
        result = (result * (a[i] - i)) % MOD;
    }
    return result;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        cout << solve(n, a) << endl;
    }

    return 0;
}

t5 题解（时间间隔计算）：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> times(n);

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

    vector<int> end_times(n);
    for (int i = 0; i < n; ++i) {
        end_times[i] = times[i] + 1;
    }

    if (k >= n) {
        cout << n << endl;
        return 0;
    }

    vector<int> gaps(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        gaps[i] = times[i + 1] - end_times[i];
    }

    sort(gaps.begin(), gaps.end());
    int total_time = end_times[n - 1] - times[0];

    for (int i = 0; i < k - 1; ++i) {
        total_time -= gaps[n - 2 - i];
    }

    cout << total_time << endl;

    return 0;
}

t6 题解（线段树）：

#include <iostream>
#include <vector>
#include <map>
#define MOD 998244353
using namespace std;

class BIT {
public:
    int n;
    vector<long long> w;

    BIT(int n) : n(n), w(n + 1, 0) {}

    void add(int x, long long k) {
        k %= MOD;
        if (k < 0) k += MOD;
        while (x <= n) {
            w[x] = (w[x] + k) % MOD;
            x += x & -x;
        }
    }

    void update_range(int x, int y, long long k) {
        add(x, k);
        add(y + 1, -k);
    }

    long long query(int x) {
        long long ans = 0;
        while (x > 0) {
            ans = (ans + w[x]) % MOD;
            x -= x & -x;
        }
        return ans;
    }
};

long long qpow(long long x, long long y) {
    x %= MOD;
    if (y == 0) return 1;
    long long ans = 1;
    while (y) {
        if (y & 1) ans = (ans * x) % MOD;
        x = (x * x) % MOD;
        y >>= 1;
    }
    return ans;
}

void dfs(int u, int fa, vector<int>& d, vector<int>& sz, vector<int>& dfn, int& cnt, const map<int, vector<int>>& to) {
    d[u] = d[fa] + 1;
    sz[u] = 1;
    dfn[u] = cnt++;
    for (int v : to.at(u)) {
        if (v == fa) continue;
        dfs(v, u, d, sz, dfn, cnt, to);
        sz[u] += sz[v];
    }
}

int main() {
    int n, m, a;
    cin >> n >> m >> a;

    BIT Q(n + 1);
    map<int, vector<int>> to;
    vector<int> d(n + 1, -1), sz(n + 1, 0), dfn(n + 1, 0);
    int cnt = 1;

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

    dfs(1, 0, d, sz, dfn, cnt, to);

    for (int i = 0; i < m; ++i) {
        int opt, v;
        cin >> opt >> v;
        if (opt == 1) {
            int x;
            cin >> x;
            Q.update_range(dfn[v], dfn[v] + sz[v] - 1, qpow(a, x - d[v]));
        } else {
            cout << (Q.query(dfn[v]) * qpow(a, d[v]) % MOD + MOD) % MOD << endl;
        }
    }

    return 0;
}

python题解链接：https://www.acgo.cn/discuss/study/28753

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论