团体程序设计天梯赛 L2 题目合集

迷南。 2022-12-24 00:52 204阅读 0赞

# 前言 #

发现自己还能再参加一次天梯赛，在高兴之余，决定把在赛前将所有的天梯赛真题过一遍，希望自己可以取得理想的成绩。目前 L1 的题目已经刷完，打算在赛前刷完 L2 的题目。

本来想 L2 的题目都写个相对详细的题解的，但是由于时间已经很紧张了，就只能像来记录 L1题目的形式来 L2 的题解了，让我们都好好加油吧。

### 文章目录 ###

*  前言
 *  L2-001 紧急救援
 *  L2-002 链表去重
 *  L2-003 月饼
 *  L2-004 这是二叉搜索树吗?
 *  L2-005 集合相似度
 *  L2-006 树的遍历
 *  L2-007 家庭房产
 *  L2-008 最长对称子串
 *  L2-009 抢红包
 *  L2-010 排座位
 *  L2-011 玩转二叉树
 *  L2-012 关于堆的判断
 *  L2-013 红色警报
 *  L2-014 列车调度
 *  L2-015 互评成绩
 *  L2-016 愿天下有情人都是失散多年的兄妹
 *  L2-017 人以群分
 *  L2-018 多项式A除以B
 *  L2-019 悄悄关注
 *  L2-020 功夫传人
 *  L2-021 点赞狂魔
 *  L2-022 重排链表
 *  L2-023 图着色问题
 *  L2-024 部落
 *  L2-025 分而治之
 *  L2-026 小字辈
 *  L2-027 名人堂与代金券
 *  L2-028 秀恩爱分得快
 *  L2-029 特立独行的幸福
 *  L2-030 冰岛人
 *  L2-031 深入虎穴
 *  L2-032 彩虹瓶

# L2-001 紧急救援 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int inf = 0x3f3f3f;
    const int maxn =550;
    int n, m, s, d;
    
    int w[maxn], sum[maxn], total[maxn];
    int dis[maxn], vis[maxn], path[maxn];
    typedef pair<int, int> pii;
    vector<pii> E[maxn];
    
    void dijstra(int s) { 
        memset(vis, 0, sizeof(vis));
        priority_queue<pii, vector<pii>, greater<pii> > q;
        for (int i = 0; i < n; i++) dis[i] = inf;
        dis[s] = 0;
        sum[s] = w[s];
        total[s] = 1;
        q.push(pii(dis[s], s));
        while (!q.empty()) { 
            int u = q.top().second;
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (int i = 0; i < E[u].size(); i++) { 
                int v = E[u][i].first;
                if (dis[v] > dis[u] + E[u][i].second) { 
                    dis[v] = dis[u] + E[u][i].second;
                    sum[v] = sum[u] + w[v];
                    total[v] = total[u];
                    path[v] = u;
                    q.push(pii(dis[v], v));
                } else if (dis[v] == dis[u] + E[u][i].second) { 
                    if (sum[v] < sum[u] + w[v]) { 
                        sum[v] = sum[u] + w[v];
                        path[v] = u;
                    }
                    total[v] += total[u];
                }
            }
        }
    }
    
    void output(int s, int d) { 
        if (s == d) { 
            printf("%d", s);
            return ;
        } else { 
            output(path[s], d);
            printf(" %d", s);
        }
    }
    
    
    int main()
    { 
        scanf("%d %d %d %d", &n, &m, &s, &d);
        for (int i = 0; i < n; i++) scanf("%d", &w[i]);
        for (int i = 1; i <= m; i++) { 
            int x, y, t;
            scanf("%d %d %d", &x, &y, &t);
            E[x].push_back(pair<int, int>(y, t));
            E[y].push_back(pair<int, int>(x, t));
        }
        dijstra(s);
        printf("%d %d\n", total[d], sum[d]);
        output(d, s);
        return 0;
    }

# L2-002 链表去重 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1e5 + 10;
    int n, cnt;
    int one, s, pre;
    /** * lb用于存储原始链表 * re用于存储原始链表中的重复节点 */
    pair<int, int> lb[maxn];
    pair<int, int> re[maxn];
    set<int> vis;
    
    int main()
    { 
        cin >> one >> n;
        for (int i = 1; i <= n; i++) { 
            int address, num, next;
            cin >> address >> num >> next;
            lb[address] = make_pair(num, next);
        }
        cnt = 0;
        for (s = one; s != -1; s = lb[s].second) { 
            int num = lb[s].first;
            if (!vis.count(abs(num))) { 
                vis.insert(abs(num));
                pre = s;
            } else { 
                //链表删除重复节点操作
                lb[pre].second = lb[s].second;
                //将删除的节点存到另一条链表
                re[cnt].first = num;
                re[cnt].second = s;
                cnt++;
            }
        }
    
        for (s = one; s != -1; s = lb[s].second) { 
            printf("%05d %d ", s, lb[s].first);
            if (lb[s].second != -1) printf("%05d\n", lb[s].second);
            else printf("-1\n");
        }
        for (int i = 0; i < cnt; i++) { 
            printf("%05d %d ", re[i].second ,re[i].first);
            if (i != cnt - 1) printf("%05d\n", re[i + 1].second);
            else printf("-1\n");
        }
        return 0;
    }

# L2-003 月饼 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1005;
    const double eps = 1e-10;
    
    struct Food { 
        double num, price;
        double pri;
    } f[maxn];
    
    
    bool cmp (const Food &A, const Food &B) { 
        return A.pri > B.pri;
    }
    
    int main()
    { 
        int n, need;
        scanf("%d %d", &n, &need);
        for (int i = 0; i < n; i++) scanf("%lf", &f[i].num);
        for (int i = 0; i < n; i++) { 
            scanf("%lf", &f[i].price);
            f[i].pri = f[i].price / f[i].num;
        }
        sort(f, f + n, cmp);
        double ans = 0.0;
        for (int i = 0; i < n; i++) { 
            if (f[i].num < need) { 
                ans += f[i].price;
                need -= f[i].num;
            } else { 
                ans += need * f[i].pri;
                break;
            }
        }
        printf("%.2f\n", ans);
        return 0;
    }

# L2-004 这是二叉搜索树吗? #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1e3 + 10;
    int n, flag;
    int a[maxn];
    vector<int> ans; // 存储后序遍历的结果
    
    /* 根据前序遍历的结果，后序遍历二叉搜索树 l: 二叉树的 r: 二叉树的 flag: 是否根据镜像的规则进行遍历 */
    void dfs(int l, int r, int flag) { 
        if (l > r) return ;
        int p1 = l + 1, p2 = r;
        // 确定左右子树的范围
        if (flag) { 
            while (p1 <= r && a[p1] >= a[l]) p1++;
            while (p2 > l && a[p2] < a[l]) p2--;
        } else { 
            while (p1 <= r && a[p1] < a[l]) p1++;
            while (p2 > l && a[p2] >= a[l]) p2--;
        }
        if (p1 - p2 != 1) return ;
        dfs(l + 1, p1 - 1);
        dfs(p2 + 1, r);
        ans.push_back(a[l]);
    }
    
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        dfs(1, n, flag);
        if (ans.size() != n) { 
            flag = 1;
            ans.clear();
            dfs(1, n, flag);
        }
        if (ans.size() != n) { 
            cout << "NO" << endl;
        } else { 
            cout << "YES" << endl;
            for (int i = 0; i < n; i++) { 
                cout << ans[i] << (i == n - 1 ? '\n' : ' ');
            }
        }
        return 0;
    }

# L2-005 集合相似度 #

#include <bits/stdc++.h>
    
    using namespace std;
    int n, m, t, k, a, b;
    const int maxn = 1e4 + 10;
    set<int> vis[maxn];
    int main()
    { 
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) { 
            scanf("%d", &m);
            while (m--) { 
                scanf("%d", &t);
                vis[i].insert(t);
            }
        }
        scanf("%d", &k);
        while (k--) { 
            scanf("%d %d", &a, &b);
            int cnt1 = vis[a].size(), cnt2 = vis[b].size(), cnt3 = 0;
            for (auto e : vis[a]) { 
                if (vis[b].count(e))
                    cnt3++;
            }
            printf("%.2f%\n", (double)cnt3 / (cnt1 + cnt2 - cnt3) * 100);
        }
        return 0;
    }

# L2-006 树的遍历 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 50;
    int n;
    /** * in_order[]表示中序遍历序列 * post_order[]表示后序遍历序列 * tree[]用于存储树形结构 * 其中，tree[i].first表示i节点左孩子编号，tree[i].second表示i号节点右孩子编号 */
    int in_order[maxn], post_order[maxn];
    pair<int, int> tree[maxn];
    /** * [la, ra]表示中序遍历序列的范围 * [lb, rb]表示后序遍历序列的范围 */
    int build(int la, int ra, int lb, int rb) { 
        if (la > ra || lb > rb) return 0;
        int rt = post_order[rb];
        //p表示根节点在中序遍历序列中的位置
        int p = la;
        while (in_order[p] != rt) p++;
        //cnt表示左子树的节点数
        int cnt = p - la;
        //根据已知量，求左右子树所在的遍历序列区间
        tree[rt].first = build(la, p - 1 , lb, lb + cnt - 1);
        tree[rt].second = build(p + 1, ra, lb + cnt, rb - 1);
        return rt;
    }
    
    /** * 利用bfs层序遍历二叉树 * @param root表示二叉树的根节点 */
    void bfs(int root) { 
        vector<int> ans;
        queue<int> q;
        q.push(root);
        while (!q.empty()) { 
            int node = q.front();
            q.pop();
            ans.push_back(node);
            if (tree[node].first) q.push(tree[node].first);
            if (tree[node].second) q.push(tree[node].second);
        }
        int len = ans.size();
        for (int i = 0; i < len; i++)
            cout << ans[i] << (i == len - 1 ? '\n' : ' ');
    }
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> post_order[i];
        for (int i = 1; i <= n; i++)
            cin >> in_order[i];
        int root = build(1, n, 1, n);
        bfs(root);
        return 0;
    }

# L2-007 家庭房产 #

#include <bits/stdc++.h>
    #include <unordered_set>
    using namespace std;
    const int maxn = 1e4 + 10;
    int n, id, fid, mid, k, cid, cnt;
    
    struct People { 
        double num, area;  // num 表示房产数、area 表示房产总面积
        bool flag = false; // 标记是否作为“编号”出现过
    } s[maxn];
    
    struct Answer { 
        int id, num;   // id 表示家庭成员的最小编号，num 表示家庭人口数
        double house, area; // house 表示人均房产套数，area 表示人均房产面积
    } ans[1005];
    
    int p[maxn], mark[maxn];
    unordered_set<int> vis;
    
    bool cmp(const Answer &A, const Answer &B) { 
        if (A.area == B.area) return A.id < B.id;
        else return A.area > B.area;
    }
    // 并查集初始化
    void init() { 
        for (int i = 1; i < maxn; i++) p[i] = i;
    }
    // 并查集查询
    int Find(int x) { 
        return p[x] == x ? x : p[x] = Find(p[x]);
    }
    // 并查集合并，保证 id 最小的人在根节点
    void Merge(int x, int y) { 
        int tx = Find(x);
        int ty = Find(y);
        if (tx != ty) { 
            if (tx < ty) p[ty] = tx;
            else p[tx] = ty;
        }
    }
    
    int main()
    { 
        init();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) { 
            scanf("%d %d %d", &id, &fid, &mid);
            vis.insert(id);
            if (fid != -1) { 
                Merge(id, fid);
                vis.insert(fid);
            }
            if (mid != -1) { 
                Merge(id, mid);
                vis.insert(mid);
            }
            scanf("%d", &k);
            for (int j = 1; j <= k; j++) { 
                scanf("%d", &cid);
                if (cid != -1) { 
                    Merge(id, cid);
                    vis.insert(cid);
                }
            }
            scanf("%lf %lf", &s[id].num, &s[id].area);
            s[id].flag = true;
        }
        for (auto i : vis) { 
            int t = Find(i); // 获取所在家庭的成员的最小编号
            if (!mark[t]) { 
                mark[t] = ++cnt; // mark[i] 用于标记i是否出现过，且记录i在ans数组未排序前的下标 
                ans[cnt].id = t;
            }
            ans[mark[t]].num++; // 统计家庭人口数
            if (s[i].flag) {  // flag 为 true 的人才有房产
                ans[mark[t]].house += s[i].num;
                ans[mark[t]].area += s[i].area;
            }
        }
       // 计算人均值
        for (int i = 1; i <= cnt; i++) { 
            ans[i].house /= ans[i].num;
            ans[i].area /= ans[i].num;
        }
        printf("%d\n", cnt);
        sort(ans + 1, ans + cnt + 1, cmp);
        for (int i = 1; i <= cnt; i++)
            printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].num, ans[i].house, ans[i].area);
        return 0;
    }

# L2-008 最长对称子串 #

#include <bits/stdc++.h>
    
    using namespace std;
    int len, ans;
    string str;
    
    int main()
    { 
        getline(cin, str);
        len = str.length();
        for (int i = 0; i < len; i++) { 
            for (int j = 0; (i - j) >= 0 && (i + j < len) && str[i - j] == str[i + j]; j++)
                ans = max(j * 2 + 1, ans);
            for (int j = 0; (i - j) >= 0 && (i + j + 1) < len && str[i - j] ==  str[i + j + 1]; j++)
                ans = max((j + 1) * 2, ans);
        }
        cout << ans << endl;
        return 0;
    }

# L2-009 抢红包 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1e4 + 5;
    int n, k, m, p;
    struct People { 
        int id, money, num;
    } s[maxn];
    
    bool cmp(const People &A, People &B) { 
        if (A.money == B.money) { 
            if (A.num == B.num) return A.id < B.id;
            else return A.num > B.num;
        } else { 
            return A.money > B.money;
        }
    }
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++) { 
            cin >> k;
            int sum = 0;
            for (int j = 1; j <= k; j++) { 
                cin >> m >> p;
                s[m].money += p;
                s[m].num++;
                sum += p;
            }
            s[i].id = i;
            s[i].money -= sum;
        }
        sort(s + 1, s + n + 1, cmp);
        for (int i = 1; i <= n; i++)
            printf("%d %.2f\n", s[i].id, s[i].money / 100.0);
        return 0;
    }

# L2-010 排座位 #

#include <bits/stdc++.h>
    
    using namespace std;
    typedef pair<int, int> pii;
    const int maxn = 105;
    int n, m, k;
    int p[maxn];
    map<pii, int> vis;
    
    int Find(int x) { 
        return p[x] == x ? x : p[x] = Find(p[x]);
    }
    
    int Merge(int x, int y) { 
        int tx = Find(x);
        int ty = Find(y);
        if (tx != ty) p[tx] = ty;
    }
    
    int main()
    { 
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i++) p[i] = i;
        for (int i = 1; i <= m; i++) { 
            int a, b, c;
            cin >> a >> b >> c;
            vis[make_pair(a, b)] = c;
            vis[make_pair(b, a)] = c;
            if (c == 1) Merge(a, b);
        }
        while (k--) { 
            int a, b;
            cin >> a >> b;
            int res = vis[make_pair(a, b)];
            if (res == 1) { 
                cout << "No problem" << endl;
            } else if (res == -1) { 
                int tx = Find(a);
                int ty = Find(b);
                if (tx == ty) cout << "OK but..." << endl;
                else cout << "No way" << endl;
            } else { 
                cout << "OK" << endl;
            }
        }
        return 0;
    }

# L2-011 玩转二叉树 #

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 50;
    int n;
    int pre_order[maxn], in_order[maxn];
    pair<int, int> tree[maxn];
    
    int build(int la, int ra, int lb, int rb) { 
        if (la > ra || lb > rb) return 0;
        int rt = pre_order[la];
        int p = 1;
        while (in_order[p] != rt) p++;
        int cnt = p - lb;
        tree[rt].first = build(la + 1, la + cnt, lb, p - 1);
        tree[rt].second = build(la + cnt + 1,ra, p + 1, rb);
        return rt;
    }
    
    void bfs(int rt) { 
        vector<int> ans;
        queue<int> q;
        q.push(rt);
        while (!q.empty()) { 
            int x = q.front();
            ans.push_back(x);
            q.pop();
            if (tree[x].second) q.push(tree[x].second);
            if (tree[x].first)  q.push(tree[x].first);
        }
        for (int i = 0; i < ans.size(); i++) { 
            if (i != 0) cout << " ";
            cout << ans[i];
        }
    }
    
    int main() { 
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> in_order[i];
        for (int i = 1; i <= n; i++) cin >> pre_order[i];
        int rt = build(1, n, 1, n);
        bfs(rt);
        return 0;
    }

# L2-012 关于堆的判断 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1010;
    int n, m;
    int Heap[maxn];
    map<int, int> mapper;
    
    void addNode(int temp, int idx) { 
        while (idx > 1 && temp  < Heap[idx / 2]) { 
            Heap[idx] = Heap[idx / 2];
            idx /= 2;
        }
        Heap[idx] = temp;
    }
    
    int main()
    { 
        cin >> n >> m;
        for (int i = 1; i <= n; i++) { 
            int t; cin >> t;
            addNode(t, i);
        }
        for (int i = 1; i <= n; i++) mapper[Heap[i]] = i;
        while (m--) { 
            int x, y;
            string s, s1, s2, s3, s4;
            cin >> x >> s;
            if (s == "is") { 
                cin >> s1 >> s2;
                s3 = s1 + s2;
                if (s3 == "theroot") { 
                    printf("%c\n", (mapper[x] == 1) ? 'T' : 'F');
                } else if (s3 == "theparent") { 
                    cin >> s4 >> y;
                    printf("%c\n", (mapper[x] == mapper[y]/2) ? 'T' : 'F');
                } else { 
                    cin >> s4 >> y;
                    printf("%c\n", (mapper[x]/2 == mapper[y]) ? 'T' : 'F');
                }
            } else { 
                cin >> y >> s1 >> s2;
                printf("%c\n", (mapper[x]/2 == mapper[y]/2) ? 'T' : 'F');
            }
        }
        return 0;
    }

# L2-013 红色警报 #

#include <bits/stdc++.h>
    #include <unordered_set>
    
    using namespace std;
    const int maxn = 510;
    int n, m, k, x, cnt;
    int p[maxn], mark[maxn];
    pair<int, int> edge[maxn * 10];
    
    void init(int n) { 
        for (int i = 0; i < n; i++) p[i] = i;
    }
    
    int Find(int x) { 
        return p[x] == x ? x : p[x] = Find(p[x]);
    }
    
    void Merge(int x, int y) { 
        int tx = Find(x);
        int ty = Find(y);
        if (tx != ty) p[tx] = ty;
    }
    
    int main()
    { 
        cin >> n >> m;
        init(n);
        for (int i = 0; i < m; i++) { 
            cin >> edge[i].first >> edge[i].second;
            Merge(edge[i].first, edge[i].second);
        }
        for (int i = 0; i < n; i++) { 
            if (p[i] == i) cnt++;
        }
        cin >> k;
        for (int i = 1; i <= k; i++) { 
            cin >> x;
            mark[x] = 1;
            init(n);
            for (int j = 0; j < m; j++) { 
                if (!mark[edge[j].first] && !mark[edge[j].second]) { 
                    Merge(edge[j].first, edge[j].second);
                }
            }
            int ans = 0;
            for (int j = 0; j < n; j++) { 
                if (!mark[j] && p[j] == j) ans++;
            }
            if (ans == cnt || ans + 1 == cnt) { 
                cout << "City "<< x << " is lost." << endl;
            } else { 
                cout << "Red Alert: City " << x << " is lost!" << endl;
            }
            cnt = ans;
        }
        if (k == n) { 
            cout << "Game Over." << endl;
        }
        return 0;
    }

# L2-014 列车调度 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1e5 + 10;
    int n, x;
    set<int> s;
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++) { 
            cin >> x;
            set<int>::iterator it = s.lower_bound(x);
            if (it == s.end()) { 
                s.insert(x);
            } else { 
                s.erase(it);
                s.insert(x);
            }
        }
        cout << s.size() << endl;
        return 0;
    }

# L2-015 互评成绩 #

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e4 + 10;
    int n, k, m;
    double score[maxn];
    int main()
    { 
        cin >> n >> k >> m;
        for (int i = 1; i <= n; i++) { 
            double sum = 0, t, maxx = 0, minn = maxn;
            for (int j = 1; j <= k; j++) { 
                cin >> t;
                sum += t;
                maxx = max(maxx, t);
                minn = min(minn, t);
            }
            sum -= maxx + minn;
            score[i] = sum / (k - 2);
        }
        sort(score + 1, score + n + 1);
        for (int i = n - m + 1; i <= n; i++) { 
            if (i != n - m + 1) putchar(' ');
            printf("%.3f", score[i]);
        }
        return 0;
    }

# L2-016 愿天下有情人都是失散多年的兄妹 #

#include <bits/stdc++.h>
    #include <unordered_set>
    
    using namespace std;
    typedef pair<int, int> pii;
    const int maxn = 1e5 + 10;
    int n, m, id, fa, mo;
    vector<int> tree[maxn];
    string sex[maxn];
    unordered_set<int> vis;
    
    int bfs(int rt) { 
        queue<pii> q;
        q.push(pii(rt, 0));
        while (!q.empty()) { 
            pii p = q.front();
            q.pop();
            int id = p.first, level = p.second;
            if (level > 4) return 1;
            if (vis.count(id)) return 0;
            vis.insert(id);
            for (int i = 0; i < tree[id].size(); i++) { 
                q.push(pii(tree[id][i], level + 1));
            }
        }
        return 1;
    }
    
    int main()
    { 
        cin >> n;
        for (int i = 0; i < n; i++) { 
            cin >> id; //注意：两句输入必须分开写
            cin >> sex[id] >> fa >> mo;
            if (fa != -1) { 
                sex[fa] = "M";
                tree[id].push_back(fa);
            }
            if (mo != -1) { 
                sex[mo] = "F";
                tree[id].push_back(mo);
            }
        }
        cin >> m;
        while (m--) { 
            int a, b;
            cin >> a >> b;
            if (sex[a] == sex[b]) { 
                cout << "Never Mind" << endl;
            } else { 
                vis.clear();
                bfs(a);
                if (bfs(b)) cout << "Yes" << endl;
                else cout << "No" << endl;
            }
        }
        return 0;
    }

# L2-017 人以群分 #

#include <bits/stdc++.h>
    
    using namespace std;
    int n, out, in, diff;
    vector<int> a;
    
    int main()
    { 
        cin >> n;
        for (int i = 0; i < n; i++) { 
            int t; cin >> t;
            a.push_back(t);
        }
        sort(a.begin(), a.end());
        if (n & 1) { 
            in = n / 2;
            out = in + 1;
        } else { 
            out = in = n / 2;
        }
    
        for (int i = in; i < a.size(); i++) diff += a[i];
        for (int i = 0; i < in; i++) diff -= a[i];
    
        cout << "Outgoing #: " << out << endl;
        cout << "Introverted #: " << in << endl;
        cout << "Diff = " << diff << endl;
        return 0;
    }

# L2-018 多项式A除以B #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 3010;
    int n, m, t, max1, max2;
    double c1[maxn], c2[maxn], c3[maxn];
    
    int getNum(double c[], int start) { 
        int cnt = 0;
        for (int i = 0; i <= start; i++)
            if (abs(c[i]) >= 0.1) cnt++;
        return cnt;
    }
    
    void printPoly(double c[], int start) { 
        printf("%d", getNum(c, start));
        if (!getNum(c, start)) printf(" 0 0.0");
        for (int i = start; i >= 0; i--)
            if (abs(c[i]) >= 0.1) printf(" %d %.1f", i, c[i]);
        putchar('\n');
    }
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++) { 
            cin >> t;
            max1 = max(max1, t);
            cin >> c1[t];
        }
        cin >> m;
        for (int i = 1; i <= m; i++) { 
            cin >> t;
            max2 = max(max2, t);
            cin >> c2[t];
        }
        int t1 = max1, t2 = max2;
        while (t1 >= t2) { 
            double c = c1[t1] / c2[t2];
            c3[t1 - t2] = c;
            for (int i = t1; i >= t1 - t2; i--)
                c1[i] -= c2[i - (t1 - t2)] * c;
            while (abs(c1[t1]) < 0.000001) t1--;
        }
        printPoly(c3, max1 - max2);
        printPoly(c1, t1);
        return 0;
    }

# L2-019 悄悄关注 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1e4 + 10;
    int n, m, num;
    double avg;
    set<string> follow;
    vector<string> ans;
    pair<string, int> a[maxn];
    string name;
    
    int main()
    { 
        cin >> n;
        for (int i = 0; i < n; i++) { 
            cin >> name;
            follow.insert(name);
        }
        cin >> m;
        for (int i = 0; i < m; i++) { 
            cin >> a[i].first >> a[i].second;
            avg += a[i].second;
        }
        avg /= m;
        for (int i = 0; i < m; i++) { 
            name = a[i].first;
            num = a[i].second;
            if (num > avg && !follow.count(name))
                ans.push_back(name);
        }
        sort(ans.begin(), ans.end());
        if (ans.size()) { 
            for (int i = 0; i < ans.size(); i++)
                cout << ans[i] << endl;
        } else { 
            cout << "Bing Mei You" << endl;
        }
        return 0;
    }

# L2-020 功夫传人 #

#include <bits/stdc++.h>
    
    using namespace std;
    typedef pair<int, double> pid;
    const int maxn = 1e5 + 10;
    int n, k, t;
    double z, r;
    vector<int> a[maxn];
    int mark[maxn];
    
    double bfs(int rt, double z, double r)
    { 
        double ans = 0;
        queue<pid> q;
        q.push(pid(rt, z));
        while (!q.empty()) { 
            pid p = q.front();
            q.pop();
            int id = p.first;
            if (mark[id]) { 
                ans += mark[id] * p.second;
                continue;
            }
            for (int i = 0; i < a[p.first].size(); i++) { 
                q.push(pid(a[p.first][i], p.second * (1.0 - r)));
            }
    // cout << p.first << " " << p.second << endl;
        }
        cout << (int)ans << endl;
    }
    
    int main()
    { 
        cin >> n >> z >> r;
        for (int i = 0; i < n; i++) { 
            cin >> k;
            if (k == 0) { 
                cin >> t;
                mark[i] = t;
            }
            for (int j = 0; j < k; j++) { 
                cin >> t;
                a[i].push_back(t);
            }
        }
        bfs(0, z, r / 100);
        return 0;
    }

# L2-021 点赞狂魔 #

#include <bits/stdc++.h>
    #include <unordered_set>
    
    using namespace std;
    const int maxn = 110;
    int n, k, t;
    struct Person { 
        char name[10];
        int num;
        double avg;
    } a[maxn];
    
    bool cmp(const Person &A, const Person &B) { 
        if (A.num == B.num) return A.avg < B.avg;
        else return A.num > B.num;
    }
    
    
    int main()
    { 
        cin >> n;
        for (int i = 0; i < n; i++) { 
            unordered_set<int> vis;
            cin >> a[i].name >> k;
            for (int j = 0; j < k; j++) { 
                cin >> t;
                vis.insert(t);
            }
            a[i].num = vis.size();
            a[i].avg = (double)k / a[i].num;
        }
        sort(a, a + n, cmp);
        int cnt = n > 3 ? 3 : n;
        for (int i = 0; i < cnt; i++) { 
            if (i != 0) putchar(' ');
            cout << a[i].name;
        }
        for (int i = 0; i < 3 - cnt; i++)
            cout << " -";
        cout << endl;
        return 0;
    }

# L2-022 重排链表 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1e5 + 10;
    int head, n, id;
    struct Node { 
        int data, next;
    } a[maxn];
    pair<int, int> ans[maxn];
    
    int main()
    { 
        cin >> head >> n;
        for (int i = 0; i < n; i++) { 
            cin >> id;
            cin >> a[id].data >> a[id].next;
        }
        int num = 0;
        for (int p = head; p != -1; p = a[p].next, num++);
        int t1 = 2, t2 = (num & 1) ? num : num - 1;
        for (int i = 1, p = head; p != -1; p = a[p].next) { 
            if (i <= num / 2) { 
                ans[t1].first = p;
                ans[t1].second = a[p].data;
                t1 += 2;
            } else { 
                ans[t2].first = p;
                ans[t2].second = a[p].data;
                t2 -= 2;
            }
            i++;
        }
        for (int i = 1; i <= num; i++) { 
            printf("%05d %d ", ans[i].first, ans[i].second);
            if (i != num) printf("%05d\n", ans[i + 1].first);
            else printf("-1\n");
        }
        return 0;
    }

# L2-023 图着色问题 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 510;
    int v, e, k, n;
    int a[maxn];
    vector<pair<int, int> > edge;
    
    int judge() { 
        for(int i = 0; i < edge.size(); i++) { 
            int u = edge[i].first;
            int v = edge[i].second;
            if (a[u] == a[v]) return 0;
        }
        return 1;
    }
    
    int main()
    { 
        cin >> v >> e >> k;
        for (int i = 0; i < e; i++) { 
            int u, v;
            cin >> u >> v;
            edge.push_back(make_pair(u, v));
        }
        cin >> n;
        while (n--) { 
            set<int> s;
            for (int i = 1; i <= v; i++) { 
                cin >> a[i];
                s.insert(a[i]);
            }
            if (s.size() != k) { 
                cout << "No" << endl;
                continue;
            }
            if (judge()) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        return 0;
    }

# L2-024 部落 #

#include <bits/stdc++.h>
    #include <unordered_set>
    using namespace std;
    const int maxn = 1e4 + 10;
    int n, m, k, a, b, cnt;
    //题目给出：所有人的编号从1开始连续编号
    int p[maxn];
    unordered_set<int> vis;
    
    int Find(int x) { 
        return p[x] == x ? x : p[x] = Find(p[x]);
    }
    
    void Merge(int x, int y) { 
        int tx = Find(x);
        int ty = Find(y);
        if (tx != ty) p[tx] = ty;
    }
    
    int main()
    { 
        //freopen("1.in", "r", stdin);
        cin >> n;
        for (int i = 1; i < maxn; i++) p[i] = i;
        for (int i = 0; i < n; i++) { 
            cin >> k;
            cin >> a;
            vis.insert(a);
            for (int j = 1; j < k; j++) { 
                cin >> b;
                vis.insert(b);
                Merge(a, b);
                a = b;
            }
        }
        for (int i = 1; i <= vis.size(); i++) { 
            if (p[i] == i) cnt++;
        }
        cout << vis.size() << " " << cnt << endl;
        cin >> m;
        while (m--) { 
            cin >> a >> b;
            if (Find(a) == Find(b)) { 
                cout << "Y" << endl;
            } else { 
                cout << "N" << endl;
            }
        }
        return 0;
    }

# L2-025 分而治之 #

#include <bits/stdc++.h>
    #include <unordered_set>
    
    using namespace std;
    const int maxn = 1e4 +10;
    int n, m, k;
    pair<int, int> edge[maxn];
    unordered_set<int> s;
    
    int main()
    { 
        cin >> n >> m;
        for (int i = 0; i < m; i++)
            cin >> edge[i].first >> edge[i].second;
        cin >> k;
        while (k--) { 
            int np; cin >> np;
            int flag = 1;
            s.clear();
            for (int i = 1; i <= np; i++) { 
                int t; cin >> t;
                s.insert(t);
            }
            for (int i = 0; i < m; i++) { 
                int u = edge[i].first, v = edge[i].second;
                if (!s.count(u) && !s.count(v)) { 
                    flag = 0;
                }
            }
            if (flag) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        return 0;
    }

# L2-026 小字辈 #

#include <bits/stdc++.h>
    
    using namespace std;
    typedef pair<int, int> pii;
    const int maxn = 1e5 +10;
    int n, t, rt;
    vector<int> tree[maxn];
    vector<pii> ans;
    
    void bfs(int rt) { 
        int maxx = 0;
        queue<pii> q;
        q.push(pii(rt, 1));
        while (!q.empty()) { 
            pii p = q.front();
            q.pop();
            int id = p.first;
            int level = p.second;
            if (!tree[id].size()) { 
                ans.push_back(pii(level, id));
                maxx = max(maxx, level);
            }
            for (int i = 0; i < tree[id].size(); i++) { 
                q.push(pii(tree[id][i], level + 1));
            }
        }
        int flag = 0;
        cout << maxx << endl;
        sort(ans.begin(), ans.end());
        for (int i = 0; i < ans.size(); i++) { 
            if (ans[i].first == maxx) { 
                if (flag) cout << " ";
                cout << ans[i].second;
                flag = 1;
            }
        }
    }
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; i++) { 
            cin >> t;
            if (t == -1) rt = i;
            else tree[t].push_back(i);
        }
        bfs(rt);
    
        return 0;
    }

# L2-027 名人堂与代金券 #

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 1e4 + 10;
    int n, g, k, sum, rate;
    struct Student{ 
        string name;
        int score;
    } s[maxn];
    
    bool cmp(const Student &A, const Student &B) { 
        if (A.score == B.score) return A.name < B.name;
        else return A.score > B.score;
    }
    
    int main()
    { 
        cin >> n >> g >> k;
        for (int i = 0; i < n; i++) { 
            cin >> s[i].name >> s[i].score;
            if (s[i].score >= 60 && s[i].score < g) { 
                sum += 20;
            } else if (s[i].score >= g) { 
                sum += 50;
            }
        }
        sort(s, s + n, cmp);
        cout << sum << endl;
        rate = 1;
        for (int i = 0; rate <= k && i < n; i++) { 
            cout << rate << " " << s[i].name << " " << s[i].score << endl;
            if (s[i].score != s[i + 1].score) { 
                rate = i + 2;
            }
        }
        return 0;
    }

# L2-028 秀恩爱分得快 #

#include <bits/stdc++.h>
    #include <unordered_set>
    
    using namespace std;
    const int maxn = 1010;
    int n, m, k, a, b;
    int sex[maxn];
    double pa_, pb_, pa[maxn], pb[maxn];
    vector<int> photo[maxn];
    unordered_set<int> have[maxn];
    
    int getNum(char *s) { 
        int num;
        if (s[0] == '-') { 
            num = atoi(s + 1);
            sex[num] = 1;
        } else { 
            num = atoi(s);
        }
        return num;
    }
    
    void printRes(int x, int y) { 
        if (sex[x]) putchar('-');
        cout << x << " ";
        if (sex[y]) putchar('-');
        cout << y << endl;
    }
    
    int main()
    { 
        cin >> n >> m;
        for (int i = 0; i < m; i++) { 
            cin >> k;
            for (int j = 0; j < k; j++) { 
                char t[10]; cin >> t;
                photo[i].push_back(getNum(t));
                have[i].insert(getNum(t));
            }
        }
        char s1[10], s2[10];
        cin >> s1 >> s2;
        a = getNum(s1), b = getNum(s2);
        for (int i = 0; i < m; i++) { 
            int have_a = have[i].count(a);
            int have_b = have[i].count(b);
            if (have_a || have_b)
            for (int j = 0; j < photo[i].size(); j++) { 
                int t = photo[i][j];
                if (have_a && sex[t] != sex[a]) { 
                    pa[t] += 1.0 / photo[i].size();
                    pa_ = max(pa[t], pa_);
                } else if (have_b && sex[t] != sex[b]) { 
                    pb[t] += 1.0 / photo[i].size();
                    pb_ = max(pb[t], pb_);
                }
            }
        }
        if (pa_ == pa[b] && pb_ == pb[a]) { 
            printRes(a, b);
        } else { 
            for (int i = 0; i < n; i++)
            if (pa_ == pa[i]) { 
                printRes(a, i);
            }
            for (int i = 0; i < n; i++)
            if (pb_ == pb[i]) { 
                printRes(b, i);
            }
        }
        return 0;
    }

# L2-029 特立独行的幸福 #

#include <bits/stdc++.h>
    #include <unordered_set>
    
    using namespace std;
    typedef pair<int, int> pii;
    const int maxn = 1e4 + 10;
    int x, y, flag;
    int vis[maxn];
    map<int, int> ans;
    
    int isPrime(int x) { 
        for (int i = 2; i <= sqrt(x); i++)
            if (x % i == 0) return 1;
        return 2;
    }
    
    int fun(int x) { 
        int ans = 0;
        while (x != 0) { 
            int t = x % 10;
            ans += t * t;
            x /= 10;
        }
        return ans;
    }
    
    void solve(int l, int r) { 
    
        for (int i = l; i <= r; i++) { 
            int t = i;
            if (vis[t]) continue;
            set<int> s;
            while (t != 1) { 
                t = fun(t);
                if (s.count(t)) break;
                s.insert(t);
                vis[t] = 1;
            }
            if (t == 1) ans[i] = s.size();
        }
    }
    
    int main()
    { 
        cin >> x >> y;
        solve(x, y);
        for (auto i : ans) { 
            if (!vis[i.first]) { 
                cout << i.first << " " << i.second * isPrime(i.first) << endl;
                flag = 1;
            }
        }
        if (!flag) cout << "SAD" << endl;
        return 0;
    }

# L2-030 冰岛人 #

#include <bits/stdc++.h>
    using namespace std;
    bool judge(vector<int> &F, int s1, int s2)
    { 
        int n = F.size();
        vector<int> count(n, 0);
        vector<int> dist1(n, 0);
        vector<int> dist2(n, 0);
        int t ;
        count[s1]++;
        count[s2]++;
        while(F[s1] != -1)
        { 
            t = F[s1];
            count[t]++;
            dist1[t] = dist1[s1] + 1;
            if(t == s2)			//直系祖宗
              return false;
            s1 = t;
        }
        while(F[s2] != -1)
        { 
            t = F[s2];
            count[t]++;
            dist2[t] = dist2[s2] + 1;
            if(count[t] > 1)
            { 
                if(dist2[t]>=4 && dist1[t] >= 4)
                    return true;
                else
                    return false;
            }
            s2 = t;
        }
        return true;
    }
    int main()
    { 
        int n;
        cin >> n;
        string f1, f2;
        vector<bool> sex(n);
        vector<vector<string> > record(n);
        map<string, int> M;			//给每个人编号
        vector<int> F(n, -1);		//父节点编号
        int cnt = 0;
        for(int i=0;i<n;i++)		//编号
        { 
            cin >> f1 >> f2;
            M.insert(make_pair(f1, cnt));
            int l = f2.size();
            if(f2[l-1] == 'm' || f2[l-1] == 'n')
                sex[cnt] = 1;       //男
            else
                sex[cnt] = 0;
            cnt++;
            record[i].push_back(f1);
            record[i].push_back(f2);
        }
        string par;
        for(int i=0;i<n;i++)		//找父节点
        { 
            f1 = record[i][0];
            f2 = record[i][1];
            int len = f2.size();
            if(f2[len-1] != 'r' && f2[len-1] != 'n')	//老祖宗
                continue;
            if(sex[M[f1]] == true)
                par = f2.substr(0, len-4);
            else
                par = f2.substr(0, len-7);
            F[M[f1]] = M[par];
        }
        int m;
        cin >> m;
        string t1,t2;
        for(int i=0;i<m;i++)
        { 
            cin >> f1 >> f2 >> t1 >> t2;
            if(M.find(f1) == M.end() || M.find(t1) == M.end() )
            { 
                cout << "NA" << endl;
                continue;
            }
            if(sex[M[f1]] == sex[M[t1]])
            { 
                cout << "Whatever" << endl;
                continue;
            }
            if(judge(F, M[f1], M[t1]))
            { 
                cout << "Yes" << endl;
            }
            else
                cout << "No" << endl;
        }
        return 0;
    }

# L2-031 深入虎穴 #

#include <bits/stdc++.h>
    
    using namespace std;
    typedef pair<int, int> pii;
    const int maxn = 1e5 + 10;
    int n, k;
    vector<int> tree[maxn];
    
    void bfs(int rt) { 
        int t;
        queue<int> q;
        q.push(rt);
        while (!q.empty()) { 
            t = q.front();
            q.pop();
            if (!tree[t].size()) continue;
            for (int i = 0; i < tree[t].size(); i++) { 
                q.push(tree[t][i]);
            }
        }
        cout << t << endl;
    }
    
    int main()
    { 
        cin >> n;
        int root = n * (n + 1) / 2;
        for (int i = 1; i <= n; i++) { 
            cin >> k;
            for(int j = 1; j <= k; j++) { 
                int t; cin >> t;
                root -= t;
                tree[i].push_back(t);
            }
        }
        bfs(root);
        return 0;
    }

# L2-032 彩虹瓶 #

#include <bits/stdc++.h>
    
    using namespace std;
    int n, m, k;
    stack<int> s;
    
    int main()
    { 
        cin >> n >> m >> k;
        while (k--) { 
            int num = 1, flag = 1;
            while (!s.empty()) s.pop();
            for (int i = 1; i <= n; i++) { 
                int t; cin >> t;
                while (!s.empty() && s.top() == num) { 
                    num++;
                    s.pop();
                }
                if (t == num) num++;
                else s.push(t);
                if (s.size() > m) flag = 0;
            }
            while (!s.empty() && s.top() == num) { 
                    num++;
                    s.pop();
            }
            if (num == n + 1 && flag) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        return 0;
    }

--------------------

2020年11月27日23:34:23 更新完毕，祝大家明天rp++。

2020年11月28日20:55:17 完赛，拖累了队友，确实应该退役了。