Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

D. Penchick and Desert Rabbit time limit per test: 3 seconds memory limit per test: 256…

  1. User

    D. Penchick and Desert Rabbit

    time limit per test: 3 seconds

    memory limit per test: 256 megabytes

    input: standard input

    output: standard output

    题目描述

    彭契克致力于挑战自己的极限,他挑战自己在阿拉伯沙漠的正午阳光下生存!

    当彭奇克沿着一片线状绿洲跋涉时,他发现一只沙漠兔正准备沿着一排棕榈树跳跃。这里有 nn 棵树,每棵树的高度用 aia_i 表示。

    如果以下条件中正好有一个为真,兔子就能从 ii (第3棵树)跳到 jj (第3棵树):

    • j<ij \lt i 和 aj>aia_j \gt a_i :兔子可以向后跳到更高的树上。
    • j>ij \gt i 和 aj<aia_j \lt a_i :兔子可以向前跳到较矮的树上。

    对于从 11 到 nn 的每棵 ii ,确定兔子从 ii -th的树开始,可以到达的最大高度。

    输入格式

    第一行包含测试用例的数量 tt ( 1≤t≤5⋅1051 \le t \le 5 \cdot 10^5 )。测试用例说明如下。

    每个测试用例的第一行都包含一个整数 nn ( 1≤n≤5⋅1051 \leq n \leq 5 \cdot 10^5 ) - 树的数量。

    每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n ( 1≤ai≤n1 \le a_i \le n ) - 树的高度。

    保证所有测试用例中 nn 的总和不超过 5⋅1055 \cdot 10^5 。

    输出格式

    对于每个测试用例,输出 nn 个整数。 ii 个整数应该包含兔子从 ii 棵树开始能到达的所有树的最大高度。

    样例 #1

    样例输入 #1

    5
    4
    2 3 1 4
    5
    5 4 3 2 1
    4
    2 1 1 3
    4
    1 1 3 1
    8
    2 4 1 6 3 8 5 7
    

    样例输出 #1

    3 3 3 4 
    5 5 5 5 5 
    2 2 2 3 
    1 1 3 3 
    8 8 8 8 8 8 8 8 
    

    提示

    注

    在第一个测试案例中,树木的初始高度为 a=[2,3,1,4]a = [2, 3, 1, 4] 。

    • 如果兔子从第一棵树开始,它可以跳到第三棵树,高度为 3>13 \gt 1 和 1<21 \lt 2 。然后,兔子可以跳到第二棵树的位置是 2<32 \lt 3 和 3>13 \gt 1 。可以证明兔子无法到达第四棵树;因此,兔子能到达的最大树高为 a2=3a_2 = 3 。
    • 如果兔子从第四棵树开始,它不需要跳到任何地方,因为它已经在最高的树上了。

    在第二个测试案例中,无论兔子从哪棵树开始,它都能跳到第一棵树上。

    在第五个测试案例中,如果兔子从第五棵树开始,它可以跳到第四棵树。然后,兔子可以跳到第七棵树,最后到达第六棵树。因此,兔子能到达的最大树高是 88 。

    用c++写,并解释代码和思路,用中文。

  2. Assistant

    要解决这个问题,我们需要为每个测试用例中的每棵树计算兔子从该树出发能够达到的最大高度。兔子的跳跃规则如下:

    • 向左跳跃:跳到左边更高的树。
    • 向右跳跃:跳到右边更低的树。

    为了解决这个问题,我们采用以下步骤:

    步骤1:寻找跳跃的位置

    对于每棵树,我们需要找到符合跳跃条件的下一个位置:

    • 左边跳跃:对于每棵树,找到其左边最近的、且高度更高的树。
    • 右边跳跃:对于每棵树,找到其右边最近的、且高度更低的树。

    这可以通过单调栈(Monotonic Stack)高效地完成:

    • 左边跳跃:使用一个递减的单调栈寻找最近的更高树。
    • 右边跳跃:使用一个递增的单调栈寻找最近的更低树。

    步骤2:构建跳跃图

    一旦我们确定了每棵树可以跳到的位置,我们可以将这些跳跃关系看作一个有向图的边。具体来说,对于每棵树,如果它可以跳到左边的某棵树或右边的某棵树,则在图中添加相应的边。

    步骤3:强连通分量(SCC)

    由于跳跃关系可能形成环路(即某些树之间可以互相跳跃形成一个循环),我们需要将图分解为若干个强连通分量(SCC)。在每个SCC中,所有的树都可以互相到达,因此在一个SCC内部,最大高度是这些树中的最大值。

    步骤4:构建缩点图并进行拓扑排序

    接下来,我们将每个SCC看作图中的一个“超级节点”,并构建缩点图。缩点图是一个DAG(有向无环图),可以进行拓扑排序。通过拓扑排序,我们可以按照依赖关系从下游到上游逐步计算每个“超级节点”的最大可达高度。

    步骤5:计算每棵树的最大可达高度

    通过上述步骤,我们可以为每个SCC计算其最大可达高度。然后,对于每棵树,其最大可达高度即为其所属SCC的最大可达高度。

    代码实现

    以下是上述思路的C++实现代码:

    #include <bits/stdc++.h>
    using namespace std;
    
    // Fast I/O
    struct FastIO {
        FastIO() {
            ios::sync_with_stdio(false);
            cin.tie(NULL);
        }
    };
    
    // Tarjan's algorithm for SCC
    struct TarjanSCC {
        int n;
        vector<vector<int>> adj;
        vector<int> index_;
        vector<int> lowlink;
        int current_index;
        stack<int> S;
        vector<bool> onStack;
        vector<int> scc_id;
        int num_scc;
    
        TarjanSCC(int size) : n(size), adj(n, vector<int>()), index_(n, -1), lowlink(n, 0),
                               current_index(0), onStack(n, false), scc_id(n, -1), num_scc(0) {}
    
        void add_edge(int u, int v){
            adj[u].push_back(v);
        }
    
        void strongconnect(int v){
            index_[v] = current_index;
            lowlink[v] = current_index;
            current_index++;
            S.push(v);
            onStack[v] = true;
    
            for(auto &w : adj[v]){
                if(index_[w] == -1){
                    strongconnect(w);
                    lowlink[v] = min(lowlink[v], lowlink[w]);
                }
                else if(onStack[w]){
                    lowlink[v] = min(lowlink[v], index_[w]);
                }
            }
    
            if(lowlink[v] == index_[v]){
                while(true){
                    int w = S.top(); S.pop();
                    onStack[w] = false;
                    scc_id[w] = num_scc;
                    if(w == v) break;
                }
                num_scc++;
            }
        }
    
        void compute_scc(){
            for(int v=0; v<n; v++){
                if(index_[v] == -1){
                    strongconnect(v);
                }
            }
        }
    };
    
    int main(){
        FastIO fio;
        int t;
        cin >> t;
        while(t--){
            int n;
            cin >> n;
            vector<int> a(n);
            for(auto &x: a) cin >> x;
    
            // Compute left[i]: nearest j <i with a[j] >a[i]
            vector<int> left(n, -1);
            stack<int> s;
            for(int i=0; i<n; i++){
                while(!s.empty() && a[s.top()] <= a[i]){
                    s.pop();
                }
                if(!s.empty()){
                    left[i] = s.top();
                }
                s.push(i);
            }
    
            // Compute right[i]: nearest j >i with a[j] <a[i]
            vector<int> right(n, -1);
            while(!s.empty()) s.pop(); // Clear the stack
            for(int i=n-1; i>=0; i--){
                while(!s.empty() && a[s.top()] >= a[i]){
                    s.pop();
                }
                if(!s.empty()){
                    right[i] = s.top();
                }
                s.push(i);
            }
    
            // Initialize Tarjan's SCC
            TarjanSCC tarjan(n);
    
            // Build the graph
            for(int i=0; i<n; i++){
                if(left[i] != -1){
                    tarjan.add_edge(i, left[i]);
                }
                if(right[i] != -1){
                    tarjan.add_edge(i, right[i]);
                }
            }
    
            // Compute SCCs
            tarjan.compute_scc();
    
            int num_scc = tarjan.num_scc;
            // Assign maximum a_i for each SCC
            vector<int> scc_max_a(num_scc, 0);
            for(int i=0; i<n; i++){
                scc_max_a[tarjan.scc_id[i]] = max(scc_max_a[tarjan.scc_id[i]], a[i]);
            }
    
            // Build condensation graph
            vector<vector<int>> cond_adj(num_scc, vector<int>());
            for(int i=0; i<n; i++){
                for(auto &j : tarjan.adj[i]){
                    if(tarjan.scc_id[i] != tarjan.scc_id[j]){
                        cond_adj[tarjan.scc_id[i]].push_back(tarjan.scc_id[j]);
                    }
                }
            }
    
            // Remove duplicate edges in condensation graph
            for(int i=0; i<num_scc; i++){
                sort(cond_adj[i].begin(), cond_adj[i].end());
                cond_adj[i].erase(unique(cond_adj[i].begin(), cond_adj[i].end()), cond_adj[i].end());
            }
    
            // Topological sort on condensation graph
            // Kahn's algorithm
            vector<int> in_degree(num_scc, 0);
            for(int i=0; i<num_scc; i++){
                for(auto &j : cond_adj[i]){
                    in_degree[j]++;
                }
            }
    
            queue<int> q;
            for(int i=0; i<num_scc; i++) if(in_degree[i]==0) q.push(i);
            vector<int> topo_order;
            while(!q.empty()){
                int u = q.front(); q.pop();
                topo_order.push_back(u);
                for(auto &v : cond_adj[u]){
                    in_degree[v]--;
                    if(in_degree[v]==0){
                        q.push(v);
                    }
                }
            }
    
            // Now process in reverse topological order
            // Initialize max_reach
            vector<int> max_reach(num_scc, 0);
            for(int i=0; i<num_scc; i++) max_reach[i] = scc_max_a[i];
    
            for(int i=topo_order.size()-1; i>=0; i--){
                int u = topo_order[i];
                for(auto &v : cond_adj[u]){
                    if(max_reach[u] < max_reach[v]){
                        max_reach[u] = max_reach[v];
                    }
                }
            }
    
            // Assign results
            vector<int> res(n, 0);
            for(int i=0; i<n; i++) res[i] = max_reach[tarjan.scc_id[i]];
    
            // Output
            for(int i=0; i<n; i++) cout << res[i] << (i<n-1?" ":"\n");
        }
    }
    

    代码解释

    1. 快速输入输出:通过禁用同步和解绑 cin 和 cout 来加速输入输出。

    2. 强连通分量(Tarjan算法):实现了Tarjan算法来找到图中的所有强连通分量。每个SCC被赋予一个唯一的ID,并且记录每个SCC内的最大高度。

    3. 寻找跳跃位置:

      • 左边跳跃:使用单调递减栈找到每棵树左边最近的更高树。
      • 右边跳跃:使用单调递增栈找到每棵树右边最近的更低树。
    4. 构建跳跃图:根据找到的跳跃位置,为每棵树添加相应的边。

    5. 构建缩点图并拓扑排序:将每个SCC视为一个“超级节点”,构建缩点图并进行拓扑排序,以确定处理顺序。

    6. 计算最大可达高度:按照拓扑排序的逆序,更新每个“超级节点”的最大可达高度。

    7. 输出结果:根据每棵树所属的SCC,输出其对应的最大可达高度。

    复杂度分析

    • 时间复杂度:每个测试用例的时间复杂度为 ( O(n) ),总体时间复杂度为 ( O(\sum n) ),其中 ( \sum n \leq 5 \times 10^5 )。

    • 空间复杂度:使用了额外的空间来存储图和SCC信息,空间复杂度也是 ( O(n) ) 每个测试用例。

    总结

    通过使用单调栈来高效找到跳跃位置,并结合Tarjan算法和拓扑排序,我们能够在线性时间内计算出每棵树的最大可达高度。这种方法不仅高效,而且适用于大规模数据。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.