L2训练3部分题目

[TOC]

7-16 家庭房产

#include <bits/stdc++.h>
using namespace std;
 
// 并查集
struct DisjointSet {
    vector<int> p;
    DisjointSet(int n = 1e6) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        x < y ? p[y] = x : p[x] = y; // 要保存家庭成员的最小编号，按照编号小的作为父节点合并
    }
};
struct Node {
    int id, n;          // 家庭成员的最小编号 家庭人口数
    double house, area; // 人均房产套数 人均房产面积
    bool operator<(const Node &t) { return area != t.area ? area > t.area : id < t.id; }
};
int main() {
    DisjointSet ds;
    set<int> peo;                      // 保存每一个人的编号
    map<int, pair<int, int>> property; // 保存每一个人的房产
    int n;
    cin >> n;
    while (n--) {
        int x, fa, ma, k, son, a, b;
        cin >> x >> fa >> ma >> k;
        // 输入之后，保存每个人的编号，并把家庭成员[自己，父，母，孩子]连接在一个并查集里
        peo.insert(x);
        if (fa != -1) {
            ds.merge(x, fa);
            peo.insert(fa);
        }
        if (ma != -1) {
            ds.merge(x, ma);
            peo.insert(ma);
        }
        while (k--) {
            cin >> son;
            ds.merge(x, son);
            peo.insert(son);
        }
        cin >> a >> b;
        property[x] = {a, b};
    }
    map<int, vector<int>> family; // 家庭成员的最小编号--家庭成员
    for (int i : peo) {
        family[ds.find(i)].push_back(i); // find(i)为i的家庭中的最小编号，把i加入这个家庭
    }
    vector<Node> ans;
    for (auto &[id, people] : family) {
        double a = 0, b = 0;
        // people为这和家庭的所有成员，累加他们的所有资产，并计算平均值
        for (int x : people) {
            a += property[x].first;
            b += property[x].second;
        }
        a /= people.size();
        b /= people.size();
        ans.push_back(Node{id, int(people.size()), a, b}); // 家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto &e : ans) {
        printf("%04d %d %.3lf %.3lf\n", e.id, e.n, e.house, e.area);
    }
    return 0;
}

7-23 图着色问题

#include <bits/stdc++.h>
using namespace std;
 
using Edge = pair<int, int>;
int n, m, k, T;
vector<Edge> G; // 存储边目录
 
int main() {
    cin >> n >> m >> k;
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        G.push_back({u, v});
    }
    cin >> T;
    while (T--) {
        vector<int> color(n + 1);
        set<int> st;
        for (int i = 1; i <= n; i++) {
            cin >> color[i];
            st.insert(color[i]);
        }
        // 一个匿名函数
        auto OK = [&]() {
            // 图染色数不是k，则方案不正确
            if (st.size() != k)
                return false;
            for (auto &[u, v] : G)
                if (color[u] == color[v]) // 存在两个相邻顶点具有同一种颜色，方案不正确
                    return false;
            return true;
        };
        puts(OK() ? "Yes" : "No");
    }
}

7-30 深入虎穴

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> G[N];
bool vis[N];
int indeg[N], dep[N]; // dep[u]为u结点到起点距离，也就是u的深度
int n, m;
int mx, idx;
 
void bfs(int s) {
    queue<int> q;
    q.push(s);
    dep[s] = 1;
    mx = 1, idx = s; // 存储最深结点编号以及它的深度
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int v : G[u]) {
            q.push(v);
            dep[v] = dep[u] + 1; // bfs搜索，子节点的深度为父节点的深度+1
            if (mx < dep[v])
                mx = dep[v], idx = v; // 更新最深结点
        }
    }
}
int main() {
    cin >> n;
    for (int u = 1; u <= n; u++) {
        int sz, v;
        cin >> sz;
        while (sz--) {
            cin >> v;
            indeg[v]++;
            G[u].push_back(v);
        }
    }
    int s = find(indeg + 1, indeg + n + 1, 0) - indeg; // 查找入度为0的结点，即为起点
    bfs(s);
    cout << idx;
}

7-86 宿舍谁最高？

#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    string name;
    int height, weight;
};
map<int, Node> mp;
int main() {
    int n;
    cin >> n;
    while (n--) {
        int num, height, weight;
        string name;
        cin >> num >> name >> height >> weight;
        // 如果这个宿舍还没往里面加人，或者宿舍里这个人的身高不如当前这个人高，更新这个宿舍的最高人
        if (!mp.count(num) || mp[num].height < height)
            mp[num] = Node{name, height, weight};
    }
    // map按照键值的大小排序，也就是按照宿舍号升序排
    for (auto &[k, e] : mp) {
        printf("%06d %s %d %d\n", k, e.name.c_str(), e.height, e.weight);
    }
    return 0;
}

7-93 秀恩爱分得快

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
 
int n, m;
double G[N][N];
vector<int> peo[N]; // 存储每个人在哪些照片出现过
vector<int> photo[N]; // 存储每张照片有哪些人
 
bool sex[N]; // 性别
string id[N]; // 编号
 
// 获取每个人的编号
int getId(string &s) {
    int x = abs(stoi(s));
    sex[x] = s[0] == '-';
    id[x] = s;
    return x;
}
int main() {
    cin >> n >> m;
    for (int i = 1, k; i <= m; i++) {
        cin >> k;
        for (int j = 0; j < k; j++) {
            string num;
            cin >> num;
            int x = getId(num); 
            peo[x].push_back(i);
            photo[i].push_back(x); // 每插入一个人，双向地记录人与照片、照片与人的关系
        }
    }
    string A, B;
    cin >> A >> B;
    int a = getId(A), b = getId(B);
	// 计算用户 A 和 B 的异性朋友的亲密度
    for (int u : {a, b})
        for (int i : peo[u])
            for (int v : photo[i]) 
                if (sex[u] != sex[v])
                    G[u][v] += 1.0 / photo[i].size();
	// 查找最亲密的异性朋友的亲密度
    double mxa = 0, mxb = 0;
    for (int i = 0; i < n; i++)
        if (sex[i] != sex[a])
            mxa = max(mxa, G[a][i]);
    for (int i = 0; i < n; i++)
        if (sex[i] != sex[b])
            mxb = max(mxb, G[b][i]);
    // 如果 A 和 B 正是彼此亲密度最高的一对，则只输出他们的编号
    if (G[a][b] == mxa && G[b][a] == mxb) {
        cout << id[a] << " " << id[b] << endl;
        return 0;
    } else { // 按他们编号的绝对值递增输出
        for (int i = 0; i < n; ++i)
            if (G[a][i] == mxa && sex[a] != sex[i])
                cout << id[a] << " " << id[i] << endl;
        for (int i = 0; i < n; ++i)
            if (G[b][i] == mxb && sex[b] != sex[i])
                cout << id[b] << " " << id[i] << endl;
    }
    return 0;
}