天梯赛 L2

链表去重 02

#include <bits/stdc++.h>
using namespace std;
map<string, pair<int, string>> mp;
map<int, bool> vis;
struct node {
    string idx;
    int val;
    string nxt;
};
vector<node> nw, del;
void deal(vector<node> &a) {
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        if (i != n - 1)
            a[i].nxt = a[i + 1].idx;
        else
            a[i].nxt = "-1";
    }
    for (int i = 0; i < n; ++i)
        cout << a[i].idx << ' ' << a[i].val << ' ' << a[i].nxt << '\n';
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    string startAddress;
    int n;
    cin >> startAddress >> n;
    string nowAddress, nxtAddress;
    int val;
    for (int i = 1; i <= n; ++i) {
        cin >> nowAddress >> val >> nxtAddress;
        mp[nowAddress] = make_pair(val, nxtAddress);
    }
    nowAddress = startAddress;
    while (nowAddress != "-1") {
        node x = {nowAddress, mp[nowAddress].first, mp[nowAddress].second};
        if (vis[abs(mp[nowAddress].first)])  // delete
            del.emplace_back(x);
        else {  // add new
            nw.emplace_back(x);
            vis[abs(mp[nowAddress].first)] = 1;
        }
        nowAddress = mp[nowAddress].second;
    }
    deal(nw);
    deal(del);
    return 0;
}

月饼 03

#include <bits/stdc++.h>
using namespace std;
struct node {
    double num;
    double price;
    double singlePrice;
} a[1005];
int main() {
    int n;
    double m;
    scanf("%d%lf", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lf", &a[i].num);
    for (int i = 1; i <= n; ++i) scanf("%lf", &a[i].price);
    for (int i = 1; i <= n; ++i) a[i].singlePrice = a[i].price * 1.0 / a[i].num;
    sort(a + 1, a + 1 + n,
         [&](node x, node y) { return x.singlePrice > y.singlePrice; });
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (m > a[i].num)
            ans += a[i].price, m -= a[i].num;
        else {
            ans += m * a[i].singlePrice;
            break;
        }
    }
    printf("%.2lf\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
struct node {
    int num;
    int price;
} a[1005];
char in[] = "10.in";
char out[] = "10.out";
int main() {
    for (int T = 1; T <= 100; ++T) {
        if (T < 10) {
            in[1] = out[1] = '0' + T;
            freopen(in + 1, "r", stdin);
            freopen(out + 1, "w", stdout);
        } else if (T < 100) {
            in[0] = out[0] = '0' + T / 10;
            in[1] = out[1] = '0' + T % 10;
            freopen(in, "r", stdin);
            freopen(out, "w", stdout);
        } else {
            freopen("100.in", "r", stdin);
            freopen("100.out", "w", stdout);
        }
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i].num);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i].price);
        sort(a + 1, a + 1 + n,
             [&](node x, node y) { return x.num * y.price > y.num * x.price; });
        double ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (m > a[i].num)
                ans += a[i].price, m -= a[i].num;
            else {
                ans += 1.0 * m * a[i].price / a[i].price;
                break;
            }
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}

树的遍历

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld%c", (x), cnt == n ? '\n' : ' ')
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5+7;
ll mid[N], post[N], tr[N << 2], n, p = 0;
void build(int i, int L, int R) {
    tr[i] = post[++p];
    int k = L;
    while (k <= R) {
        if (mid[k] == post[p]) break;
        ++k;
    }
    if (k < R) build(i * 2 + 1, k + 1, R);
    if (k > L) build(i * 2, L, k - 1);
}
int main() {
    sc(n);
    rep(i, 1, n) sc(post[n + 1 - i]);  // rt R L
    rep(i, 1, n) sc(mid[i]);           // L rt R
    build(1, 1, n);
    for (int i = 1, cnt = 1; cnt <= n; ++i)
        if (tr[i]) pr(tr[i]), ++cnt;
    return 0;
}

集合相似度

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef int ll;
const int N = 1e4 + 7;
ll a[55][N];
unordered_set<ll> st, vis;
int main() {
    ll n, q, x, y;
    sc(n);
    rep(i, 1, n) {
        sc(a[i][0]);
        rep(j, 1, a[i][0]) sc(a[i][j]);
    }
    sc(q);
    while (q--) {
        scanf("%d%d", &x, &y);
        st.clear();
        vis.clear();
        ll up = 0;
        rep(i, 1, a[x][0]) st.insert(a[x][i]);
        rep(i, 1, a[y][0]) {
            if (st.count(a[y][i]) && !vis.count(a[y][i])) ++up;
            vis.insert(a[y][i]);
        }
        rep(i, 1, a[y][0]) st.insert(a[y][i]);
        ll down = st.size();
        printf("%.2lf%%\n", 100.0 * up / down);
    }
    return 0;
}