本文共 8893 字，大约阅读时间需要 29 分钟。

以下是优化后的内容：

天梯赛 L3 练习题 1

题目1：L3-001 鑄零钱

题意：给定n枚硬币的面值，问能否恰好凑成m元。输出字典序最小的排列，或者输出“No Solution”。

思路：贪心算法，从小面额硬币开始取，这样排列才会字典序最小。使用动态规划记录能否凑成每个金额，并记录路径。

代码示例：

#include 
   
    
#include 
    
     
using namespace std;
int main() {
    int n, m;
    vector
     
       a(n);
    // 读取输入并排序
    sort(a.begin(), a.end());
    // 初始化dp数组
    vector
      
        dp(m + 1, false);
    dp[0] = true;
    // 遍历每个硬币
    for (int i = 0; i < n; ++i) {
        int val = a[i];
        for (int j = m; j >= val; --j) {
            if (dp[j - val] && !dp[j]) {
                dp[j] = true;
            }
        }
    }
    if (!dp[m]) {
        puts("No Solution");
    } else {
        // 回溯路径
        vector
       
         ans;
        int cur = m;
        for (int i = n - 1; i >= 0; --i) {
            if (cur >= a[i] && dp[cur - a[i]]) {
                ans.push_back(a[i]);
                cur -= a[i];
            }
        }
        // 输出结果
        int len = ans.size();
        for (int i = 0; i < len; ++i) {
            if (i != len - 1) {
                printf("%d", ans[i]);
            } else {
                printf("%d\n", ans[i]);
            }
        }
    }
    return 0;
}
       
      
     
    
   

题目2：L3-002 特殊堆栈

题意：维护一个栈，支持Push、Pop、PeekMedian操作。PeekMedian要求输出栈中第(n+1)/2小的数。

思路：使用线段树维护元素个数，通过二分查找找到第k小的元素。

代码示例：

#include 
   
    
#include 
    
     
using namespace std;
int main() {
    int n;
    vector
     
       sta(n);
    // 初始化线段树
    vector
      
        st(4 * n, 0);
    // Push操作
    while (n--) {
        string s;
        cin >> s;
        if (s == "Push") {
            int val = sta[top];
            update(1, val, 1, n, 1);
            sta[++top] = val;
        } else if (s == "Pop") {
            if (!top) {
                puts("Invalid");
                continue;
            }
            int val = sta[top];
            update(1, val, 1, n, -1);
            sta[top--] = 0;
        } else {
            if (!top) {
                puts("Invalid");
                continue;
            }
            int k = (top + 1) / 2;
            int res = query(1, k, 1, n);
            puts(res);
        }
    }
    return 0;
}
      
     
    
   

题目3：L3-003 社交集群

题意：给定n个人的兴趣列表，找出每个社交集群的人数。

思路：使用并查集，合并具有相同兴趣爱好的节点，最后统计每个根节点的大小。

代码示例：

#include 
   
    
using namespace std;
int main() {
    int n;
    vector
    
      pa(n + 1), sz(n + 1);
    for (int i = 1; i <= n; ++i) {
        int k, x, y;
        cin >> k >> x >> y;
        visit[x] = 1;
        for (int i = 2; i <= k; ++i) {
            cin >> y;
            visit[y] = 1;
            union(x, y);
        }
        sz[find(x)]++;
    }
    // 收集结果并排序
    vector
     
       ans;
    for (int i = 1; i <= 1000; ++i) {
        if (pa[i] == i && visit[i]) {
            ans.push_back(sz[i]);
        }
    }
    sort(ans.begin(), ans.end(), greater
      
       ());
    int m = ans.size();
    printf("%d\n", m);
    if (m > 0) {
        for (int i = 1; i <= m; ++i) {
            if (i != m) {
                printf("%d", ans[i - 1]);
            } else {
                printf("%d\n", ans[i - 1]);
            }
        }
    }
    return 0;
}
      
     
    
   

题目4：L3-005 垃圾箱分布

题意：选择一个垃圾箱点，使得到其他住户的最小距离最大，相同则平均距离最小，相同则编号最小。

思路：对每个点，计算到所有住户的最短距离总和，找出总和最大的点。

代码示例：

#include 
   
    
#include 
    
     
using namespace std;
int main() {
    int n, m, k, d;
    vector
     
      
       > e;
    for (int i = 1; i <= k; ++i) {
        string x, y;
        int w;
        cin >> x >> y >> w;
        int u = calc(x), v = calc(y);
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    // 计算每个点的总距离
    int ans1 = 0, ans2 = INF;
    int best = -1;
    for (int i = 1; i <= m; ++i) {
        int s = n + i;
        // 使用Dijkstra计算每个住户的最短距离
        vector
       
         dis(n + 1, INF);
        vector
        
          sum_d(n + 1, 0); int ok = 1; for (int j = 1; j <= n; ++j) { if (dis[j] > d) { ok = 0; break; } sum_d[j] += dis[j]; } if (!ok) continue; if (sum_d[j] > sum_d[best]) { ans1 = sum_d[j]; best = i; } else if (sum_d[j] == sum_d[best]) { if (i < best) { best = i; } } } // 输出结果 if (best != -1) { int s = n + best; // 进行Dijkstra计算每个住户的最短距离 vector
         
           dis(n + 1, INF); for (int j = 1; j <= n; ++j) dis[j] = INF; dis[s] = 0; // 使用优先队列 priority_queue
          
           
            > pq; pq.push({0, s}); while (!pq.empty()) { int d, u = pq.top().second; pq.pop(); if (visit[u]) continue; visit[u] = 1; for (auto v : e[u]) { int v_node = v.first, weight = v.second; if (dis[v_node] > dis[u] + weight) { dis[v_node] = dis[u] + weight; pq.push({dis[v_node], v_node}); } } } // 计算各住户的距离 int max_d = 0, sum_d = 0; int max_id = -1; for (int j = 1; j <= n; ++j) { if (dis[j] > max_d) { max_d = dis[j]; max_id = j; } sum_d += dis[j]; } // 输出结果 printf("%d\n", max_d); vector
            
              res; int cur = max_id; do { res.push_back(cur); cur = pre[cur]; } while (cur != -1); reverse(res.begin(), res.end()); int m_res = res.size(); for (int i = 0; i < m_res; ++i) { if (i != m_res - 1) { printf("%d", res[i]); } else { printf("%d\n", res[i]); } } } else { puts("No Solution"); } return 0; }
            
           
          
         
        
       
      
     
    
   

题目5：L3-007 天梯地图

题意：给定图的边权有时间和距离两种，找出两条路径：时间最短和距离最短。

思路：分别运行两次Dijkstra，一次记录时间，另一次记录距离和经过点数。

代码示例：

#include 
   
    
#include 
    
     
using namespace std;
int main() {
    int n, m;
    vector
     
      
       > e;
    for (int i = 1; i <= m; ++i) {
        int u, v, ty, w, t;
        cin >> u >> v >> ty >> w >> t;
        e[u].push_back({v, w, t});
        e[v].push_back({u, w, t});
    }
    // 时间最短路径
    int time shortest, dis shortest;
    vector
       
         time_path, dis_path, num_path;
    // 距离最短路径
    int dist shortest, dist_num shortest;
    // 两次Dijkstra
    // ...
    // 输出结果
    printf("Time: %d Distance: %d Path: ", time_shortest, dis_shortest);
    // 输出路径
    // ...
    return 0;
}
       
      
     
    
   

题目6：L3-008 告诉山

题意：无向图中，查询给定节点到图中其他节点的最远距离及对应的节点编号。

思路：使用BFS计算每个节点的深度，记录最远距离和对应的节点。

代码示例：

#include 
   
    
using namespace std;
int main() {
    int n, m, q;
    vector
    
     
      > e;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    // 处理每个查询
    for (int i = 1; i <= q; ++i) {
        int x;
        cin >> x;
        // BFS计算深度
        vector
      
        depth(n + 1, 0);
        vector
       
         visit(n + 1, false);
        queue
        
          q; q.push(x); visit[x] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : e[u]) { if (!visit[v]) { visit[v] = true; depth[v] = depth[u] + 1; q.push(v); } } } // 找最大深度的节点 int max_d = *max_element(depth.begin() + 1, depth.begin() + n + 1); int id = 0; if (max_d > 1) { for (int j = 1; j <= n; ++j) { if (depth[j] == max_d) { id = j; break; } } } ans.push_back(id); } // 输出结果 for (int i = 1; i <= q; ++i) { printf("%d\n", ans[i - 1]); } return 0; }
        
       
      
     
    
   

题目7：L3-009 长城

题意：设置烽火台，使得从右往左可以一直被看到。

思路：从右往左扫描，当遇到一个凸点挡住视线时，设置这个点为烽火台。

代码示例：

#include 
   
    
using namespace std;
int main() {
    int n;
    vector
    
      x(n + 1), y(n + 1);
    // 设置栈
    set
     
       ans;
    int top = 0;
    for (int i = 1; i <= n; ++i) {
        while (top >= 1 && check(i, sta[top], sta[top - 1])) {
            top--;
        }
        if (top >= 1 && sta[top] != 1) {
            ans.insert(sta[top]);
        }
        sta[++top] = i;
    }
    // 输出结果
    printf("%d\n", ans.size());
    return 0;
}
     
    
   

题目8：L3-010 是否完全二叉搜索树

题意：判断给定的树是否为完全二叉树。

思路：层序遍历时，检查除了最后一层外，其他层是否完全填充。

代码示例：

#include 
   
    
using namespace std;
int main() {
    int n;
    vector
    
      a(n + 1);
    // 插入到树中
    Node* root = new Node();
    for (int i = 1; i <= n; ++i) {
        insert(root, a[i]);
    }
    // BFS遍历
    vector
     
       ans;
    int sta = 0;
    queue
      
        q;
    q.push(root);
    while (!q.empty()) {
        Node* t = q.front();
        q.pop();
        if (sta == 0) {
            sta = 1;
        }
        if (sta == 1) {
            sta = 2;
        }
        ans.push_back(t->val);
        if (t->ls) q.push(t->ls);
        if (t->rs) q.push(t->rs);
    }
    // 判断是否为完全二叉树
    if (sta != 2) {
        puts("YES");
    } else {
        puts("NO");
    }
    return 0;
}
      
     
    
   

题目9：L3-011 直捣黄龙

题意：带权图中，找出一条最短路径，满足特定规则。

思路：使用Dijkstra算法，记录路径长度、经过的点数和杀敌数，满足优先级顺序。

代码示例：

#include 
   
    
using namespace std;
int main() {
    int n, m;
    map
    
      id, name;
    // 读取输入
    while (m--) {
        string x, y;
        int w;
        cin >> x >> y >> w;
        int u = id[x], v = id[y];
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    // Dijkstra算法
    int shortest_path_length, shortest_dist, kills;
    vector
     
       path;
    // 详细实现见代码
    // ...
    // 输出结果
    printf("%d %d %d\n", path_size, shortest_dist, kills);
    return 0;
}
     
    
   

总结

以上是对每个题目的分析和简要代码示例，希望对解决问题有所帮助。