饿了么笔试题解 8月15日

第一题：n为奇数输出n个1，n为偶数输出n-1个0即可：
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t --) {
        int n;
        cin >> n;
        if (n & 1) {
            for (int i = 0; i < n; i ++) {
                cout << 1 << " ";
            }
            cout << '\n';
        } else {
            for (int i = 0; i < n - 1; i ++) {
                cout << 1 << " ";
            }
            cout << 0 << '\n';
        }
    }
}

第二题：如果你有n个长度相同的木棍，那么他们组成正m边形的组合是C(n，m)个，C是组合数，计下数就可以了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int p = 998244353;
const int N = 5e3 + 10;
int h[N], rh[N];
int C(int n, int m) {
    if (n < m) return 0;
    return h[n] * rh[m] % p * rh[n - m] % p;
}

int qs(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
signed main() {
    h[0] = rh[0] = 1;
    for (int i = 1; i < N ; i ++) {
        h[i] = h[i - 1] * i % p;
        rh[i] = qs(h[i], p - 2);
    }
    int n;
    cin >> n;
    map<int, int> mp;
    for (int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        mp[x] ++;
    }
    for (int i = 3; i <= n; i ++) {
        int res = 0;
        for (auto& it : mp) {
            res = (res + C(it.second, i)) % p;
        }
        cout << res << ' ';
    }
}

3，最小生成树模板题，注意处理一下正边
#include <cmath>
# include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int p[N];
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int main() {
    int n, m;
    cin >> n >> m;
    priority_queue<pair<int, pair<int, int>>> pq;
    for (int i = 1; i <= n; i ++) p[i] = i;
    for (int i = 1 ; i <= m; i ++) {
        int u, v, x;
        cin >> u >> v >> x;
        pq.push({x, {u, v}});
    }
    long long res = 0;
    while (pq.size() > 0) {
        auto t = pq.top();
        pq.pop();
        int u = t.second.first;
        int v = t.second.second;
        int x = t.first;
        if (x >= 0) {
            res += x;
            p[find(u)] = find(v);
        } else if (find(u) != find(v)) {
            res += x;
            p[find(u)] = find(v);
        }

    }
    cout << res << '\n';

#笔试#